scientific article; zbMATH DE number 572102

zbMath0816.68078MaRDI QIDQ4294173

Arto Salomaa, Grzegorz Rozenberg

Publication date: 24 May 1994

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Post correspondence problemHalting problemdiophantine problemsThe secret number

Mathematics Subject Classification ID

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

Related Items (19)

Undecidability of State Complexities Using Mirror Images ⋮ Slender 0L languages ⋮ Is complexity a source of incompleteness? ⋮ Natural halting probabilities, partial randomness, and zeta functions ⋮ On the membership of invertible diagonal and scalar matrices ⋮ Unification in sort theories and its applications ⋮ The complete realization problem for hidden Markov models: a survey and some new results ⋮ Quasi-universal \(k\)-regular sequences ⋮ STATE COMPLEXITY AND APPROXIMATION ⋮ Post correspondence problem: Words possible as primitive solutions ⋮ The freeness problem over matrix semigroups and bounded languages ⋮ Recursively enumerable reals and Chaitin \(\Omega\) numbers ⋮ On the power of enzymatic numerical P systems ⋮ Unnamed Item ⋮ The undecidability of some equivalence problems concerning ngsm's and finite substitutions ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ Absoluteness of subword inequality is undecidable ⋮ Universality of Enzymatic Numerical P systems ⋮ Undecidability of state complexity

This page was built for publication: