Publication detail

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

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

Original Title

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

Type

article in a collection out of WoS and Scopus

Language

English

Original 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.

Keywords

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

Authors

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

RIV year

2012

Released

23. 7. 2012

Publisher

Springer Verlag

Location

Braga

ISBN

978-3-642-31622-7

Book

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

Edition

Lecture Notes in Computer Science

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Year of study

7386

State

Federal Republic of Germany

Pages from

236

Pages to

243

Pages count

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