Conjunto reconocible

En informática , más precisamente en teoría de autómatas , un conjunto reconocible de un monoide es un subconjunto que puede distinguirse por algún homomorfismo con respecto a un monoide finito. Los conjuntos reconocibles son útiles en teoría de autómatas, lenguajes formales y álgebra .

Esta noción es diferente de la noción de lenguaje reconocible . De hecho, el término "reconocible" tiene un significado diferente en la teoría de la computabilidad .

Definición

Sea un monoide , un subconjunto es reconocido por un monoide si existe un homomorfismo de a tal que , y reconocible si es reconocido por algún monoide finito. Esto significa que existe un subconjunto de (no necesariamente un submonoide de ) tal que la imagen de está en y la imagen de está en . ${\displaystyle N}$ ${\displaystyle S\subseteq N}$ ${\displaystyle M}$ ${\displaystyle \phi }$ ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle S=\phi ^{-1}(\phi (S))}$ ${\displaystyle T}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle N\setminus S}$ ${\displaystyle M\setminus T}$

Ejemplo

Sea un alfabeto : el conjunto de palabras de arriba es un monoide, el monoide libre de . Los subconjuntos reconocibles de son precisamente los lenguajes regulares . De hecho, dicho lenguaje es reconocido por el monoide de transición de cualquier autómata que reconozca el lenguaje. ${\displaystyle A}$ ${\displaystyle A^{*}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A^{*}}$

Los subconjuntos reconocibles de son los conjuntos de números enteros, en última instancia, periódicos. ${\displaystyle \mathbb {N} }$

Propiedades

Un subconjunto de es reconocible si y sólo si su monoide sintáctico es finito. ${\displaystyle N}$

El conjunto de subconjuntos reconocibles de se cierra en: ${\displaystyle \mathrm {REC} (N)}$ ${\displaystyle N}$

• Unión
• intersección
• complementar
• cociente derecho e izquierdo

El teorema de Mezei ^{[ cita requerida ]} establece que si es el producto de los monoides , entonces un subconjunto de es reconocible si y sólo si es una unión finita de subconjuntos de la forma , donde cada uno es un subconjunto reconocible de . Por ejemplo, el subconjunto de es racional y, por tanto, reconocible, ya que es un monoide libre. De ello se deduce que el subconjunto de es reconocible. ${\displaystyle M}$ ${\displaystyle M_{1},\dots ,M_{n}}$ ${\displaystyle M}$ ${\displaystyle R_{1}\times \cdots \times R_{n}}$ ${\displaystyle R_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle \{1\}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle S=\{(1,1)\}}$ ${\displaystyle \mathbb {N} ^{2}}$

El teorema de McKnight ^{[ cita necesaria ]} establece que si se genera de forma finita , entonces sus subconjuntos reconocibles son subconjuntos racionales . Esto no es cierto en general, ya que el todo es siempre reconocible pero no es racional si se genera infinitamente. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$

Por el contrario, un subconjunto racional puede no ser reconocible, incluso si se genera de forma finita. De hecho, incluso un subconjunto finito de no es necesariamente reconocible. Por ejemplo, el conjunto no es un subconjunto reconocible de . De hecho, si un homomorfismo de a satisface , entonces es una función inyectiva ; por tanto es infinito. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle \{0\}}$ ${\displaystyle (\mathbb {Z} ,+)}$ ${\displaystyle \phi }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle M}$ ${\displaystyle \{0\}=\phi ^{-1}(\phi (\{0\}))}$ ${\displaystyle \phi }$ ${\displaystyle M}$

Además, en general, no está cerrado bajo la estrella Kleene . Por ejemplo, el conjunto es un subconjunto reconocible de , pero no es reconocible. De hecho, su monoide sintáctico es infinito. ${\displaystyle \mathrm {REC} (N)}$ ${\displaystyle S=\{(1,1)\}}$ ${\displaystyle \mathbb {N} ^{2}}$ ${\displaystyle S^{*}=\{(n,n)\mid n\in \mathbb {N} \}}$

La intersección de un subconjunto racional y de un subconjunto reconocible es racional.

Los conjuntos reconocibles están cerrados bajo homomorfismos inversos. Es decir, si y son monoides y es un homomorfismo entonces si entonces . ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle \phi :N\rightarrow M}$ ${\displaystyle S\in \mathrm {REC} (M)}$ ${\displaystyle \phi ^{-1}(S)=\{x\mid \phi (x)\in S\}\in \mathrm {REC} (N)}$

Para grupos finitos, el siguiente resultado de Anissimov y Seifert es bien conocido: un subgrupo H de un grupo G generado finitamente es reconocible si y sólo si H tiene un índice finito en G. Por el contrario, H es racional si y sólo si H se genera de forma finita. ^[1]

Ver también

• conjunto racional
• monoide racional

Referencias

1. John Meakin (2007). "Grupos y semigrupos: conexiones y contrastes". En CM Campbell; Señor Rápido; EF Robertson; GC Smith (eds.). Grupos St Andrews 2005 Volumen 2 . Prensa de la Universidad de Cambridge. pag. 376.ISBN​ 978-0-521-69470-4.preimpresión

• Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Capítulo 7: Autómatas". Métodos algebraicos discretos . Berlín/Bostón: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8.
• Jean-Éric Pin , Fundamentos matemáticos de la teoría de los autómatas, Capítulo IV: Conjuntos reconocibles y racionales

Otras lecturas

• Sakarovich, Jacques (2009). Elementos de la teoría de los autómatas . Traducido del francés por Reuben Thomas. Cambridge: Prensa de la Universidad de Cambridge. Parte II: El poder del álgebra. ISBN 978-0-521-84425-3. Zbl  1188.68177.