A1 Refereed original research article in a scientific journal

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



Authors: Halava Vesa, Holub Štěpán

Publisher: World Scientific

Publication year: 2023

Journal: International Journal of Foundations of Computer Science

Journal name in source: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

ISSN: 0129-0541

eISSN: 1793-6373

DOI: https://doi.org/10.1142/S0129054123480076

Web address : https://doi.org/10.1142/S0129054123480076


Abstract

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.



Last updated on 2024-26-11 at 18:24