D 2011

On Biautomata

KLÍMA, Ondřej a Libor POLÁK

Základní údaje

Originální název

On Biautomata

Autoři

KLÍMA, Ondřej a Libor POLÁK

Vydání

Non-Classical Models for Automata and Applications, od s. 153-164, 12 s. 2011

Nakladatel

Austrian Computer Society

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Rakousko

Utajení

není předmětem státního či obchodního tajemství

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-3-85403-282-3

UT WoS

000310757900007

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 21. 11. 2011 16:38, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

V originále

We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language L its canonical biautomaton. This structure plays, among all biautomata recognizing the language L, the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language L. We expect that from the graph structure of this automaton one could decide the membership of a given language to certain signicant classes of languages. We present the rst result of this kind: a language L is piecewise testable if and only if the canonical biautomaton of L is acyclic. From this result the famous Simon's characterization of piecewise testable languages easily follows.

Návaznosti

GA201/09/1313, projekt VaV
Název: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků II
MSM0021622409, záměr
Název: Matematické struktury a jejich fyzikální aplikace
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky