Towards parametrizing word equations

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • 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 u f ≈ v f , f ∈ ℱ , each involving less variables than u ≈ v , and then combine solutions of u f ≈ v f 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 - Informatique Théorique et Applications 35.4 (2001): 331-350. <http://eudml.org/doc/92669>.

@article{Abdulrab2001,
abstract = {Classically, in order to resolve an equation $u\approx v$ over a free monoid $X^*$, we reduce it by a suitable family $\mathcal \{F\}$ of substitutions to a family of equations $uf\approx vf$, $f\in \mathcal \{F\}$, each involving less variables than $u\approx v$, and then combine solutions of $uf\approx vf$ into solutions of $u\approx v$. The problem is to get $\mathcal \{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\approx 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 - Informatique Théorique et Applications},
keywords = {equation; free monoid; parametrization; universal family},
language = {eng},
number = {4},
pages = {331-350},
publisher = {EDP-Sciences},
title = {Towards parametrizing word equations},
url = {http://eudml.org/doc/92669},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Abdulrab, H.
AU - Goralčík, P.
AU - Makanin, G. S.
TI - Towards parametrizing word equations
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2001
PB - EDP-Sciences
VL - 35
IS - 4
SP - 331
EP - 350
AB - Classically, in order to resolve an equation $u\approx v$ over a free monoid $X^*$, we reduce it by a suitable family $\mathcal {F}$ of substitutions to a family of equations $uf\approx vf$, $f\in \mathcal {F}$, each involving less variables than $u\approx v$, and then combine solutions of $uf\approx vf$ into solutions of $u\approx v$. The problem is to get $\mathcal {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\approx 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
UR - http://eudml.org/doc/92669
ER -

References

top
  1. [1] J. Jaffar, Minimal and Complete Word Unification. J. ACM 37 (1990) 47-85. Zbl0697.68052MR1072430
  2. [2] Yu.I. Hmelevskiĭ, Equations in free semigroups. Trudy Mat. Inst. Steklova 107 (1971); English Translation in Proc. Steklov Inst. Math. 107 (1971) 1976. Zbl0326.02032MR393284
  3. [3] A. Lentin, Équations dans les monoïdes libres. Gautier-Villars, Paris (1972). Zbl0258.20058MR333034
  4. [4] M. Lothaire, Combinatorics on Words. Addison-Wesley (1983). Zbl0514.20045MR675953
  5. [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. Zbl0396.20037MR470107
  6. [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. Zbl0925.20067
  7. [7] G. Plotkin, Building-in Equational Theories. Machine intelligence 7 (1972) 73-90. Zbl0262.68036

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.