| Author | dc.contributor.author | Diekert, Volkert | |
| Author | dc.contributor.author | Gutiérrez Gallardo, Claudio | es_CL |
| Author | dc.contributor.author | Hagenah, Christian | es_CL |
| Admission date | dc.date.accessioned | 2007-05-18T16:10:20Z | |
| Available date | dc.date.available | 2007-05-18T16:10:20Z | |
| Publication date | dc.date.issued | 2005-11-01 | |
| Cita de ítem | dc.identifier.citation | INFORMATION AND COMPUTATION 202 (2): 105-140 NOV 1 2005 | en |
| Identifier | dc.identifier.issn | 0890-5401 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/124610 | |
| Abstract | dc.description.abstract | It is well-known that the existential theory of equations in free groups is decidable. This is a celebrated result of Makanin which was published 1982. Makanin did not discuss complexity issues, but later it was shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space. This improvement is based upon an extension of Plandowski's techniques for solving word equations. We present a Pspace-algorithm in a more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. We obtain our main result about the existential theory in free groups as a corollary of the corresponding statement in free monoids with involution. | en |
| Lenguage | dc.language.iso | en | en |
| Publisher | dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | en |
| Keywords | dc.subject | WORD EQUATIONS | en |
| Título | dc.title | The existential theory of equations with rational constraints in free groups is PSPACE-complete | en |
| Document type | dc.type | Artículo de revista | |
