On some variants of Post's correspondence problem

DOI10.1007/BF00290732zbMATH Open0537.68080DBLPjournals/acta/Ruohonen83WikidataQ56095058 ScholiaQ56095058MaRDI QIDQ792770FDOQ792770

Authors: Keijo Ruohonen 

Publication date: 1983

Published in: Acta Informatica (Search for Journal in Brave)

Recommendations

• Publication:4729772
• On the \(n\)-permutation Post correspondence problem
• Some new results on Post correspondence problem and its modifications
• Remarks on generalized Post Correspondence Problem
• On simplest possible solutions for Post Correspondence Problems
• Post's correspondence problem: from computer science to algebra
• scientific article; zbMATH DE number 1522564
• On F-prime solutions of the Post correspondence problem
• The Post correspondence problem over a unary alphabet
• On the dual Post correspondence problem

zbMATH Keywords

decidabilityundecidabilitylinear bounded automataemptiness problemPost's Correspondence Problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Turing machines and related notions (03D10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on Post's correspondence problem
• Generalized Parikh mappings and homomorphisms
• Title not available (Why is that?)
• Title not available (Why is that?)
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Remark on Code Sets and Context-Free Languages
• Title not available (Why is that?)

Cited In (21)

• More decidable instances of Post's correspondence problem: beyond counting
• Undecidable verification problems for programs with unreliable channels
• Title not available (Why is that?)
• Title not available (Why is that?)
• Post correspondence problem for short words
• Deterministic semi-Thue systems and variants of Post correspondence problem
• A variant of a recursively unsolvable problem
• The Post correspondence problem in groups.
• Post correspondence problem with partially commutative alphabets
• On bi-infinite and conjugate post correspondence problems
• On the dual Post correspondence problem
• Undecidable problems in unreliable computations.
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• On the steps of Emil Post: from normal systems to the correspondence decision problem
• Remarks on generalized Post Correspondence Problem
• Decidability of liveness for concurrent objects on the TSO memory model
• On the \(n\)-permutation Post correspondence problem
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Title not available (Why is that?)
• New proof for the undecidability of the circular PCP
• On complete one-way functions

This page was built for publication: On some variants of Post's correspondence problem

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