Detail publikace

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

MEDUNA, A. VRÁBEL, L. ZEMEK, P.

Originální název

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

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

angličtina

Originální 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

Autoři

MEDUNA, A.; VRÁBEL, L.; ZEMEK, P.

Rok RIV

2012

Vydáno

23. 7. 2012

Nakladatel

Springer Verlag

Místo

Braga

ISBN

978-3-642-31622-7

Kniha

DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems

Edice

Lecture Notes in Computer Science

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Ročník

7386

Stát

Spolková republika Německo

Strany od

236

Strany do

243

Strany počet

8

URL

http://www.springerlink.com/content/071345778vgw67tm/

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/"
}