Detail publikace

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

Originální název

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

Anglický název

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

Jazyk

en

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.

Anglický 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.

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",
  annote="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.",
  address="Springer Verlag",
  booktitle="DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems",
  chapter="96942",
  doi="10.1007/978-3-642-31623-4_18",
  edition="Lecture Notes in Computer Science",
  howpublished="print",
  institution="Springer Verlag",
  year="2012",
  month="july",
  pages="236--243",
  publisher="Springer Verlag",
  type="conference paper"
}