More decidable instances of Post's correspondence problem: beyond counting
type: Item
instance of: scholarly article
title: More decidable instances of Post's correspondence problem: beyond counting
zbMATH Open document ID: 1186.68266
author: Mirko Rahn
published in: Information Processing Letters
publication date: 2010-04-19T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5694917
zbMATH Keywords: Post correspondence problem
zbMATH Keywords: context-free language
zbMATH Keywords: decidability
zbMATH Keywords: combinatorial problems
MaRDI profile type: Publication
full work available at URL: j.ipl.2007.11.002
OpenAlex ID: W1986342569
cites work: The (generalized) Post correspondence problem with lists consisting of two words is decidable
cites work: A Remark on Code Sets and Context-Free Languages
cites work: Generalized Post correspondence problem for marked morphisms
cites work: Extension of the decidability of the marked PCP to instances with unique blocks
cites work: Marked PCP is decidable
cites work: A useful device for showing the solvability of some decision problems
cites work: Generalized Parikh mappings and homomorphisms
cites work: Q4714446
cites work: A variant of a recursively unsolvable problem
DOI: 10.1016/J.IPL.2007.11.002
Recommended article: On some variants of Post's correspondence problem
Recommended article: Decidability of the binary infinite Post Correspondence Problem
Recommended article: Q4729772
Recommended article: Q4453473
Recommended article: The exact complexity of the infinite Post Correspondence Problem
Recommended article: On the \(n\)-permutation Post correspondence problem
Recommended article: P, NP, and the Post correspondence problem
Recommended article: On simplest possible solutions for Post Correspondence Problems
Recommended article: Post's correspondence problem: from computer science to algebra
Recommended article: Q4265636
description: scientific article; zbMATH DE number 5694917