On the classification of Post automaton bases according to the decidability of the completeness and A-completeness problems

zbMATH0958.03026MaRDI QIDQ1594479FDOQ1594479

Authors Dmitriĭ Nikolaevich Babin

Publication date 28 January 2001

Published in Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

automaton functionsdecidable completeness problemPost class

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Recommendations

• On the classification of Post automaton bases by the decidability of the \(A\)-completeness property for definite automata
• Finiteness of the set of automaton Post bases with solvable completeness problem
• On the classification of bases in \(P_k\) according to the decidability of the completeness problem for automata
• scientific article; zbMATH DE number 2032360
• On decidability of the completeness problem for special systems of automaton functions

Cited in

(7)

• On the classification of Post automaton bases by the decidability of the \(A\)-completeness property for definite automata
• Finiteness of the set of automaton Post bases with solvable completeness problem
• Solvability of the problem of completeness of automaton basis depending on its Boolean part
• On the classification of bases in \(P_k\) according to the decidability of the completeness problem for automata
• scientific article; zbMATH DE number 5005932 (Why is no real title available?)
• A criterion for the decidability of the \(A\)-completeness problem for definite automata
• Dualizability of automatic algebras.

This page was built for publication: On the classification of Post automaton bases according to the decidability of the completeness and \(A\)-completeness problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1594479)