Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Bidlo Radek, Ing., Ph.D., UIFS (FIT)
Blatný Petr, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
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

Rok
2007
Strany
21–35
Časopis
KYBERNETIKA, roč. 2007, č. 1, ISSN 0023-5954
Kniha
Kybernetika
Místo
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"
}
Projekty
Optimally Integrated Models of Modern Information Technologies, GAČR, Standardní projekty, GA201/04/0441, zahájení: 2004-01-01, ukončení: 2006-12-31, ukončen
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru