scientific article; zbMATH DE number 572102

MaRDI QIDQ4294173zbMATH OpenFDO

Authors Grzegorz Rozenberg, Arto Salomaa

Publication date 24 May 1994

zbMATH Keywords

diophantine problemsHalting problemPost correspondence problemThe secret number

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45)

Recommendations

• Elementar computability theory
• scientific article; zbMATH DE number 49449
• Publication:4505125

Cited in

(30)

• The unification hierarchy is undecidable
• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• An undecidable fragment of the theory of set constraints
• Slender 0L languages
• Unification in sort theories and its applications
• Undecidability and intuitionistic incompleteness
• Quasi-universal \(k\)-regular sequences
• The freeness problem over matrix semigroups and bounded languages
• Is complexity a source of incompleteness?
• Universality of Enzymatic Numerical P systems
• Undecidability of state complexity
• Undecidability of state complexities using mirror images
• Undecidable problems: a sampler
• Undecidability in Some Structures Related to Computation Theory
• scientific article; zbMATH DE number 4031659 (Why is no real title available?)
• Post correspondence problem: words possible as primitive solutions
• scientific article; zbMATH DE number 2123258 (Why is no real title available?)
• State complexity and approximation
• Undecidability of the Spectral Gap
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• Termination of linear loops over the integers
• scientific article; zbMATH DE number 5497805 (Why is no real title available?)
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• The complete realization problem for hidden Markov models: a survey and some new results
• On the Skolem problem and the Skolem conjecture
• On the power of enzymatic numerical P systems
• On large zeros of linear recurrence sequences
• Absoluteness of subword inequality is undecidable
• Natural halting probabilities, partial randomness, and zeta functions
• On the membership of invertible diagonal and scalar matrices

This page was built for publication:

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