Height-Deterministic Pushdown Automata

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Výškově-deterministické zásobníkové automaty
Autoři	NOWOTKA Dirk SRBA Jiří
Rok publikování	2007
Druh	Článek ve sborníku
Konference	32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	pushdown automata - visibly pushdown laguages - height determinism
Popis	Budeme definovat pojem výšky-deterministické zásobníkové automaty, model, kdy pro daný vstupní řetězec komína výšky při jakémkoli (nedeterministické), počítání na vstupu jsou předem stanoveny. Různé podtřídy výšky-deterministické zásobníkové automaty, přísně střežit třídy regulárních jazyků a stále zavřené pod jazyk boolean operace, jsou považovány. Některé z těchto jazykových kurzů byly popsány v literatuře. Zde doporučujeme přirozené a intuitivní model, který znamená také všechny formalismy dosud navržených zaměstnáváním výška-deterministické zásobníkové automaty. Rozhodnutelnost a složitosti otázky jsou rovněž považovány.
Související projekty:	Institut Teoretické Informatiky Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů