Conjunto reconocible

En informática , más precisamente en la teoría de autómatas , un conjunto reconocible de un monoide es un subconjunto que puede distinguirse mediante algún homomorfismo a un monoide finito. Los conjuntos reconocibles son útiles en la teoría de autómatas, los lenguajes formales y el á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 .

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

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

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

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

El conjunto${\displaystyle \mathrm {REC} (N)}$de subconjuntos reconocibles de${\displaystyle N}$está cerrado bajo:

• unión
• intersección
• complementar
• cociente derecha e izquierda

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

El teorema de McKnight establece que si${\displaystyle N}$Si es finitamente generado, entonces sus subconjuntos reconocibles son subconjuntos racionales . Esto no es cierto en general, ya que todo${\displaystyle N}$siempre es reconocible pero no es racional si${\displaystyle N}$se genera infinitamente.

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

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

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

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

Para grupos finitos, es bien conocido el siguiente resultado de Anissimov y Seifert: un subgrupo H de un grupo G finitamente generado es reconocible si y solo si H tiene índice finito en G. Por el contrario, H es racional si y solo si H es finitamente generado. ^{[ 1 ]}

• Conjunto racional
• Monoide racional

• 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 autómatas , Capítulo IV: Conjuntos reconocibles y racionales

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