Name
Abstract | ||
|---|---|---|
One of the most intrincate algorithms related to words is Makanin's algorithm for solving word equations. Even if Makanin's algorithm is very complicated, the solvability problem for word equations remains NP-hard if one looks for short solutions, i.e. with length bounded by a linear function w. r. t. the size of the system ([2]) or even with constant bounded length ([1]). Word equations can be used to define various properties of strings, e. g. characterization of imprimitiveness, hardware specification and verification and string unification in PROLOG-3 or unification in theories with associative non-commutative operators. This paper is devoted to propose the heuristic approach to deal with the problem of solving word equation systems provided that some upper bound for the length of the solutions is given. Up to this moment several heuristic strategies have been proposed for other NP-complete problems, like 3-SAT, with a remarkable success. Following this direction we compare here two genetic local search algorithms for solving word equation systems. The first one consists of an adapted version of the well known WSAT heuristics for 3-SAT instances (see [9]). The second one is an improved version of our genetic local search algorithm in ([1]). We present some empirical results which indicate that our approach to this problem becomes a promising strategy. Our experimental results also certify that our local optimization technique seems to outperform the WSAT class of local search procedures for the word equation system problem. Keywords: Evolutionary computation, genetic algorithms, local search strategies, word equations. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-28645-5_9 | ADVANCES IN ARTIFICIAL INTELLIGENCE - SBIA 2004 |
Keywords | Field | DocType |
evolutionary computation,genetic algorithms,local search strategies,word equations | Constraint satisfaction,Discrete mathematics,Heuristic,Search algorithm,Computer science,Algorithm,Evolutionary computation,Theoretical computer science,Local search (optimization),String (computer science),Genetic algorithm,Bounded function | Conference |
Volume | ISSN | Citations |
3171 | 0302-9743 | 1 |
PageRank | References | Authors |
0.36 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| César Luis Alonso | 1 | 9 | 2.97 |
| Fátima Drubi | 2 | 1 | 0.36 |
| Judith Gómez-garcía | 3 | 1 | 0.36 |
| Josè L. Montaña | 4 | 82 | 15.50 |