Left is Better Than Right for Reducing Nondeterminism of NFAs

Sang Ki Ko, Yo Sub Han

Research output: Contribution to journalArticlepeer-review


We study the NFA reductions by invariant equivalences and preorders. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been many approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence or preorder relation and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences and preorders. We, in particular, show that computing equivalence and preorder relation from the left is more useful than the right for reducing the degree of nondeterminism in NFAs. We also present experimental evidence for showing that NFA reduction from the left achieves the better reduction of nondeterminism than reduction from the right.

Original languageEnglish
Article number2141006
Pages (from-to)531-550
Number of pages20
JournalInternational Journal of Foundations of Computer Science
Issue number5
Publication statusPublished - 2021 Aug

Bibliographical note

Funding Information:
This research was supported by the NRF grant funded by MIST (NRF-2020R1A4A3079947).

Publisher Copyright:
© 2021 World Scientific Publishing Co. Pte Ltd. All rights reserved.

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


Dive into the research topics of 'Left is Better Than Right for Reducing Nondeterminism of NFAs'. Together they form a unique fingerprint.

Cite this