Back to Search
Start Over
Decremental subset construction
- Source :
- Intelligent Decision Technologies 2017 ISBN: 9783319594200, KES-IDT (1)
- Publication Year :
- 2018
- Publisher :
- Springer Science and Business Media Deutschland GmbH, 2018.
-
Abstract
- Finite automata are exploited in several domains, including language processing, artificial intelligence, automatic control, and software engineering. Let \({\mathcal {N}}\) be a nondeterministic finite automaton (NFA) and \({\mathcal {D}}\) the deterministic finite automaton (DFA) equivalent to \({\mathcal {N}}\). Assume to decrement \({\mathcal {N}}\) by \(\varDelta {\mathcal {N}}\), thus obtaining the decremented NFA \({\mathcal {N}}' = {\mathcal {N}}\setminus \varDelta {\mathcal {N}}\), where some states and/or transitions are missing. Consider determinizing \({\mathcal {N}}'\). Instead of determinizing \({\mathcal {N}}'\) from scratch using the classical Subset Construction algorithm, we propose Decremental Subset Construction, an algorithm which generates the DFA \({\mathcal {D}}'\) equivalent to \({\mathcal {N}}'\) by updating \({\mathcal {D}}\) based on \({\mathcal {N}}\) and \(\varDelta {\mathcal {N}}\). This way, only the actions necessary to transform \({\mathcal {D}}\) into \({\mathcal {D}}'\) are applied. Although evidence from worst-case complexity analysis indicates that Decremental Subset Construction is not better than Subset Construction, in practice, when \({\mathcal {N}}\) is large and \(\varDelta {{\mathcal {N}}}\) relatively small, Decremental Subset Construction may outperform Subset Construction significantly.
- Subjects :
- Physics
Decision Sciences (all)
Computer Science (all)
Transition function
Powerset construction
020207 software engineering
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Combinatorics
Deterministic finite automaton
Regular language
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
Nondeterministic finite automaton
Computer Science::Formal Languages and Automata Theory
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-319-59420-0
- ISBNs :
- 9783319594200
- Database :
- OpenAIRE
- Journal :
- Intelligent Decision Technologies 2017 ISBN: 9783319594200, KES-IDT (1)
- Accession number :
- edsair.doi.dedup.....351a8137586a47ff25b96b4b65c17838