Decision Problems for Language Equations with Boolean Operations
Decision Problems for Language Equations with Boolean Operations
复制标题
具有布尔运算的语言方程的决策问题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
A. Okhotin
中科院分区：
文献类型：
--
作者：
A. Okhotin
这篇论文研究了语言方程的分解系统，它允许使用除连接之外的所有布尔运算。证明了解的存在唯一性是它们的非平凡性质，用一阶公式刻画了这些性质，并确定了相应的决策问题在算术族中的位置。由这种系统的唯一解的分量定义的语言类被证明与递归语言类重合。
The paper studies resolved systems of language equations that allow the use of all Boolean operations in addition to concatenation. Existence and uniqueness of solutions are shown to be their nontrivial properties, these properties are given characterizations by first order formulae, and the position of the corresponding decision problems in the arithmetical hierarchy is determined. The class of languages defined by components of unique solutions of such systems is shown to coincide with the class of recursive languages.