Ecuación de palabras

Relación en la informática teórica

Una ecuación de palabras es una igualdad formal entre un par de palabras  y , cada una sobre un alfabeto  que comprende tanto constantes (cf ) como incógnitas (cf ). ^[1]  Se dice que  una asignación  de palabras constantes a las incógnitas de resuelve si asigna ambos lados de  a palabras idénticas. En otras palabras, las soluciones de  son aquellos morfismos  cuya restricción a  es la función identidad , y que satisfacen . Las ecuaciones de palabras son un objeto central en la combinatoria de palabras ; desempeñan un papel análogo en esta área al de las ecuaciones diofánticas en la teoría de números . Una marcada diferencia es que las ecuaciones diofánticas tienen un problema de solubilidad indecidible , ^[2] mientras que el problema análogo para las ecuaciones de palabras es decidible . ^[3] ${\displaystyle E:=u{\overset {\cdot }{=}}v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \Sigma \cup \Xi }$ ${\displaystyle \Sigma }$ ${\displaystyle \Xi }$ ${\displaystyle h}$ ${\displaystyle E}$ ${\displaystyle E}$  ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle h:(\Sigma \cup \Xi )^{*}\to \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle h(u)=h(v)}$

Un ejemplo clásico de una ecuación de palabras es la ecuación de conmutación , en la que  es una incógnita y  es una palabra constante. Es bien sabido ^[4] que las soluciones de la ecuación de conmutación son exactamente aquellos morfismos  que se asignan  a alguna potencia de . Otro ejemplo es la ecuación de conjugación ^[5] , en la que  y  son todas incógnitas. Las soluciones de esta ecuación son precisamente aquellos morfismos  que envían  y  a las palabras conjugadas, con la imagen  completada según corresponda. ${\displaystyle xw{\overset {\cdot }{=}}wx}$ ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle xz{\overset {\cdot }{=}}zy}$ ${\displaystyle x,y,}$ ${\displaystyle z}$ ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle h(z)}$

Se han introducido muchas subclases de ecuaciones de palabras, algunas de las cuales incluyen:

• ecuaciones libres de constantes , ^[6] que son aquellas  que  comprenden solo incógnitas. Dichas ecuaciones tienen una solución trivial en la que se eliminan todas sus incógnitas; por lo tanto, se las suele estudiar sobre semigrupos libres . ${\displaystyle u{\overset {\cdot }{=}}v}$ ${\displaystyle u,v}$
• ecuaciones cuadráticas ^[1] , que son aquellas que contienen cada una de sus incógnitas como máximo dos veces. Esta es exactamente la clase de ecuaciones de palabras en las que termina el algoritmo de Transformaciones de Nielsen (véase más abajo).
• ecuaciones de palabras con una incógnita , cuya solubilidad en tiempo lineal se puede comprobar . ^[7]

Historia

El estudio de las ecuaciones verbales fue iniciado por Willard Quine en 1946. Quine demostró ^[8] que la teoría de primer orden de las ecuaciones verbales es esencialmente equivalente a la teoría de primer orden de la aritmética. En 1954, Andrey Markov propuso ^[9] el problema de solubilidad de las ecuaciones verbales: decidir si una ecuación verbal dada admite una solución. Durante mucho tiempo, se esperó que este problema fuera indecidible . Una razón para esto es que se esperaba, ^[10] (incorrectamente, según se demostró), que las ecuaciones verbales pudieran proporcionar un paso intermedio entre el Décimo Problema de Hilbert y los problemas indecidibles relacionados con las máquinas de Turing .

Gennady Makanin , quien introdujo el algoritmo de Makanin.

A principios de los años 1970 se realizaron más contribuciones con el trabajo de André Lentin y Juri Ilich Hmelevskii. ^[11] En 1976, Gennady Makanin introdujo ^[3] un método con el que se podía determinar si una ecuación dada admitía una solución. Es muy difícil demostrar que este procedimiento, que se ha dado en llamar algoritmo de Makanin, existe, y es uno de los resultados más celebrados en la combinatoria de palabras ^[10] . El algoritmo de Makanin se considera uno de los más difíciles conceptualmente que existen en la literatura ^[6] , y también es muy intratable , requiriendo (en su formulación inicial) un tiempo triplemente exponencial . ^[12] Por lo tanto, hubo muchos intentos de mejorarlo ^[12] . En 1999, Wojciech Plandowski introdujo un nuevo algoritmo, que mostraba ^[13] que el problema de solubilidad de las ecuaciones de palabras está en PSPACE .

