Deep pushdown automata
Deep pushdown automata
复制标题
深下推自动机
DOI：
10.1007/s00236-006-0005-0
复制
发表时间：
2006
期刊：
影响因子：
0.6
通讯作者：
A. Meduna
中科院分区：
文献类型：
--
作者：
A. Meduna
本文介绍和讨论了作为经典下推自动机的推广的深度下推自动机。这种泛化包括允许它们在下推中进行更深的扩展。基于扩展深度，本文建立了一个与有限状态文法的层次结构相一致的语言族的无限层次结构，因此深度下推自动机实际上代表了这些文法的自动机对应物。在结论中，本文提出了一些开放的问题领域。
This paper introduces and discussesdeep pushdown automataas a generalization of the classical pushdown automata. This generalization consists in allowing them to make expansions deeper in the pushdown. Based on the expansion depth, the present paper establishes an infinite hierarchy of language families that coincides with the hierarchy resulting from then-limited state grammars, so the deep pushdown automata actually represent the automaton counterpart to these grammars. In its conclusion, this paper suggests some open problem areas.