Detail publikace

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT Lucie a MEDUNA Alexander. A Reduction of Finitely Expandable Deep Pushdown Automata. Schedae Informaticae, roč. 2017, č. 26, 2018, s. 61-68. ISSN 0860-0295.
Název česky
Redukce konečně expandovatelných hlubokých zásobníkových automatů
Typ
článek v časopise
Jazyk
angličtina
Autoři
Charvát Lucie, Ing. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
URL
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
2018
Strany
61-68
Časopis
Schedae Informaticae, roč. 2017, č. 26, ISSN 0860-0295
DOI
10.4467/20838476SI.17.005.8151
EID Scopus
2-s2.0-85057858123
BibTeX 
@ARTICLE{FITPUB11519,
   author = "Lucie Charv\'{a}t and Alexander Meduna",
   title = "A Reduction of Finitely Expandable Deep Pushdown Automata",
   pages = "61--68",
   journal = "Schedae Informaticae",
   volume = 2017,
   number = 26,
   year = 2018,
   ISSN = "0860-0295",
   doi = "10.4467/20838476SI.17.005.8151",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11519"
}
Nahoru