Solutions of Word Equations over Partially Commutative Structures
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2016
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908400388931584 |
|---|---|
| author | Diekert, Volker Jeż, Artur Kufleitner, Manfred Thumm, Alexander |
| author_facet | Diekert, Volker Jeż, Artur Kufleitner, Manfred Thumm, Alexander |
| contents | Let $M(A,I)$ be a free partially commutative monoid with involution and $G(A,I)$ be its quotient group, e.g. a right-angled Artin or Coxeter group. Given a system of word equations over $M(A,I)$ with recognizable constraints with input size $n$ we show the structural result about the solution set of the system: the set of all solutions in $M(A,I)$ or in the group $G(A,I)$ is an EDT0L language. That is, it is given by an NFA $\mathcal{A}$ recognizing endomorphisms over some extended monoid. Moreover, $\mathcal{A}$ is effectively constructible by an NSPACE($n \log n$)-transducer. This implies that Satisfiability: `Is the system is solvable?' and Finiteness: `Are there infinitely many solutions?' can be decided in NSPACE($n \log n$). In the uniform version, these problems are PSPACE-complete, but for a suitable subclass of constraints we have more precise complexities and we conjecture that the decision problems above are NP-complete in this setting. Our results apply also to word equation over free monoids in the classical case where the involution is reading words right-to-left. This allows to specify that solutions are restricted to be palindromes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1603_02966 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Solutions of Word Equations over Partially Commutative Structures Diekert, Volker Jeż, Artur Kufleitner, Manfred Thumm, Alexander Formal Languages and Automata Theory Logic in Computer Science Group Theory 03D05, 20F65, 20F70, 68Q25, 68Q45 F.2.2; F.4.2; F.4.3 Let $M(A,I)$ be a free partially commutative monoid with involution and $G(A,I)$ be its quotient group, e.g. a right-angled Artin or Coxeter group. Given a system of word equations over $M(A,I)$ with recognizable constraints with input size $n$ we show the structural result about the solution set of the system: the set of all solutions in $M(A,I)$ or in the group $G(A,I)$ is an EDT0L language. That is, it is given by an NFA $\mathcal{A}$ recognizing endomorphisms over some extended monoid. Moreover, $\mathcal{A}$ is effectively constructible by an NSPACE($n \log n$)-transducer. This implies that Satisfiability: `Is the system is solvable?' and Finiteness: `Are there infinitely many solutions?' can be decided in NSPACE($n \log n$). In the uniform version, these problems are PSPACE-complete, but for a suitable subclass of constraints we have more precise complexities and we conjecture that the decision problems above are NP-complete in this setting. Our results apply also to word equation over free monoids in the classical case where the involution is reading words right-to-left. This allows to specify that solutions are restricted to be palindromes. |
| title | Solutions of Word Equations over Partially Commutative Structures |
| topic | Formal Languages and Automata Theory Logic in Computer Science Group Theory 03D05, 20F65, 20F70, 68Q25, 68Q45 F.2.2; F.4.2; F.4.3 |
| url | https://arxiv.org/abs/1603.02966 |