En 2006, Plandowski y Wojciech Rytter demostraron ^[14] que las soluciones mínimas de ecuaciones de palabras son altamente (es decir, exponencialmente) compresibles usando la codificación Lempel-Ziv . Se conjetura ^[14] que la longitud de una solución mínima de una ecuación de palabras  es (como máximo) simplemente exponencial en la longitud  de . Si esta conjetura es verdadera, entonces el resultado de Plandowski y Rytter produce un algoritmo NP sencillo de "adivinar y verificar" para el problema de solubilidad: muestran que una solución  puede verificarse mientras se trabaja solo con su representación comprimida LZ , y si la conjetura es verdadera implicaría que  tiene un polinomio de tamaño en . Tal como está, la última parte del análisis de complejidad -la pregunta de si resolver ecuaciones de palabras es NP-completo- permanece abierta. ( La NP-dureza se desprende inmediatamente del hecho de que resolver ecuaciones de palabras generaliza el problema NP-completo de coincidencia de patrones ^[14] ). ${\displaystyle E}$ ${\displaystyle |E|}$ ${\displaystyle E}$ ${\displaystyle h}$ ${\displaystyle LZ(h)}$ ${\displaystyle LZ(h)}$ ${\displaystyle |E|}$

Métodos de solución

No existe un algoritmo "elemental" para determinar si una ecuación dada admite una solución. ^[15] Los algoritmos mencionados anteriormente son todos de interés teórico, pero no sirven para resolver una ecuación de palabras a mano, por ejemplo. Sin embargo, existen algunos métodos que a veces pueden ayudar con esto:

Argumentos de longitud

Como una solución  a una ecuación verbal  debe unificar sus dos lados, se puede usar el multiconjunto de símbolos que aparecen en ambos lados de  para deducir una igualdad lineal en las longitudes de las imágenes de las incógnitas. Por ejemplo, la forma de  implica que sus soluciones  deben satisfacer , lo que reduce el conjunto de posibles  para comprobar. Argumentos similares pueden permitir que una ecuación verbal  se "divida" en otras más pequeñas si se puede deducir que las posiciones dentro de los dos lados de  deben alinearse en todas las soluciones de . Por ejemplo, los puntos medios de cada lado de  se pueden detectar mediante un argumento de longitud y, por lo tanto, esa ecuación verbal se puede dividir en el sistema . ${\displaystyle h}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle xx{\overset {\cdot }{=}}y}$ ${\displaystyle h}$ ${\displaystyle |h(y)|=2|h(x)|}$ ${\displaystyle h}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle xyyx{\overset {\cdot }{=}}uvvu}$ ${\displaystyle \left\lbrace {\begin{matrix}xy{\overset {\cdot }{=}}uv\\yx{\overset {\cdot }{=}}vu\end{matrix}}\right.}$

Apelación a la periodicidad

