A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Hardness results for constant-free pattern languages and word equations
Tekijät: Aleksi Saarela
Toimittaja: Artur Czumaj, Anuj Dawar, Emanuela Merelli
Konferenssin vakiintunut nimi: International Colloquium on Automata, Languages, and Programming
Kustantaja: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Julkaisuvuosi: 2020
Journal: LIPICS – Leibniz international proceedings in informatics
Kokoomateoksen nimi: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Tietokannassa oleva lehden nimi: Leibniz International Proceedings in Informatics, LIPIcs
Sarjan nimi: Leibniz International Proceedings in Informatics (LIPIcs)
Vuosikerta: 168
Aloitussivu: 140:1
Lopetussivu: 140:15
ISBN: 978-3-95977-138-2
ISSN: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.ICALP.2020.140
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/48671620
We
study constant-free versions of the inclusion problem of pattern
languages and the satisfiability problem of word equations. The
inclusion problem of pattern languages is known to be undecidable for
both erasing and nonerasing pattern languages, but decidable for
constant-free erasing pattern languages. We prove that it is undecidable
for constant-free nonerasing pattern languages. The satisfiability
problem of word equations is known to be in PSPACE and NP-hard. We prove
that the nonperiodic satisfiability problem of constant-free word
equations is NP-hard. Additionally, we prove a polynomial-time reduction
from the satisfiability problem of word equations to the problem of
deciding whether a given constant-free equation has a solution morphism α
such that α(xy) ≠ α(yx) for given variables x and y.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
