论文标题
关于包含反机器语言的完整三重奏家族
On Families of Full Trios Containing Counter Machine Languages
论文作者
论文摘要
我们查看不确定的有限自动机，并通过多个相反的计数器增强，在接受计算过程中，计数器的行为由某些固定模式指定。这些模式可以作为理论计算机科学文献中其他重要自动机和语法模型的有用“桥梁”，从而在他们的研究中有所帮助。考虑各种模式行为，以及特征和比较。例如，这样的模式完全定义了包含所有有界半线性语言的最小完整三人组。另一种模式定义了包含所有无上下文语言的最小完整三人组。然后将“桥接”与其他家庭进行应用，例如到某些图灵机限制以及其他家庭。还使用此框架研究了某些一般的可确定性属性。
We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by some fixed pattern. These patterns can serve as a useful "bridge" to other important automata and grammar models in the theoretical computer science literature, thereby helping in their study. Various pattern behaviors are considered, together with characterizations and comparisons. For example, one such pattern defines exactly the smallest full trio containing all the bounded semilinear languages. Another pattern defines the smallest full trio containing all the bounded context-free languages. The "bridging" to other families is then applied, e.g. to certain Turing machine restrictions, as well as other families. Certain general decidability properties are also studied using this framework.
