An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F12%3APU101767" target="_blank" >RIV/00216305:26230/12:PU101767 - isvavai.cz</a>
Result on the web
<a href="http://www.springerlink.com/content/071345778vgw67tm/" target="_blank" >http://www.springerlink.com/content/071345778vgw67tm/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-31623-4_18" target="_blank" >10.1007/978-3-642-31623-4_18</a>
Alternative languages
Result language
angličtina
Original language name
An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets
Original language description
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 whosesize 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems
ISBN
978-3-642-31622-7
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
236-243
Publisher name
Springer Verlag
Place of publication
Braga
Event location
Braga
Event date
Jul 23, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—