Otra herramienta útil para razonar sobre ecuaciones de palabras es el Lema de la Periodicidad de Fine y Wilf ^[1] , que describe lo que sucede si una determinada palabra tiene múltiples períodos (es decir, distancias en las que se repiten sus letras). Consideremos, por ejemplo, la ecuación de palabras ^[15] . Supongamos que  es una de sus soluciones. Entonces . Al tomar una conjugación adecuada en esta identidad, se puede inferir que existe algún conjugado  de  que es tal que . Ahora bien, un argumento de longitud permite identificar aquí el punto medio de cada lado, y de esta observación se sigue que . Aquí está la ecuación de conmutación, de donde  y  son potencias de una palabra común. Ahora bien, las infinitas palabras  y  tienen un prefijo común de longitud . Puesto que , se puede aplicar el Lema de la Periodicidad. Su conclusión aquí es que  y  también son potencias de una palabra común. Por tanto, toda solución  de  se aplica  a  potencias de una palabra común. ${\displaystyle E:=x^{2}y^{2}{\overset {\cdot }{=}}z^{2}}$ ${\displaystyle (x,y,z)\mapsto (w_{x},w_{y},w_{z})}$ ${\displaystyle w_{x}^{2}w_{y}^{2}=w_{z}^{2}}$ ${\displaystyle z'}$ ${\displaystyle z}$ ${\displaystyle z'^{2}=w_{x}w_{y}^{2}w_{x}}$ ${\displaystyle w_{x}w_{y}=z'=w_{y}w_{x}}$ ${\displaystyle w_{x}}$ ${\displaystyle w_{y}}$ ${\displaystyle w_{x}^{\omega }}$ ${\displaystyle w_{z}^{\omega }}$ ${\displaystyle |w_{z}^{2}|}$ ${\displaystyle |w_{z}^{2}|=2|w_{z}|\geq |w_{z}|+|w_{x}|\geq |w_{z}|+|w_{x}|-\gcd(|z|,|x|)}$ ${\displaystyle w_{z}}$ ${\displaystyle w_{x}}$ ${\displaystyle h}$ ${\displaystyle E}$ ${\displaystyle x,y,}$ ${\displaystyle z}$

Transformaciones de Nielsen

El funcionamiento del algoritmo de transformaciones de Nielsen en la ecuación de palabras . No se alcanzó la ecuación de palabras trivial, lo que implica la insolubilidad de la ecuación. ${\displaystyle XaY{\overset {\cdot }{=}}YbX}$

Sea  una ecuación de palabras, tal que , y . Aquí se presentará un método conceptualmente simple (llamado algoritmo de transformaciones de Nielsen o método de Levi ^[16] ) para determinar si  es soluble, con la salvedad de que el método termina solo en ecuaciones de palabras cuadráticas (como se definió anteriormente) ^[5] . ${\displaystyle E:=xu{\overset {\cdot }{=}}yv}$ ${\displaystyle x,y\in \Sigma \cup \Xi }$ ${\displaystyle u,v\in (\Sigma \cup \Xi )^{*}}$ ${\displaystyle E}$

La idea del algoritmo es "adivinar" cómo se comparan las longitudes de  y  en alguna solución de . O bien , o bien . En el primer caso, se puede aplicar la regla de reescritura de cadenas  a , donde  (después de la reescritura) es una nueva cantidad cuyo significado es "lo que queda de la antigua  se  elimina". Simétricamente, en el segundo caso, se puede aplicar la regla , y en el tercer caso . El método presente en realidad realiza las tres suposiciones; para cada una de ellas (por separado) reescribe  para tener en cuenta la suposición realizada. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle E}$ ${\displaystyle |h(x)|>|h(y)|}$ ${\displaystyle |h(x)|<|h(y)|}$ ${\displaystyle h(x)=h(y)}$ ${\displaystyle x\mapsto yx}$ ${\displaystyle E}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y\mapsto xy}$ ${\displaystyle x\mapsto y}$ ${\displaystyle E}$

Por construcción, habrá alguna cancelación al comienzo de  después de aplicar cada regla de reescritura de cadenas. (Por ejemplo, al aplicar  a la ecuación  se obtiene , que se cancela hasta ). El método siempre aprovecha esta cancelación; la esperanza es que sea suficiente para contrarrestar la regla de reescritura de cadenas, que (en general) habrá hecho que la ecuación sea más larga. ${\displaystyle E}$ ${\displaystyle x\mapsto ax}$ ${\displaystyle xab{\overset {\cdot }{=}}abx}$ ${\displaystyle axab{\overset {\cdot }{=}}abax}$ ${\displaystyle xab{\overset {\cdot }{=}}bax}$

El algoritmo, por tanto, equivale a aplicar exhaustivamente estas transformaciones. Es natural considerar el funcionamiento del algoritmo como la construcción de un grafo ^[5] , cuyos nodos son las ecuaciones alcanzadas y las aristas son las transformaciones entre ellas. Si la palabra trivial ecuación , (donde  es la palabra vacía ) se encuentra alguna vez durante esta construcción, entonces  es seguramente solucionable. Por el contrario, si  es soluble, entonces  debe aparecer en . Por tanto, mediante este método (suponiendo  que es finito) se puede determinar si  admite una solución. ${\displaystyle {\mathcal {G}}(E)}$ ${\displaystyle \varepsilon {\overset {\cdot }{=}}\varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle \varepsilon {\overset {\cdot }{=}}\varepsilon }$ ${\displaystyle {\mathcal {G}}(E)}$ ${\displaystyle {\mathcal {G}}(E)}$ ${\displaystyle E}$

Sistemas de ecuaciones de palabras

