Detail výsledku

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

MASOPUST, T.; MEDUNA, A. On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops. Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings. Balatonfured: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2008. p. 325-336. ISBN: 978-963-311-367-7.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
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.

Klíčová slova

pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy

Rok
2008
Strany
325–336
Sborník
Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings
Konference
The 12th International Conference on Automata and Formal Languages
ISBN
978-963-311-367-7
Vydavatel
Computer and Automation Research Institute, Hungarian Academy of Sciences
Místo
Balatonfured
BibTeX 
@inproceedings{BUT27768,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops",
  booktitle="Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings",
  year="2008",
  pages="325--336",
  publisher="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  address="Balatonfured",
  isbn="978-963-311-367-7"
}
Projekty
Multiinformační technologie, GAČR, Standardní projekty, GA201/07/0005, zahájení: 2007-01-01, ukončení: 2009-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru