@inproceedings{a8d95afcf09a42caa2e5afcf4f14a397,
title = "Left is better than right for reducing nondeterminism of NFAs",
abstract = "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.",
keywords = "Invariant equivalences, NFA reduction, Nondeterministic finite automata, Regular expression",
author = "Ko, {Sang Ki} and Han, {Yo Sub}",
year = "2014",
doi = "10.1007/978-3-319-08846-4_18",
language = "English",
isbn = "9783319088457",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "238--251",
booktitle = "Implementation and Application of Automata - 19th International Conference, CIAA 2014, Proceedings",
address = "Germany",
note = "19th International Conference on Implementation and Application of Automata, CIAA 2014 ; Conference date: 30-07-2014 Through 02-08-2014",
}