Se pueden definir sistemas de ecuaciones de palabras de la forma natural ^[4] . Una solución de tal sistema  es un morfismo  que resuelve simultáneamente cada ecuación en . Una extensión natural es considerar fórmulas booleanas de ecuaciones de palabras ^[4] , en las que también se permite la negación y la disyunción . De hecho, cada sistema (e incluso cada fórmula booleana) de ecuaciones de palabras, es equivalente a una sola ecuación de palabras ^[4] . Por lo tanto, muchos resultados sobre ecuaciones de palabras se generalizan inmediatamente a tales sistemas (o fórmulas). Debe decirse, sin embargo, que la transformación en una sola ecuación de palabras puede introducir incógnitas adicionales, y esto es a veces por necesidad. ${\displaystyle S}$ ${\displaystyle h}$ ${\displaystyle S}$

Dos ecuaciones de palabras (o sistemas de las mismas) se denominan equivalentes si tienen el mismo conjunto de soluciones. Un sistema de ecuaciones de palabras se denomina independiente si no es equivalente a ninguno de sus subsistemas propios ^[15] . Dicho de otro modo, un sistema independiente  de ecuaciones de palabras es uno tal que cada una  puede resolverse "independientemente", es decir, sin resolver ninguna de las otras . Un interesante teorema de compacidad , que suele llevar el nombre de Andrzej Ehrenfeucht , establece que un sistema infinito de ecuaciones de palabras, y con un número finito de incógnitas, es necesariamente equivalente a uno de sus subsistemas finitos. ^[17] De ello se deduce que cualquier sistema independiente de ecuaciones de palabras con un número finito de incógnitas es en sí mismo finito. ${\displaystyle S}$ ${\displaystyle E\in S}$ ${\displaystyle E'\in S}$

Expresar lenguajes formales y relaciones

Las ecuaciones de palabras se pueden utilizar para caracterizar propiedades de (tuplas de) palabras. Por ejemplo, una palabra termina en  si y solo si es la imagen  en alguna solución de la ecuación de palabras . De manera similar, dos palabras conmutan si y solo si son las imágenes  en alguna solución de la ecuación de palabras . En este sentido, las ecuaciones de palabras pueden considerarse como mecanismos para expresar lenguajes formales , ^[18] en analogía con los autómatas y las gramáticas formales . No se sabe exactamente qué propiedades de (tuplas de) palabras se pueden expresar mediante ecuaciones de palabras de esta manera. En particular, demostrar que una relación es inexpresable mediante ecuaciones de palabras suele ser bastante desafiante ^[15] . (Un ejemplo de una propiedad inexpresable es " es primitivo " ^[18] ). ${\displaystyle a}$ ${\displaystyle h(x)}$ ${\displaystyle x{\overset {\cdot }{=}}ya}$ ${\displaystyle h(x),h(y)}$ ${\displaystyle xy{\overset {\cdot }{=}}yx}$ ${\displaystyle x}$

También debe notarse que incluso caracterizar el conjunto de soluciones de una ecuación de una sola palabra es complicado. Hmelevskii ^[19] demostró que, aunque las soluciones de ecuaciones libres de constantes con tres incógnitas se pueden dar en términos de expresiones finitas con parámetros de palabras y enteros, esto no es cierto (en general) para ecuaciones libres de constantes con cuatro incógnitas. De hecho,  es un ejemplo de una ecuación de palabras "no parametrizable". ${\displaystyle xyz{\overset {\cdot }{=}}ztx}$

Teorías extendidas y conexiones con la resolución de cuerdas

Se pueden aumentar las ecuaciones de palabras con otros tipos de restricciones sobre los valores , . Por ejemplo, en 1968, Yuri Matiyasevich consideró ^[20] una extensión de las ecuaciones de palabras mediante "restricciones de longitud" como una posible herramienta para mostrar la insolubilidad del décimo problema de Hilbert. Estas restricciones de longitud equivalían a desigualdades lineales en las incógnitas , . A veces, permitir restricciones adicionales (junto con las ecuaciones de palabras) conduce a teorías con problemas de solubilidad indecidibles, pero también es posible agregar restricciones menos poderosas y terminar con una teoría que todavía es decidible. Un ejemplo del primer tipo de restricción es requerir que algunos  sean equivalentes abelianos (es decir, anagramas entre sí) ^[21] ; un ejemplo del último tipo es requerir que algunos  pertenezcan a un lenguaje regular dado . ^[22] Para la extensión de Matiyasevich con las restricciones de longitud, el problema de solubilidad todavía tiene un estado de decidibilidad abierta ^[16] . ${\displaystyle h(x)}$ ${\displaystyle x\in \Xi }$ ${\displaystyle |h(x)|}$ ${\displaystyle x\in \Xi }$ ${\displaystyle h(x),h(y)}$ ${\displaystyle h(x)}$ ${\displaystyle L}$

Recientemente, ha habido un interés en la teoría de ecuaciones de palabras (y teorías más generales basadas en ella), desde el punto de vista práctico de quienes desarrollan herramientas de verificación de software llamadas solucionadores de cadenas . ^[23] Estas herramientas, que son cada vez más populares, ^[24] buscan resolver algorítmicamente problemas de satisfacción de restricciones sobre cadenas. Tales problemas toman la forma de un conjunto de restricciones, que un conjunto desconocido de cadenas debe satisfacer. El solucionador de cadenas debe determinar entonces si existen cadenas que satisfagan todas las restricciones dadas. Un objetivo típico de una herramienta de este tipo sería garantizar que una pieza particular de software esté libre de alguna vulnerabilidad relacionada con las cadenas, como secuencias de comandos entre sitios o inyección de código . ^[25]

Los componentes básicos de las restricciones utilizadas en estas herramientas son las preguntas estándar que uno podría hacer sobre las cadenas, como "¿es  una subcadena de ?", "¿cuál es la longitud de la cadena ?" y "¿cuál es el índice de la cadena  en la cadena ?" ^[24] . Ostensiblemente, estas restricciones se pueden modelar mediante teorías basadas en ecuaciones de palabras y, como tal, las herramientas de resolución de cadenas deben ser capaces de tratar con estas teorías algorítmicamente (al menos en el subcaso de aquellas ecuaciones y fórmulas que realmente surgen en la práctica). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

Relación con el efecto del defecto

El teorema del defecto es un resultado central de la combinatoria de palabras. ^{[4] [5]} . Dice que, si un conjunto  de palabras satisface una relación no trivial, entonces las palabras de  pueden expresarse (simultáneamente) como potencias de  palabras, donde . Se dice entonces que un conjunto de este tipo  posee un "efecto de defecto" de orden . Los sistemas de ecuaciones de palabras (al menos los "no triviales") expresan el hecho de que un cierto conjunto finito de palabras (a saber, las imágenes  de las incógnitas ), satisfacen alguna(s) relación(es) no trivial(es). Por lo tanto, se puede decir que los sistemas  de ecuaciones de palabras causan un efecto de defecto en los conjuntos de palabras  que provienen de soluciones  de ^[15] . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle |X|-r}$ ${\displaystyle r\geq 1}$ ${\displaystyle X}$ ${\displaystyle r}$ ${\displaystyle h(x)}$ ${\displaystyle x\in \Xi }$ ${\displaystyle S}$ ${\displaystyle X=\{h(x):x\in \Xi \}}$ ${\displaystyle h}$ ${\displaystyle S}$

