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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationProceedings 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
PublisherCEUR-WS.org
Pages47-57
Number of pages11
Volume1552
Publication statusPublished - 2015
Event1st 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 20155 Dec 2015

Workshop

Workshop1st Russian-South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30-December 5, 2015, Stellenbosch, South Africa
Abbreviated titleRuZA 2015
CountrySouth Africa
CityStellenbosch
Period30/11/155/12/15

Fingerprint

Finite automata
Testing

Keywords

  • Random Failure Deterministic Finite Automaton

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

}

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 proceedingConference contributionAcademicpeer-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 -

Nxumalo M, Kourie DG, Cleophas LGWA, Watson BW. 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. 2015. p. 47-57