Publication Details

Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets

BIDLO Radek, BLATNÝ Petr and MEDUNA Alexander. Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets. Kybernetika, vol. 2007, no. 1, pp. 21-35. ISSN 0023-5954.
Czech title
Automaty s oboustrannými zásobníky definovanými nad volnými grupami generovanými redukovanými abecedami
Type
journal article
Language
english
Authors
Bidlo Radek, Ing. (DIFS FIT BUT)
Blatný Petr, Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Keywords

pushdown automata, modifications, recursively enumerable languages

Abstract

This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by nomore than four symbols.

Published
2007
Pages
21-35
Journal
Kybernetika, vol. 2007, no. 1, ISSN 0023-5954
Book
Kybernetika
Place
Praha, CZ
BibTeX 
@ARTICLE{FITPUB8289,
   author = "Radek Bidlo and Petr Blatn\'{y} and Alexander Meduna",
   title = "Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets",
   pages = "21--35",
   booktitle = "Kybernetika",
   journal = "Kybernetika",
   volume = 2007,
   number = 1,
   year = 2007,
   location = "Praha, CZ",
   ISSN = "0023-5954",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8289"
}
Back to top