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

Kód výsledku v 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>
Výsledek na webu
<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>

Jazyk výsledku
angličtina
Název v původním jazyce
Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time
Popis výsledku anglicky
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.

Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění
2023
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)