Towards parametrizing word equations

H. Abdulrab; P. Goralčík; G. S. Makanin

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 35, Issue: 4, page 331-350
  • ISSN: 0988-3754

Abstract

top
Classically, in order to resolve an equation u ≈ v over a free monoid X*, we reduce it by a suitable family ℱ of substitutions to a family of equations uf ≈ vf, f ∈ ℱ , each involving less variables than u ≈ v, and then combine solutions of uf ≈ vf into solutions of u ≈ v. The problem is to get ℱ in a handy parametrized form. The method we propose consists in parametrizing the path traces in the so called graph of prime equations associated to u ≈ v. We carry out such a parametrization in the case the prime equations in the graph involve at most three variables.

How to cite

top

Abdulrab, H., Goralčík, P., and Makanin, G. S.. "Towards parametrizing word equations." RAIRO - Theoretical Informatics and Applications 35.4 (2010): 331-350. <http://eudml.org/doc/222084>.

@article{Abdulrab2010,
abstract = { Classically, in order to resolve an equation u ≈ v over a free monoid X*, we reduce it by a suitable family $\cal F$ of substitutions to a family of equations uf ≈ vf, $f\in\cal F$, each involving less variables than u ≈ v, and then combine solutions of uf ≈ vf into solutions of u ≈ v. The problem is to get $\cal F$ in a handy parametrized form. The method we propose consists in parametrizing the path traces in the so called graph of prime equations associated to u ≈ v. We carry out such a parametrization in the case the prime equations in the graph involve at most three variables. },
author = {Abdulrab, H., Goralčík, P., Makanin, G. S.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Equation; free monoid; parametrization; universal family.; universal family},
language = {eng},
month = {3},
number = {4},
pages = {331-350},
publisher = {EDP Sciences},
title = {Towards parametrizing word equations},
url = {http://eudml.org/doc/222084},
volume = {35},
year = {2010},
}

TY - JOUR
AU - Abdulrab, H.
AU - Goralčík, P.
AU - Makanin, G. S.
TI - Towards parametrizing word equations
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 4
SP - 331
EP - 350
AB - Classically, in order to resolve an equation u ≈ v over a free monoid X*, we reduce it by a suitable family $\cal F$ of substitutions to a family of equations uf ≈ vf, $f\in\cal F$, each involving less variables than u ≈ v, and then combine solutions of uf ≈ vf into solutions of u ≈ v. The problem is to get $\cal F$ in a handy parametrized form. The method we propose consists in parametrizing the path traces in the so called graph of prime equations associated to u ≈ v. We carry out such a parametrization in the case the prime equations in the graph involve at most three variables.
LA - eng
KW - Equation; free monoid; parametrization; universal family.; universal family
UR - http://eudml.org/doc/222084
ER -

References

top
  1. J. Jaffar, Minimal and Complete Word Unification. J. ACM37 (1990) 47-85.  
  2. Yu.I. Hmelevskii, Equations in free semigroups. Trudy Mat. Inst. Steklova 107 (1971); English Translation in Proc. Steklov Inst. Math. 107 (1971) 1976.  
  3. A. Lentin, Équations dans les monoïdes libres. Gautier-Villars, Paris (1972).  
  4. M. Lothaire, Combinatorics on Words. Addison-Wesley (1983).  
  5. G.S. Makanin, The problem of solvability of equations in a free semigroup. Mat. Sbornik 103 (1977) 147-236 (in Russian); English Translation in Math. USSR Sbornik 32 (1977) 128-198.  
  6. G.S. Makanin, On general solution of equations in free semigroups, in Proc. of IWWERT'91, edited by H. Abdulrab and J.P. Pécuchet. Springer, Lecture Notes in Comput. Sci. 677, 1-5.  
  7. G. Plotkin, Building-in Equational Theories. Machine intelligence7 (1972) 73-90.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.