On generating a random deterministic finite automaton as well as its failure equivalent

M. Nxumalo; D.G. Kourie; L.G.W.A. Cleophas; B.W. Watson

On generating a random deterministic finite automaton as well as its failure equivalent

M. Nxumalo, D.G. Kourie, L.G.W.A. Cleophas, B.W. Watson

Model Driven Software Engineering W&I

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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

Keywords

Random Failure Deterministic Finite Automaton

Access to Document

Fingerprint Dive into the research topics of 'On generating a random deterministic finite automaton as well as its failure equivalent'. Together they form a unique fingerprint.

Cite this

Nxumalo, M., Kourie, D. G., Cleophas, L. G. W. A., & Watson, B. W. (2015). On generating a random deterministic finite automaton as well as its failure equivalent. In 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, pp. 47-57). CEUR-WS.org.

Nxumalo, M. ; Kourie, D.G. ; Cleophas, L.G.W.A. ; Watson, B.W. / On generating a random deterministic finite automaton as well as its failure equivalent. 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. pp. 47-57

@inproceedings{1497ba987ceb466384a7c17beb0a6cf3,

title = "On generating a random deterministic finite automaton as well as its failure equivalent",

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.",

keywords = "Random Failure Deterministic Finite Automaton",

author = "M. Nxumalo and D.G. Kourie and L.G.W.A. Cleophas and B.W. Watson",

year = "2015",

language = "English",

volume = "1552",

pages = "47--57",

booktitle = "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",

note = "1st Russian-South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30-December 5, 2015, Stellenbosch, South Africa, RuZA 2015 ; Conference date: 30-11-2015 Through 05-12-2015",

}

Nxumalo, M, Kourie, DG, Cleophas, LGWA & Watson, BW 2015, On generating a random deterministic finite automaton as well as its failure equivalent. in 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, pp. 47-57, 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, 30/11/15.

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

T2 - 1st Russian-South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30-December 5, 2015, Stellenbosch, South Africa

Y2 - 30 November 2015 through 5 December 2015

ER -