Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time

DOI10.1142/S0129054123480076OpenAlexW4387672105MaRDI QIDQ6154978

Vesa Halava, Štěpán Holub

Publication date: 16 February 2024

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054123480076

zbMATH Keywords

Isabelle/HOLbinary Post's correspondence problemperiodic morphism

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Computability and recursion theory (03Dxx)

Cites Work

• Title not available (Why is that?)
• 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
• Binary (generalized) Post Correspondence Problem
• Concrete Semantics
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• BINARY MORPHISMS WITH STABLE SUFFIX COMPLEXITY
• REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• A variant of a recursively unsolvable problem
• Formalization of Basic Combinatorics on Words

This page was built for publication: Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time

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