Publication Details

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

MEDUNA Alexander, VRÁBEL Lukáš and ZEMEK Petr. An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets. In: DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science, vol. 7386. Braga: Springer Verlag, 2012, pp. 236-243. ISBN 978-3-642-31622-7. ISSN 0302-9743. Available from: http://www.springerlink.com/content/071345778vgw67tm/
Czech title
Nekonečná hierarchie jazykových tříd vyplývající z bezstavových zásobníkových automatů s omezenými zásobníkovými abecedami
Type
conference paper
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Vrábel Lukáš, Ing. (DIFS FIT BUT)
Zemek Petr, Ing. (DIFS FIT BUT)
URL
Keywords


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

Abstract

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.

Published
2012
Pages
236-243
Journal
Lecture Notes in Computer Science, vol. 7386, ISSN 0302-9743
Proceedings
DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems
Series
Lecture Notes in Computer Science
Conference
14th International Workshop on Descriptional Complexity of Formal Systems, Braga, PT
ISBN
978-3-642-31622-7
Publisher
Springer Verlag
Place
Braga, PT
DOI
10.1007/978-3-642-31623-4_18
BibTeX 
@INPROCEEDINGS{FITPUB9953,
   author = "Alexander Meduna and Luk\'{a}\v{s} Vr\'{a}bel and Petr Zemek",
   title = "An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets",
   pages = "236--243",
   booktitle = "DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems",
   series = "Lecture Notes in Computer Science",
   journal = "Lecture Notes in Computer Science",
   volume = 7386,
   year = 2012,
   location = "Braga, PT",
   publisher = "Springer Verlag",
   ISBN = "978-3-642-31622-7",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-642-31623-4\_18",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9953"
}
Back to top