Detail publikace

On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops

Originální název

On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops

Anglický název

On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops

Jazyk

en

Originální abstrakt

This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, the pushdown is completely emptied and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simple matrix grammars. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns.

Anglický abstrakt

This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, the pushdown is completely emptied and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simple matrix grammars. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns.

BibTex


@inproceedings{BUT27768,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops",
  annote="This paper introduces and discusses pure multi-pushdown automata that remove
symbols from their pushdowns only by performing complete-pushdown pops. During
this operation, the entire pushdown is compared with a prefix of the input, and
if they match, the pushdown is completely emptied and the input is advanced by
the prefix. The paper proves that these automata define an infinite hierarchy of
language families identical with the infinite hierarchy of language families
resulting from right linear simple matrix grammars. If these automata are allowed
to join their pushdowns and create new pushdowns, then they define another
infinite hierarchy of language families according to the number of pushdowns.",
  address="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  booktitle="Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings",
  chapter="27768",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  year="2008",
  month="may",
  pages="325--336",
  publisher="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  type="conference paper"
}