Existence of constants in regular splicing languages.
Existence of constants in regular splicing languages.
复制标题
常规拼接语言中常量的存在。
DOI：
10.1016/j.ic.2015.04.001
复制
发表时间：
2015
影响因子：
1
通讯作者：
Jonoska,Nataša
中科院分区：
文献类型：
--
作者：
Bonizzoni,Paola;Jonoska,Nataša
尽管在形式语言理论中对有限拼接系统进行了广泛的研究，但诸如其特征描述等基本问题仍然没有解决。正则语言L成为拼接语言的一个必要条件是L必须有一个Schützenberger意义上的常数。我们证明这个长期存在的猜想是正确的。结果是基于最小的确定性有限状态自动机的规则拼接语言的强连接组件的属性。利用相应语言的常数，我们还给出了传递自动机和路径自动机的性质。
In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. It has been conjectured that a necessary condition for a regular languageLto be a splicing language is thatLmust have a constant in the Schützenberger sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language. Using constants of the corresponding languages, we also provide properties of transitive automata and path-automata.