Detail publikace

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.
Název česky
Automaty s oboustrannými zásobníky definovanými nad volnými grupami generovanými redukovanými abecedami
Typ
článek v časopise
Jazyk
anglicky
Autoři
Bidlo Radek, Ing., Ph.D.
Blatný Petr, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Klíčová slova

zásobníkové automaty, modifikace, rekurzívně vyčíslitelné jazyky

Abstrakt

Článek představuje a diskutuje modifikaci zásobníkových automatů. Tato modifikace je založena na oboustranných zásobnících, do kterých jsou symboly vkládány z obou stran. Tyto zásobníky nejsou definovány nad volnými monoidy, ale nad volnými grupami a mohou být zkráceny pouze standardní grupovou redukcí. Je demonstrováno, že tyto automaty charakterizují třídu rekurzívně vyčíslitelných jazyků i když jsou volné grupy generovány ne více než čtyřmi symboly.

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