Abstract
An algorithm is proposed that constructs a failure deterministic finite automaton in lockstep with the construction of a languageequivalent deterministic finite automaton. The states of both automata are assumed to be predefined and the failure deterministic finite automaton's symbol and failure transitions are randomised. It is guaranteed that the latter remains free of divergent failure cycles. The benefits are explained of using this algorithm to produce input data for testing algorithms that produce a language-equivalent FDFA from an arbitrary DFA.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30 - December 5, 2015, Stellenbosch, South Africa |
| Publisher | CEUR-WS.org |
| Pages | 47-57 |
| Number of pages | 11 |
| Volume | 1552 |
| Publication status | Published - 2015 |
| Event | 1st Russian-South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30-December 5, 2015, Stellenbosch, South Africa - Stellenbosch, South Africa Duration: 30 Nov 2015 → 5 Dec 2015 |
Workshop
| Workshop | 1st Russian-South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30-December 5, 2015, Stellenbosch, South Africa |
|---|---|
| Abbreviated title | RuZA 2015 |
| Country | South Africa |
| City | Stellenbosch |
| Period | 30/11/15 → 5/12/15 |
Fingerprint
Keywords
- Random Failure Deterministic Finite Automaton
Cite this
}
On generating a random deterministic finite automaton as well as its failure equivalent. / Nxumalo, M.; Kourie, D.G.; Cleophas, L.G.W.A.; Watson, B.W.
Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30 - December 5, 2015, Stellenbosch, South Africa. Vol. 1552 CEUR-WS.org, 2015. p. 47-57.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - On generating a random deterministic finite automaton as well as its failure equivalent
AU - Nxumalo, M.
AU - Kourie, D.G.
AU - Cleophas, L.G.W.A.
AU - Watson, B.W.
PY - 2015
Y1 - 2015
N2 - An algorithm is proposed that constructs a failure deterministic finite automaton in lockstep with the construction of a languageequivalent deterministic finite automaton. The states of both automata are assumed to be predefined and the failure deterministic finite automaton's symbol and failure transitions are randomised. It is guaranteed that the latter remains free of divergent failure cycles. The benefits are explained of using this algorithm to produce input data for testing algorithms that produce a language-equivalent FDFA from an arbitrary DFA.
AB - An algorithm is proposed that constructs a failure deterministic finite automaton in lockstep with the construction of a languageequivalent deterministic finite automaton. The states of both automata are assumed to be predefined and the failure deterministic finite automaton's symbol and failure transitions are randomised. It is guaranteed that the latter remains free of divergent failure cycles. The benefits are explained of using this algorithm to produce input data for testing algorithms that produce a language-equivalent FDFA from an arbitrary DFA.
KW - Random Failure Deterministic Finite Automaton
UR - http://www.scopus.com/inward/record.url?scp=84964066482&partnerID=8YFLogxK
UR - http://ceur-ws.org/
M3 - Conference contribution
AN - SCOPUS:84964066482
VL - 1552
SP - 47
EP - 57
BT - Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30 - December 5, 2015, Stellenbosch, South Africa
PB - CEUR-WS.org
ER -