Detail výsledku

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT, L.; MEDUNA, A. A Reduction of Finitely Expandable Deep Pushdown Automata. Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017). Electronic Proceedings in Theoretical Computer Science. Telč: 2017. p. 1 (1 s.).
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Charvát Lucie, Ing., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the presentation demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols---$ and #, where # always appears solely as the pushdown bottom. Moreover, the presentation  demonstrates an infinite hierarchy of language families that follows from this main result. The presentation also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.

Klíčová slova

Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown Symbols

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
Místo
Telč
BibTeX
@inproceedings{BUT170110,
  author="Lucie {Charvát} and Alexandr {Meduna}",
  title="A Reduction of Finitely Expandable Deep Pushdown Automata",
  booktitle="Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)",
  year="2017",
  series="Electronic Proceedings in Theoretical Computer Science",
  pages="1--1",
  address="Telč",
  url="https://www.fit.vut.cz/research/publication/11521/"
}
Soubory
Projekty
Centrum kompetence ve zpracování vizuálních informací (V3C - Visual Computing Competence Center), TAČR, Centra kompetence, TE01020415, zahájení: 2012-05-01, ukončení: 2019-12-31, ukončen
Nástroje, metody a technologie ICT pro podporu konceptu smart cities, VUT, Vnitřní projekty VUT, FIT-S-17-3964, zahájení: 2017-03-01, ukončení: 2020-02-29, ukončen
Výzkumné skupiny
Pracoviště
Nahoru