A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time
Tekijät: Halava Vesa, Holub Štěpán
Kustantaja: World Scientific
Julkaisuvuosi: 2023
Journal: International Journal of Foundations of Computer Science
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
ISSN: 0129-0541
eISSN: 1793-6373
DOI: https://doi.org/10.1142/S0129054123480076
Verkko-osoite: https://doi.org/10.1142/S0129054123480076
We show that the binary generalized Post’s Correspondence Problem is decidable in polynomial time for the case where both morphisms are periodic. Our result is based on combinatorial properties and we have formalized the proofs and verified correctness of our algorithm using the Isabelle/HOL formal proof system.
