LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA

In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classic...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2014-09, Vol.25 (6), p.781-802
Main Authors: AIZIKOWITZ, TAMAR, KAMINSKI, MICHAEL
Format: Article
Language:English
Subjects:
Computation
Computer simulation
Equivalence
Foundations
Grammars
Mathematical models
Strengthening
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classical equivalence between one-turn pushdown automata and linear grammars, thus strengthening the claim of synchronized alternating pushdown automata as a natural counterpart of conjunctive grammars.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054114500336