LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

详细信息    查看全文

• 作者：Tamar Aizikowitz ; Michael Kaminski ; ^{kaminski@cs.technion.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Conjunctive grammars ; Synchronized alternating pushdown automata ; LR(0)LR(0) conjunctive grammars ; Deterministic synchronized alternating pushdown automata
• 刊名：Journal of Computer and System Sciences
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：82
• 期：8
• 页码：1329-1359
• 全文大小：895 K

文摘

The paper introduces a subfamily of synchronized alternating pushdown automata, deterministic synchronized alternating pushdown automata  , and a subfamily of conjunctive grammars, LR(0)$LR(0)$conjunctive grammars  . It is shown that deterministic synchronized alternating pushdown automata and LR(0)$LR(0)$ conjunctive grammars have the same recognition/generation power, analogously to the classical equivalence between acceptance by empty stack of deterministic pushdown automata and LR(0)$LR(0)$ grammars. These models form the theoretical basis for efficient linear time parsing of a subfamily of conjunctive languages which properly   includes the classical LR(0)$LR(0)$ languages.