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

DOI10.1134/S1064562411040065zbMATH Open1244.68049MaRDI QIDQ656372FDOQ656372

Authors: D. N. Zhuk 

Publication date: 17 January 2012

Published in: Doklady Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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)