Detail publikačního výsledku

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

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

Originální název

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

Anglický název

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

Druh

Článek recenzovaný mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

pushdown automata, modifications, recursively enumerable languages

Klíčová slova v angličtině

pushdown automata, modifications, recursively enumerable languages

Autoři

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

Vydáno

21.03.2007

Místo

Praha

Kniha

Kybernetika

ISSN

0023-5954

Periodikum

KYBERNETIKA

Svazek

2007

Číslo

1

Stát

Česká republika

Strany od

21

Strany do

35

Strany počet

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