The Post correspondence problem over a unary alphabet

DOI10.1016/S0893-9659(03)00073-9zbMath1041.03031OpenAlexW2081149247MaRDI QIDQ1431872

Gerhard J. Woeginger, Piotr Rudnicki

Publication date: 11 June 2004

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0893-9659(03)00073-9

zbMATH Keywords

computational complexityNP-completenessPost correspondence problempseudopolynomial time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Thue and Post systems, etc. (03D03)

Related Items

Study of differential equations on warped product semi-invariant submanifolds of the generalized Sasakian space forms, From decidability to undecidability by considering regular sets of instances

Cites Work

• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item