Height-Deterministic Pushdown Automata

• 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
• 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ů