Minimalization of NFA using the universal automaton

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.

Název česky	Minimalizace NFA užitím univerzálního automatu
Autoři	POLÁK Libor
Rok publikování	2004
Druh	Článek ve sborníku
Konference	Descriptional Complexity of Formal Systems
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
Obor	Informatika
Klíčová slova	minimalization of NFA; universal automaton
Popis	Je dobře známo, že každý minimální NFA pro regulární jazyk L je izomorfní podautomatu tzv. univerzálního automatu U pro L. Zkoumáme a porovnáváme rozličné podmínky na množiny stavů automatu U, které jsou příbuzné faktu, že indukovaný automat v U přijímá celý jazyk L. Metody několika předchozích prací o minimalizaci NFA mohou být modifikovány tak, aby zapadly do našeho přístupu. Rovněž navrhujeme snadno implementovatelný algoritmus.
Související projekty:	Matematické struktury algebry a geometrie