Conference paper

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. Braga: Springer Verlag, 2012, pp. 236-243. ISBN 978-3-642-31622-7. ISSN 0302-9743. Available from: http://www.springerlink.com/content/071345778vgw67tm/
Publication language:english
Original title:An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets
Title (cs):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
Pages:236-243
Proceedings:DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems
Conference:14th International Workshop on Descriptional Complexity of Formal Systems
Series:LNCS 7386
Place:Braga, PT
Year:2012
URL:http://www.springerlink.com/content/071345778vgw67tm/
ISBN:978-3-642-31622-7
Journal:Lecture Notes in Computer Science, Vol. 2012, No. 7386, DE
ISSN:0302-9743
Publisher:Springer Verlag
Keywords
stateless pushdown automata, limited pushdown alphabets, generative power, infinite hierarchy of language families
Annotation
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.
BibTeX:
@INPROCEEDINGS{
   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 = {LNCS 7386},
   journal = {Lecture Notes in Computer Science},
   volume = {2012},
   number = {7386},
   year = {2012},
   location = {Braga, PT},
   publisher = {Springer Verlag},
   ISBN = {978-3-642-31622-7},
   ISSN = {0302-9743},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9953}
}

Your IPv4 address: 54.145.85.87
Switch to IPv6 connection

DNSSEC [dnssec]