Descriptional Complexity of Biautomata

Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Deskriptivní složitost biautomatů
Autoři

JIRÁSKOVÁ Galina KLÍMA Ondřej

Rok publikování 2012
Druh Článek ve sborníku
Konference Descriptional Complexity of Formal Systems
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Doi http://dx.doi.org/10.1007/978-3-642-31623-4_15
Obor Obecná matematika
Klíčová slova biautomata; descriptional complexity; minimal automaton
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info