Se ha estudiado el efecto de defecto causado por ciertos sistemas de ecuaciones de palabras ^[26] y existen algunos resultados sorprendentes al respecto que muestran que las " propiedades de dimensionalidad " de los conjuntos de palabras son en realidad bastante débiles. Por ejemplo, se sabe que aquí existe un sistema independiente  de ecuaciones de tamaño , que contiene  incógnitas, que es tal que  causa solamente un efecto de defecto de orden ^[15] . ${\displaystyle S}$ ${\displaystyle \Omega (n^{2})}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle 1}$

Papel dentro del álgebra abstracta

Se han realizado muchas investigaciones sobre la formulación y resolución de ecuaciones dentro de diferentes estructuras del álgebra abstracta (por ejemplo, grupos y semigrupos ). ^{[27] [28]} Las ecuaciones de palabras, como se presentan aquí, son simplemente ecuaciones en monoides libres . Las ecuaciones en semigrupos libres están estrechamente relacionadas con estas; de hecho, son solo ecuaciones de palabras con el requisito adicional de que el morfismo de la solución  no se borra. También se pueden considerar ecuaciones en grupos libres, aunque la teoría de tales objetos difiere en muchos aspectos de la discusión presentada aquí. Otro resultado de Makanin ^[29] establece que el problema de solubilidad para ecuaciones en grupos libres es nuevamente decidible. ${\displaystyle h}$

Referencias

