Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Left is Better than Right for Reducing Nondeterminism of NFAs
verfasst von : Sang-Ki Ko, Yo-Sub Han
Erschienen in: Implementation and Application of Automata
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the NFA reductions by invariant equivalences. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences. We, in particular, show that the left-invariant equivalence is more useful than the right-invariant equivalence for reducing NFA nondeterminism. We also present experimental evidence for showing that NFA reduction by left-invariant equivalence achieves the better reduction of nondeterminism than right-invariant equivalence.