zbMATH — the first resource for mathematics

Efficient recognition of completeness of systems of automaton functions with complete Boolean part. (English. Russian original) Zbl 1088.68630
Discrete Math. Appl. 13, No. 1, 63-84 (2003); translation from Diskretn. Mat. 15, No. 1, 110-131 (2003).
Summary: We consider automaton bases with complete Boolean part. We construct an algorithm to test completeness of such bases and give upper bounds for its complexity.

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
06E30 Boolean functions
03D05 Automata and formal grammars in connection with logical questions
Full Text: DOI
[1] Dokl. Acad. Sci. USSR 151 pp 493– (1963)
[2] Soviet Math. Dokl. 5 pp 338– (1964)
[3] Comput. Math. Math. Phys. 3 pp 829– (1963)
[4] Babin A, Diskretnaya Matematika 4 (4) pp 41– (1992)
[5] Discrete Math. Appl. 6 pp 491– (1996)
[6] Intellectual Systems 3 pp 51– (1998)
[7] Discrete Math. Appl. 8 pp 475– (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.