On decidability of the completeness problem for special systems of automaton functions

DOI10.1515/DMA.1996.6.5.491MaRDI QIDQ3125966zbMATH OpenOpenAlexFDO

Authors Dmitriĭ Nikolaevich Babin

Publication date 23 March 1997

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma.1996.6.5.491

zbMATH Keywords

\(A\)-completeness problemalgorithmic decidabilityautomaton functionscompleteness problemPost class

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(14)

• Decidability of some problems related to the class of nondeterministic iterative (k,m)-systems
• On the classification of Post automaton bases according to the decidability of the completeness and \(A\)-completeness problems
• The completeness problem in the function algebra of linear integer-coefficient polynomials
• Completeness problem for the class of linear automata functions
• On the classification of Post automaton bases by the decidability of the A-completeness property for definite automata
• Automatic Decidability and Combinability Revisited
• SYSTEM FUNCTIONS AND THEIR DECISION PROBLEMS
• scientific article; zbMATH DE number 1268706 (Why is no real title available?)
• scientific article; zbMATH DE number 468641 (Why is no real title available?)
• AN ELEMENTARY SYSTEM AS AND ITS SEMI‐COMPLETENESS AND DECIDABILITY
• The completeness criterion for systems which contain all one-place finite-automaton functions
• Undecidability of the completeness and A-completeness problems for some systems of automaton functions
• The completeness criterion for some systems containing \(P\)-sets of automaton functions
• A criterion for the decidability of the A-completeness problem for definite automata

This page was built for publication: On decidability of the completeness problem for special systems of automaton functions

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