1. Lothaire, M., ed. (1997). Combinatoria de palabras. Cambridge Mathematical Library (2.ª ed.). Cambridge: Cambridge University Press. doi :10.1017/cbo9780511566097. ISBN 978-0-521-59924-5.
2. Cooper, S. Barry; Cooper, S. Barry (6 de septiembre de 2017). Teoría de la computabilidad. doi :10.1201/9781315275789. ISBN 978-1-315-27578-9.
3. Makanin, GS (28 de febrero de 1977). "El problema de la resolubilidad de ecuaciones en un semigrupo libre". Matemáticas de la URSS-Sbornik . 32 (2): 129–198. Bibcode :1977SbMat..32..129M. doi :10.1070/sm1977v032n02abeh002376. ISSN  0025-5734.
4. Rozenberg, Grzegorz; Salomaa, Arto, eds. (1997). Manual de lenguajes formales. doi :10.1007/978-3-642-59136-5. ISBN 978-3-642-63863-3.
5. Lothaire, M. (2002). Combinatoria algebraica en palabras. Enciclopedia de matemáticas y sus aplicaciones. Cambridge: Cambridge University Press. doi :10.1017/cbo9781107326019. ISBN 978-0-521-81220-7.
6. Berstel, Jean; Karhumäki, Juhani (febrero de 2003). "Combinatoria en palabras: un tutorial" (PDF) . Consultado el 18 de octubre de 2024 .
7. Jeż, Artur (1 de enero de 2016). "Ecuaciones de palabras de una variable en tiempo lineal". Algorithmica . 74 (1): 1–48. doi :10.1007/s00453-014-9931-3. ISSN  1432-0541.
8. Quine, WV (diciembre de 1946). "La concatenación como base para la aritmética". The Journal of Symbolic Logic . 11 (4): 105–114. doi :10.2307/2268308. ISSN  0022-4812. JSTOR  2268308.
9. Markov, AA; Nagornyĭ, NM (1988). La teoría de algoritmos . Matemáticas y sus aplicaciones (serie soviética) (en inglés y ruso). Dordrecht; Boston: Kluwer Academic. ISBN 978-90-277-2773-2.
10. Obono, S. Eyono; Goralcik, P.; Maksimenko, M. (1994). "Resolución eficiente de ecuaciones verbales en una variable". En Prívara, Igor; Rovan, Branislav; Ruzička, Peter (eds.). Fundamentos matemáticos de la informática 1994. Apuntes de clase en informática. Vol. 841. Berlín, Heidelberg: Springer. págs. 336–341. doi :10.1007/3-540-58338-6_80. ISBN 978-3-540-48663-3.
11. Berstel, Jean; Perrin, Dominique (1 de abril de 2007). "Los orígenes de la combinatoria en palabras". Revista Europea de Combinatoria . 28 (3): 996–1022. doi :10.1016/j.ejc.2005.07.019. ISSN  0195-6698.
12. Kościelski, Antoni; Pacholski, Leszek (1 de julio de 1996). "Complejidad del algoritmo de Makanin". J. ACM . 43 (4): 670–684. doi :10.1145/234533.234543. ISSN  0004-5411.
13. Plandowski, W. (1999). "La satisfacibilidad de ecuaciones de palabras con constantes está en PSPACE". 40.º Simposio anual sobre fundamentos de la informática (Cat. No.99CB37039) . IEEE Comput. Soc. pp. 495–500. doi :10.1109/SFFCS.1999.814622. ISBN 978-0-7695-0409-4.
14. Plandowski, Wojciech; Rytter, Wojciech (1998). "Aplicación de las codificaciones Lempel-Ziv a la solución de ecuaciones de palabras". En Larsen, Kim G.; Skyum, Sven; Winskel, Glynn (eds.). Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 1443. Berlín, Heidelberg: Springer. págs. 731–742. doi :10.1007/BFb0055097. ISBN. 978-3-540-68681-1.
15. Karhumäki, Juhani. «Combinatoria de Palabras» (PDF) . Consultado el 18 de octubre de 2024 .
16. Lin, Anthony W.; Majumdar, Rupak (29 de octubre de 2021). "Ecuaciones de palabras cuadráticas con restricciones de longitud, sistemas de contadores y aritmética de Presburger con divisibilidad". Métodos lógicos en informática . 17 (4). doi :10.46298/lmcs-17(4:4)2021. ISSN  1860-5974.
17. Albert, MH; Lawrence, J. (1 de enero de 1985). "Una prueba de la conjetura de Ehrenfeucht". Ciencias de la computación teórica . 41 : 121–123. doi :10.1016/0304-3975(85)90066-0. ISSN  0304-3975.
18. Karhumäki, Juhani; Mignosi, Filippo; Plandowski, Wojciech (1 de mayo de 2000). "La expresividad de los lenguajes y las relaciones mediante ecuaciones de palabras". J. ACM . 47 (3): 483–505. doi :10.1145/337244.337255. ISSN  0004-5411.
19. Chmelevskij, Jurij I.; Chmelevskij, Jurij I. (1976). Ecuaciones en semigrupos libres . Actas del Instituto Steklov de Matemáticas. Providence, RI: American Mathematical Soc. ISBN 978-0-8218-3007-9.
20. Matiyasevich, Yuri (1968). "СВЯЗЬ СИСТЕМ УРАВНЕНИЙ В СЛОВАХ И ДЛИНАХ С 10-Й ПРОБЛЕМОЙ ГИЛЬБЕРТА" (PDF) . Math-Net.Ru . Consultado el 19 de octubre de 2024 .
21. Day, Joel D.; Ganesh, Vijay; He, Paul; Manea, Florin; Nowotka, Dirk (2018). "La satisfacibilidad de las ecuaciones de palabras: teorías decidibles e indecidibles". En Potapov, Igor; Reynier, Pierre-Alain (eds.). Problemas de accesibilidad . Apuntes de clase en informática. Vol. 11123. Cham: Springer International Publishing. págs. 15–29. doi :10.1007/978-3-030-00250-3_2. ISBN 978-3-030-00250-3.
22. Diekert, Volker; Gutierrez, Claudio; Hagenah, Christian (1 de noviembre de 2005). "La teoría existencial de ecuaciones con restricciones racionales en grupos libres es PSPACE-completa". Información y computación . 202 (2): 105–140. doi :10.1016/j.ic.2005.04.002. ISSN  0890-5401.
23. Lin, Anthony W.; Barceló, Pablo (11 de enero de 2016). "Resolución de cadenas con ecuaciones de palabras y transductores: hacia una lógica para analizar mutaciones XSS". SIGPLAN No. 51 ( 1): 123–136. doi :10.1145/2914770.2837641. ISSN  0362-1340.
24. Amadini, Roberto (23 de noviembre de 2021). "Una encuesta sobre la resolución de restricciones de cadenas". ACM Comput. Surv . 55 (1): 16:1–16:38. doi :10.1145/3484198. hdl :11585/850408. ISSN  0360-0300.
25. Thome, Julian; Shar, Lwin Khin; Bianculli, Domenico; Briand, Lionel (2017). "Resolución de restricciones de cadenas impulsada por búsquedas para la detección de vulnerabilidades". 2017 IEEE/ACM 39th International Conference on Software Engineering (ICSE). IEEE. págs. 198–208. doi :10.1109/ICSE.2017.26. ISBN . 978-1-5386-3868-2.
26. Karhumäki, Juhani; Plandowski, Wojciech (1994), "Sobre el efecto de defecto de muchas identidades en semigrupos libres", Aspectos matemáticos de los lenguajes naturales y formales , World Scientific, págs. 225-232, doi :10.1142/9789814447133_0012, ISBN 978-981-02-1914-7, consultado el 19 de octubre de 2024
27. Ciobanu, Laura; Holt, Derek; Rees, Sarah (1 de marzo de 2020). "Ecuaciones en grupos que son productos prácticamente directos". Journal of Algebra . Número especial en memoria de Charles Sims. 545 : 88–99. doi :10.1016/j.jalgebra.2018.10.044. ISSN  0021-8693.
28. Schiek, Helmut (1 de enero de 1973), Boone, WW; Cannonito, FB; Lyndon, RC (eds.), "Ecuaciones sobre grupos", Estudios de lógica y fundamentos de las matemáticas , Problemas de palabras, vol. 71, Elsevier, págs. 563–567, doi :10.1016/s0049-237x(08)71920-7, ISBN 978-0-7204-2271-9, consultado el 19 de octubre de 2024
29. Makanin, GS (30 de junio de 1983). "Ecuaciones en un grupo libre". Matemáticas de la URSS-Izvestia . 21 (3): 483–546. Código Bibliográfico :1983IzMat..21..483M. doi :10.1070/IM1983v021n03ABEH001803. ISSN  0025-5726.