Detail publikace

Absolutely Unlimited Deep Pushdown Automata

KUČERA Jiří, MEDUNA Alexander a SOUKUP Ondřej. Absolutely Unlimited Deep Pushdown Automata. In: Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015). Telč: Ing. Vladislav Pokorný - Litera, 2015, s. 36-44. ISBN 978-80-214-5254-1.
Název česky
Absolutně neomezené hluboké zásobníkové automaty
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Kučera Jiří, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Soukup Ondřej, Ing. (UIFS FIT VUT)
Klíčová slova

hluboké zásobníkové automaty, neomezené hluboké zásobníkové automaty, výpočetní síla, absolutně neomezená hloubka expanzí

Abstrakt

Tento článek zavádí absolutně neomezené hluboké zásobníkové automaty a studuje jejich výpočetní sílu. Tyto automaty jsou zobecněnými verzemi nedávno zavedených hlubokých zásobníkových automatů ve smyslu hloubky expanze - symboly lze na zásobníku expandovat v libovolné hloubce. Je ukázáno, že nezkracující a zkracující verze absolutně neomezených hlubokých zásobníkových automatů charakterizují jazyky typu 1 a jazyky typu 0, v tomto pořadí.

Rok
2015
Strany
36-44
Sborník
Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015)
Konference
MEMICS'15 - 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, CZ
ISBN
978-80-214-5254-1
Vydavatel
Ing. Vladislav Pokorný - Litera
Místo
Telč, CZ
BibTeX 
@INPROCEEDINGS{FITPUB10978,
   author = "Ji\v{r}\'{i} Ku\v{c}era and Alexander Meduna and Ond\v{r}ej Soukup",
   title = "Absolutely Unlimited Deep Pushdown Automata",
   pages = "36--44",
   booktitle = "Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2015)",
   year = 2015,
   location = "Tel\v{c}, CZ",
   publisher = "Ing. Vladislav Pokorn\'{y} - Litera",
   ISBN = "978-80-214-5254-1",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10978"
}
Nahoru