Publication Details

Prefix Pushdown Automata

MEDUNA Alexander. Prefix Pushdown Automata. International Journal of Computer Mathematics, vol. 1999, no. 71, pp. 1-20. ISSN 0020-7160.

Czech title

Prefixové zásobníkové automaty

Type

journal article

Language

english

Authors

Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)

Keywords

prefix pushdown automata, pushdown, recursively enumerable languages

Abstract

The present paper demonstrates this result for some simplified versions of prefix pushdown automata. Finally, it discusses the descriptional complexity of these automata.

Annotation

A prefix pushdown automaton, M, accepts a word, x, with respect to a language, Z, if and only if M makes a sequence of moves so it reads xy, for some y \in Z, and enters a final state. This paper demonstrates that for every recursively enumerable language, L, there exist a linear language, Z, and a prefix pushdown automaton, M, so that L equals the prefix language that M accepts with respect to Z. Besides the acceptance by final state, this result is established in terms of acceptance by empty pushdown and acceptance by final state and empty pushdown. In addition, the present paper demonstrates this result for some simplified versions of prefix pushdown automata. Finally, it discusses the descriptional complexity of these automata.

Published

1999

Pages

1-20

Journal

International Journal of Computer Mathematics, vol. 1999, no. 71, ISSN 0020-7160

Book

International Journal of Computer Mathematics

Place

London, GB

BibTeX

@ARTICLE{FITPUB6179,
   author = "Alexander Meduna",
   title = "Prefix Pushdown Automata",
   pages = "1--20",
   booktitle = "International Journal of Computer Mathematics",
   journal = "International Journal of Computer Mathematics",
   volume = 1999,
   number = 71,
   year = 1999,
   location = "London, GB",
   ISSN = "0020-7160",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6179"
}