Name
Abstract | ||
|---|---|---|
Many regularity properties of strings, like those appearing in hardware specification and verification, can be expressed in terms of word equations. The solvability problem of word equations is NP-hard and the first algorithm to find a solution for a word equation, when this solution exists, was given by Makanin in 1977. The time complexity of Makanin's algorithm is triple exponential in the length of the equations. In this paper we present an evolutionary algorithm with a local search procedure that is efficient for solving word equation systems. The fitness function of our algorithm is based on Levensthein distance considered as metric for the set of 0-1 binary strings. Our experimental results evidence that this metric is better suited for solving word equations than other edit metrics like, for instance, Hamming distance. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-76631-5_30 | MICAI |
Keywords | Field | DocType |
word equation,experimental results evidence,hamming distance,levensthein distance,fitness function,local search procedure,evolutionary algorithm,hardware specification,word equations,binary string,local search strategies.,word equation solver,evolutionary computation,word equation system,local search,time complexity,evolutionary computing | Edit distance,Evolutionary algorithm,Computer science,Word metric,Fitness function,Hamming distance,Artificial intelligence,Solver,Local search (optimization),Time complexity,Machine learning | Conference |
Volume | ISSN | ISBN |
4827 | 0302-9743 | 3-540-76630-8 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| César L. Alonso | 1 | 27 | 4.69 |
| David Alonso | 2 | 0 | 0.34 |
| Mar Callau | 3 | 2 | 1.05 |
| Josè L. Montaña | 4 | 82 | 15.50 |