2012
Descriptional Complexity of Biautomata
JIRÁSKOVÁ, Galina a Ondřej KLÍMAZákladní údaje
Originální název
Descriptional Complexity of Biautomata
Název česky
Deskriptivní složitost biautomatů
Autoři
JIRÁSKOVÁ, Galina (203 Česká republika) a Ondřej KLÍMA (203 Česká republika, garant, domácí)
Vydání
Berlin Heidelberg, Descriptional Complexity of Formal Systems, od s. 196-208, 13 s. 2012
Nakladatel
Springer-Verlag Berlin Heidelberg
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Švýcarsko
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14310/12:00057568
Organizační jednotka
Přírodovědecká fakulta
ISBN
978-3-642-31622-7
ISSN
UT WoS
000440496400015
EID Scopus
2-s2.0-84864829911
Klíčová slova anglicky
biautomata; descriptional complexity; minimal automaton
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 10. 7. 2020 10:23, Mgr. Marie Novosadová Šípková, DiS.
Anotace
V originále
A biautomaton is a finite automaton which arbitrarily alternates between reading the input word from the left and from the right. Some compatibility assumptions in the formal definition of a biautomaton ensure that the acceptance of an input does not depend on the way how the input is read. The paper studies the constructions of biautomata from the descriptional point of view. It proves the tight bounds on the size of a biautomaton recognizing a regular language represented by a deterministic or nondeterministic automaton.
Návaznosti
| GBP202/12/G061, projekt VaV |
|