Publication Details

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

BIDLO, R.; BLATNÝ, P.; MEDUNA, A. Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets. Kybernetika, 2007, vol. 2007, no. 1, p. 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., Ph.D.
Blatný Petr, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)

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

BibTeX

@article{BUT45154,
  author="Radek {Bidlo} and Petr {Blatný} and Alexandr {Meduna}",
  title="Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets",
  journal="Kybernetika",
  year="2007",
  volume="2007",
  number="1",
  pages="21--35",
  issn="0023-5954"
}