Detail publikace

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT Lucie a MEDUNA Alexander. A Reduction of Finitely Expandable Deep Pushdown Automata. In: Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017). Electronic Proceedings in Theoretical Computer Science. Telč, 2017, s. 1-1.
Název česky
Redukce konečně expandovatelných hlubokých zásobníkových automatů
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Abstrakt

Pro přirozené číslo n, n-expandovatelné hluboké zasobníkové automaty vždy obsahují maximálně n výskytů nevstupních symbolů v jejich zásobníku v průběhu jakékoli kompilace. Jako hlavní výsledek, tato práce demonstruje, že tyto automaty mají stejnou vyjadřovací sílu jako automaty s #, nacházející pouze na dně zásobníku, a jediným dalším nevstupním symbolem. Z tohoto závěru vyplývá nekonečná hierarchie jazyků přijímaných těmito automaty.

Rok
2017
Strany
1-1
Sborník
Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)
Řada
Electronic Proceedings in Theoretical Computer Science
Konference
MEMICS'17 - 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, CZ
Místo
Telč, CZ
BibTeX
@INPROCEEDINGS{FITPUB11521,
   author = "Lucie Charv\'{a}t and Alexander Meduna",
   title = "A Reduction of Finitely Expandable Deep Pushdown Automata",
   pages = "1--1",
   booktitle = "Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)",
   series = "Electronic Proceedings in Theoretical Computer Science",
   year = 2017,
   location = "Tel\v{c}, CZ",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11521"
}
Nahoru