Left is Better Than Right for Reducing Nondeterminism of NFAs.
Saved in:
| Title: | Left is Better Than Right for Reducing Nondeterminism of NFAs. |
|---|---|
| Authors: | Ko, Sang-Ki1 (AUTHOR) sangkiko@kangwon.ac.kr, Han, Yo-Sub2 (AUTHOR) emmous@yonsei.ac.kr |
| Source: | International Journal of Foundations of Computer Science. Aug2021, Vol. 32 Issue 5, p531-550. 20p. |
| Subjects: | Polynomial time algorithms, Finite state machines, Equivalence classes (Set theory) |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 151853249 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Left is Better Than Right for Reducing Nondeterminism of NFAs. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Ko%2C+Sang-Ki%22">Ko, Sang-Ki</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> sangkiko@kangwon.ac.kr</i><br /><searchLink fieldCode="AR" term="%22Han%2C+Yo-Sub%22">Han, Yo-Sub</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> emmous@yonsei.ac.kr</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Foundations+of+Computer+Science%22">International Journal of Foundations of Computer Science</searchLink>. Aug2021, Vol. 32 Issue 5, p531-550. 20p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Finite+state+machines%22">Finite state machines</searchLink><br /><searchLink fieldCode="DE" term="%22Equivalence+classes+%28Set+theory%29%22">Equivalence classes (Set theory)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=151853249 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1142/S0129054121410069 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 20 StartPage: 531 Subjects: – SubjectFull: Polynomial time algorithms Type: general – SubjectFull: Finite state machines Type: general – SubjectFull: Equivalence classes (Set theory) Type: general Titles: – TitleFull: Left is Better Than Right for Reducing Nondeterminism of NFAs. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Ko, Sang-Ki – PersonEntity: Name: NameFull: Han, Yo-Sub IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Text: Aug2021 Type: published Y: 2021 Identifiers: – Type: issn-print Value: 01290541 Numbering: – Type: volume Value: 32 – Type: issue Value: 5 Titles: – TitleFull: International Journal of Foundations of Computer Science Type: main |
| ResultId | 1 |
