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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Titel	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
Uitgeverij	CEUR-WS.org
Pagina's	47-57
Aantal pagina's	11
Volume	1552
Status	Gepubliceerd - 2015
Evenement	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, Zuid-Afrika Duur: 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
Verkorte titel	RuZA 2015
Land/Regio	Zuid-Afrika
Stad	Stellenbosch
Periode	30/11/15 → 5/12/15

Andere bestanden en links

Citeer dit

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, blz. 47-57). CEUR-WS.org.

Nxumalo, M. ; Kourie, D.G. ; Cleophas, L.G.W.A. et al. / 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. blz. 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, blz. 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, Zuid-Afrika, 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. et al.
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. blz. 47-57.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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 -

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. blz. 47-57

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

Samenvatting

Workshop

Andere bestanden en links

Vingerafdruk

Citeer dit