Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10471504" target="_blank" >RIV/00216208:11320/23:10471504 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=SJZsJAZhYa" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=SJZsJAZhYa</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0129054123480076" target="_blank" >10.1142/S0129054123480076</a>
Alternative languages
Result language
angličtina
Original language name
Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time
Original language description
We show that the binary generalized Post's Correspondence Problem is decidable inpolynomial time for the case where both morphisms are periodic.Our result is based oncombinatorial properties and we have formalized the proofs and verified correctness ofour algorithm using the Isabelle/HOL formal proof system.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
International Journal of Foundations of Computer Science
ISSN
0129-0541
e-ISSN
1793-6373
Volume of the periodical
Neuveden
Issue of the periodical within the volume
October
Country of publishing house
SG - SINGAPORE
Number of pages
16
Pages from-to
1-16
UT code for WoS article
001086426200001
EID of the result in the Scopus database
2-s2.0-85174848028