A criterion for the decidability of the A-completeness problem for definite automata

DOI10.1134/S1064562411040065MaRDI QIDQ656372zbMATH OpenFDO

Authors D. N. Zhuk

Publication date 17 January 2012

Published in Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

automatic structuresmonadic second-order logicBoolean functionsalgorithmic decidabilitypush-down machinesA-completenessdefinite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the classification of Post automaton bases by the decidability of the \(A\)-completeness property for definite automata
• On decidability of the completeness problem for special systems of automaton functions
• Undecidability of the completeness and A-completeness problems for some systems of automaton functions
• scientific article; zbMATH DE number 4769
• Decidability of the equivalence problem for deterministic pushdown automata
• scientific article; zbMATH DE number 1342250
• On the classification of Post automaton bases according to the decidability of the completeness and \(A\)-completeness problems
• A characterization of completely reachable automata
• On completeness of nondeterministic automata

Cites work

• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(2)

• On the classification of bases in \(P_k\) according to the decidability of the completeness problem for automata
• Undecidability of the completeness and A-completeness problems for some systems of automaton functions

This page was built for publication: A criterion for the decidability of the \(A\)-completeness problem for definite automata

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