论文标题
有限语言，反机器，有限索引语法，歧义和合理性的关系之间的关系
Relationships Between Bounded Languages, Counter Machines, Finite-Index Grammars, Ambiguity, and Commutative Regularity
论文作者
论文摘要
结果表明，对于仅包含半连接语言的每个语言家族，其中所有有界语言都可以通过单向确定性逆转的多次互动计算机（DCM）接受。这意味着，对于每个半线性三重奏（这些属性是有效的），就可以决定有关其有限语言的遏制，等效性和矛盾性。还提供了一个条件，何时与DCM机器所接受的半线性三人组中的有限语言完全一致，并且它用于表明许多有限索引的语法系统（例如有限索引矩阵语法和有限索引ETOL）具有与DCM相同的界限语言。 然后，建立了歧义性，计算规律性和交换性规律性之间的连接，因为明确的许多机器和语法只能产生/接受定期或换算的规则语言。因此，这样的系统可以生成/接受非规则或非共同的规则语言意味着在该系统上存在固有的模棱两可的语言。此外，还表明，由明确的有限索引矩阵语法产生的每种语言都具有合理的特征序列，并在通勤变量中进行计数。此结果加上连接用于证明有限索引矩阵语法和有限索引ETOL可以像几种机器模型一样生成固有的模棱两可的语言（在语法上）。还表明，这两个语法系统（任何半线性三重奏中的语法系统）生成的所有有限语言都可以在系统中明确生成。最后，获得了有限索引矩阵语法产生的语言条件和有限索引的Etol，这意味着可交换规律性。特别是，每种有限索引EDOL语言都是正常的。
It is shown that for every language family that is a trio containing only semilinear languages, all bounded languages in it can be accepted by one-way deterministic reversal-bounded multicounter machines (DCM). This implies that for every semilinear trio (where these properties are effective), it is possible to decide containment, equivalence, and disjointness concerning its bounded languages. A condition is also provided for when the bounded languages in a semilinear trio coincide exactly with those accepted by DCM machines, and it is used to show that many grammar systems of finite index -- such as finite-index matrix grammars and finite-index ETOL -- have identical bounded languages as DCM. Then connections between ambiguity, counting regularity, and commutative regularity are made, as many machines and grammars that are unambiguous can only generate/accept counting regular or commutatively regular languages. Thus, such a system that can generate/accept a non-counting regular or non-commutatively regular language implies the existence of inherently ambiguous languages over that system. In addition, it is shown that every language generated by an unambiguous finite-index matrix grammar has a rational characteristic series in commutative variables, and is counting regular. This result plus the connections are used to demonstrate that finite-index matrix grammars and finite-index ETOL can generate inherently ambiguous languages (over their grammars), as do several machine models. It is also shown that all bounded languages generated by these two grammar systems (those in any semilinear trio) can be generated unambiguously within the systems. Finally, conditions on languages generated by finite-index matrix grammars and finite-index ETOL implying commutative regularity are obtained. In particular, it is shown that every finite-index EDOL language is commutatively regular.
