Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.127
URN: urn:nbn:de:0030-drops-62624
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6262/
Diekert, Volker ; Jez, Artur ; Kufleitner, Manfred
Solutions of Word Equations Over Partially Commutative Structures
| pdf-format: |
|
Abstract
We give NSPACE(n*log(n)) algorithms solving the following decision problems. Satisfiability: Is the given equation over a free partially commutative monoid with involution (resp. a free partially commutative group) solvable? Finiteness: Are there only finitely many solutions of such an equation? PSPACE algorithms with worse complexities for the first problem are known, but so far, a PSPACE algorithm for the second problem was out of reach. Our results are much stronger: Given such an equation, its solutions form an EDT0L language effectively representable in NSPACE(n*log(n)). In particular, we give an effective description of the set of all solutions for equations with constraints in free partially commutative monoids and groups.
BibTeX - Entry
@InProceedings{diekert_et_al:LIPIcs:2016:6262,
author = {Volker Diekert and Artur Jez and Manfred Kufleitner},
title = {{Solutions of Word Equations Over Partially Commutative Structures}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {127:1--127:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6262},
URN = {urn:nbn:de:0030-drops-62624},
doi = {10.4230/LIPIcs.ICALP.2016.127},
annote = {Keywords: Word equations, EDT0L language, trace monoid, right-angled Artin group, partial commutation}
}
| Keywords: | Word equations, EDT0L language, trace monoid, right-angled Artin group, partial commutation | |
| Seminar: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 23.08.2016 |
