Some more algorithms for Conway’s universal automaton

Boris Melnikov; Vasily Dolgov

doi:10.2478/ausi-2014-0015

.blurhash-client-img { display: none !important; }

Some more algorithms for Conway’s universal automaton

Acta Universitatis Sapientiae, Informatica

Volume 6 (2014): Issue 1 (June 2014)

By: Boris Melnikov and Vasily Dolgov

Open Access

|Jun 2014

Abstract

In this paper authors propose algorithms for constructing so called automaton COM(L) and prove that this automaton coincides, up to re-denoting states, with Conway’s universal automaton. We give some algorithms of constructing this automaton and consider some examples.

References

[1] A.Aho, J.Ullman, The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing. Prentice Hall, 1972. ⇒8
Search in Google Scholar
[2] R.Dedekind, Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler. Gesammelte Werke, Vol. 2, 103-148. ⇒18
Search in Google Scholar
[3] T.Kameda, P.Weiner, On the state minimization of nondeterministic finite automata, IEEE Trans. on Comp. C-19, 7 (1970) 617-627. ⇒2010.1109/T-C.1970.222994
Search in Google Scholar
[4] S. Lombardy, J. Sakarovitch, The Universal Automaton, in: Logic and Automata, Texts in Logic and Games Amsterdam Univ. Press. Vol. 2 (2008) 457-504. ⇒ 5, 7, 18
Search in Google Scholar
[5] B.Melnikov, Extended nondeterministic finite automata, Fundamenta Informaticae 104, 3 (2010) 255-265. ⇒5, 610.3233/FI-2010-348
Search in Google Scholar
[6] B.Melnikov, Once more on the edge-minimization of nondeterministic finite automata and the connected problems, Fundamenta Informaticae 104, 3 (2010) 267-283. ⇒5, 6, 9, 10, 13, 1410.3233/FI-2010-349
Search in Google Scholar
[7] B.Melnikov, A. Melnikova, Some more on the basis finite automaton, Acta Univ. Sapientiae, Inform. 5, 2 (2013) 227-244 ⇒1910.2478/ausi-2014-0012
Search in Google Scholar
[8] B.Melnikov, N. Sciarini-Guryanova, Possible edges of a finite automaton defining a given regular language, The Korean Journal of Computational and Applied Mathematics 9, 2 (2002) 475-485. ⇒510.1007/BF03021555
Search in Google Scholar

DOI: https://doi.org/10.2478/ausi-2014-0015 | Journal eISSN: 2066-7760

Journal RSS Feed

Language: English

Page range: 5 - 20

Submitted on: Jun 9, 2013

Published on: Jun 27, 2014

Published by: Sapientia Hungarian University of Transylvania

In partnership with: Paradigm Publishing Services

Publication frequency: 2 issues per year

Keywords:

nondeterministic finite automata,

Conway’s universal automaton,

constructing algorithms

Related subjects:

Computer sciences,

Computer sciences, other

© 2014 Boris Melnikov, Vasily Dolgov, published by Sapientia Hungarian University of Transylvania
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 6 (2014): Issue 1 (June 2014)Next article