Satisfiability of word equations with constants is in PSPACE
Journal of the ACMPublished 1 May 2004
Wojciech Plandowski
Citations136
SJR quartileQ1
SJR score2.25
SNIP3.16
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We prove that satisfiability problem for word equations is in PSPACE.
Keywords
Computer Science
HAL (Le Centre pour la Communication Scientifique Directe)Combinatorics on words
1,751 Citations1984M. Lothaire
Mathematics of the USSR-SbornikTHE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
492 Citations1977G. S. Makanin
Lecture notes in computer scienceTesting equivalence of morphisms on context-free languages
143 Citations1994Wojciech Plandowski
A polynomial time algorithm for testing if two morphisms are equal on every word of a context-free language and whether or not n first elements of two sequences of words defined by recurrence formulae are the same.
Recognizing string graphs in NP
110 Citations2002Marcus Schaefer, Eric Sedgwick +1 more
It is shown that the recognition problem for string graphs is in NP, and therefore NP-complete, since Kratochvíl showed that the Recognition problem is NP-hard.
Lecture notes in computer scienceMakanin's algorithm for word equations-two improvements and a generalization
98 Citations1992Klaus U. Schulz
Two improvements of Makanin's algorithm are described which bring it nearer to the area of practical applicability and a simple pre-algorithm is suggested which decides the solvability of word equations with not more than two occurrences of each variable and which partially solves and simplifies the decision procedure for all other equations.
Journal of the ACMMinimal and complete word unification
98 Citations1990Joxan Jaffar
The main result of this paper solves the complementary problem of generating the set of all solutions and generates, given a word equation, a minimal and complete set of unifiers.
Lecture notes in computer scienceApplication of Lempel-Ziv encodings to the solution of word equations
92 Citations1998Wojciech Plandowski, Wojciech Rytter
A new approach is introduced and the solvability can be tested in polynomial deterministic time if the lengths of all variables are given in binary and it is proved that each minimal solution of a word equation is highly compressible (exponentially compressible for long solutions) in terms of Lempel-Ziv encoding.
Finding patterns common to a set of strings (Extended Abstract)
81 Citations1979Dana Angluin
This problem is shown to be effectively solvable in the general case and to lead to correct inference in the limit of the pattern languages and a polynomial time algorithm for finding minimal one-variable pattern languages compatible with a given set of strings is given.
Journal of the ACMThe expressibility of languages and relations by word equations
67 Citations2000Juhani Karhumäki, Filippo Mignosi +1 more
This paper proves theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations.
Journal of the ACMComplexity of Makanin's algorithm
66 Citations1996Antoni Kościelski, Leszek Pacholski
It is proved that the exponent of periodicity of a minimal solution of a word equation is of order 2, which implies an exponential improvement of known upper bounds on complexity of word-unification algorithms.
Satisfiability of word equations with constants is in NEXPTIME
48 Citations1999Wojciech Plandowski
It is proved that the length of a shortest solution of a word equation of length n can bounded by a double exponential function in n and proves that the problem of solvability of word equations is in NEXPTIME.
Journal of Symbolic ComputationSolving word equations
41 Citations1989Habib Abdulrab, Jean-Pierre Pécuchet
Satisfiability of word equations with constants is in exponential space
39 Citations2002Claudio Gutiérrez
This paper proves the stronger fact that Makanin's algorithm (1977), a general procedure to decide if a word equation has a solution, is single exponential, while reducing it to triple exponential, and conjecturing that it could be brought down to double exponential.
Résolution d'équations sur les mots : étude et implémentation Lisp de l'algorithme de Makanin
18 Citations1987Habib Abdulrab