Detail výsledku

An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets

MEDUNA, A.; VRÁBEL, L.; ZEMEK, P. An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets. DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science. Lecture Notes in Computer Science. Braga: Springer Verlag, 2012. p. 236-243. ISBN: 978-3-642-31622-7. ISSN: 0302-9743.
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Vrábel Lukáš, Ing., FIT (FIT), UIFS (FIT)
Zemek Petr, Ing., Ph.D., FIT (FIT), UIFS (FIT)
Abstrakt

As its name suggests, a stateless pushdown automaton has no states. As a result, each of its computational steps depends only on the currently scanned symbol and the current pushdown-store top. In this paper, we consider stateless pushdown automata whose size of their pushdown alphabet is limited by a positive integer. More specifically, we establish an infinite hierarchy of language families resulting from stateless pushdown automata with limited pushdown alphabets. In addition, we prove analogous results for stateless deterministic pushdown automata and stateless real-time pushdown automata. A formulation of an open problem closes the paper.

Klíčová slova


stateless pushdown automata, limited pushdown alphabets, generative power, infinite hierarchy of language families

URL
Rok
2012
Strany
236–243
Časopis
Lecture Notes in Computer Science, roč. 7386, ISSN 0302-9743
Sborník
DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems
Řada
Lecture Notes in Computer Science
Konference
14th International Workshop on Descriptional Complexity of Formal Systems
ISBN
978-3-642-31622-7
Vydavatel
Springer Verlag
Místo
Braga
DOI
10.1007/978-3-642-31623-4_18
BibTeX 
@inproceedings{BUT96942,
  author="Alexandr {Meduna} and Lukáš {Vrábel} and Petr {Zemek}",
  title="An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets",
  booktitle="DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems",
  year="2012",
  series="Lecture Notes in Computer Science",
  journal="Lecture Notes in Computer Science",
  volume="7386",
  pages="236--243",
  publisher="Springer Verlag",
  address="Braga",
  doi="10.1007/978-3-642-31623-4\{_}18",
  isbn="978-3-642-31622-7",
  issn="0302-9743",
  url="http://www.springerlink.com/content/071345778vgw67tm/"
}
Projekty
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, zahájení: 2011-01-01, ukončení: 2015-12-31, ukončen
Matematické základy teorie formálních jazyků, MŠMT, Fond rozvoje vysokých škol (FRVŠ), FR271/2012/G1, zahájení: 2012-01-01, ukončení: 2012-12-31, ukončen
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru