J 2007

Remarks on multiple entry deterministic finite automata

POLÁK, Libor

Základní údaje

Originální název

Remarks on multiple entry deterministic finite automata

Název česky

Poznámky o deterministických konečných automatech s více vstupy

Autoři

POLÁK, Libor

Vydání

Journal of Automata, Languages and Combinatorics, Magdeburg (Germany), 2007, 1430-189X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10000 1. Natural Sciences

Stát vydavatele

Německo

Utajení

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

Organizační jednotka

Přírodovědecká fakulta

Klíčová slova anglicky

multiple entry DFA; minimalization; conversion; decomposition

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 17. 7. 2008 19:45, doc. RNDr. Libor Polák, CSc.

Anotace

V originále

We investigate several aspects of the multiple entry DFA's. We consider their DFA conversion. Further, we show that they appear as minimal NFA's for certain classes of languages. Finally, we deal with their decompositions into disjoint unions of automata with less number of states.

Česky

Zabýváme se několika aspekty deterministických konečných automatů s více vstupy. Uvažujeme konverzi na deteministické konečné automaty. Dále ukazujeme, že se vyskytují jako minimální nedeterministické automaty pro jisté třídy jazyků. Konečně pojednáváme o jejich rozkladech na disjunktní sjednocení automatů s menším počtem stavů.

Návaznosti

1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky