Publication result detail

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

BIDLO, R.; BLATNÝ, P.; MEDUNA, A.

Original Title

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

English Title

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

Type

Peer-reviewed article not indexed in WoS or Scopus

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

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

Keywords

pushdown automata, modifications, recursively enumerable languages

Key words in English

pushdown automata, modifications, recursively enumerable languages

Authors

BIDLO, R.; BLATNÝ, P.; MEDUNA, A.

Released

21.03.2007

Location

Praha

Book

Kybernetika

ISBN

0023-5954

Periodical

KYBERNETIKA

Volume

2007

Number

1

State

Czech Republic

Pages from

21

Pages to

35

Pages count

14

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