Back to Search
Start Over
Online Determinization of Large Mutating Automata
- Source :
- KES
- Publication Year :
- 2018
- Publisher :
- Elsevier BV, 2018.
-
Abstract
- A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) which changes its morphology over discrete time by a sequence of mutations, one mutation at each time instant. A mutation involves the insertion and/or removal of a set of states and/or transitions. This results in a sequence of NFAs, one mutated NFA for each mutation. Some application domains, including model-based diagnosis and monitoring of active systems in artificial intelligence and model-based testing in software engineering, require online determinization of MFAs. Determinizing an MFA online means generating a deterministic finite automaton (DFA) as soon as a mutation occurs, which is equivalent to the mutated NFA. Since the classical Subset Construction determinization algorithm may be inadequate for MFAs, a conservative algorithm is proposed, called Subset Restructuring, that generates the new DFA by restructuring the previous DFA based on the mutation occurred, instead of building it from scratch. Experimental results indicate the effectiveness of the approach, especially so when large MFAs change in time by small mutations.
- Subjects :
- Determinization
Sequence
Theoretical computer science
Finite-state machine
Computer science
Powerset construction
020207 software engineering
Mutating automata
02 engineering and technology
Intelligent monitoring
Automaton
Set (abstract data type)
Model-based reasoning
Deterministic finite automaton
Discrete-event systems
Finite automata, Determinization, Mutating automata, Model-based reasoning, Discrete-event systems, Intelligent monitoring
Mutation (genetic algorithm)
0202 electrical engineering, electronic engineering, information engineering
General Earth and Planetary Sciences
020201 artificial intelligence & image processing
Nondeterministic finite automaton
Finite automata
General Environmental Science
Subjects
Details
- ISSN :
- 18770509
- Volume :
- 126
- Database :
- OpenAIRE
- Journal :
- Procedia Computer Science
- Accession number :
- edsair.doi.dedup.....6d9127f6f4e48869417d9eb208c76c30