Conjunto racional

En informática , más precisamente en la teoría de autómatas , un conjunto racional de un monoide es un elemento de la clase mínima de subconjuntos de este monoide que contiene todos los subconjuntos finitos y es cerrado bajo la unión , el producto y la estrella de Kleene . Los conjuntos racionales son útiles en la teoría de autómatas , los lenguajes formales y el álgebra .

Un conjunto racional generaliza la noción de lenguaje racional (o regular) (entendido como definido por expresiones regulares ) a monoides que no son necesariamente libres .

Dejar${\displaystyle (N,\cdot )}$ser un monoide con elemento identidad${\displaystyle e}$. El conjunto${\displaystyle \mathrm {RAT} (N)}$de subconjuntos racionales de${\displaystyle N}$es el conjunto más pequeño que contiene a todos los conjuntos finitos y es cerrado bajo

• unión : si${\displaystyle A,B\in \mathrm {RAT} (N)}$entonces${\displaystyle A\cup B\in \mathrm {RAT} (N)}$
• producto: si${\displaystyle A,B\in \mathrm {RAT} (N)}$entonces${\displaystyle A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)}$
• Estrella Kleene : si${\displaystyle A\in \mathrm {RAT} (N)}$entonces${\displaystyle A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)}$dónde${\displaystyle A^{0}=\{e\}}$es el singleton que contiene el elemento identidad , y donde${\displaystyle A^{n+1}=A^{n}\cdot A}$.

Esto significa que cualquier subconjunto racional de${\displaystyle N}$se puede obtener tomando un número finito de subconjuntos finitos de${\displaystyle N}$y aplicando las operaciones de unión, producto y estrella de Kleene un número finito de veces.

En general, un subconjunto racional de un monoide no es un submonoide.

Dejar${\displaystyle A}$ser un alfabeto , el conjunto${\displaystyle A^{*}}$de palabras sobre${\displaystyle A}$es un monoide. El subconjunto racional de${\displaystyle A^{*}}$son precisamente los lenguajes regulares . De hecho, los lenguajes regulares pueden definirse mediante una expresión regular finita .

Los subconjuntos racionales de${\displaystyle \mathbb {N} }$son los conjuntos de enteros en última instancia periódicos. Más generalmente, los subconjuntos racionales de${\displaystyle \mathbb {N} ^{k}}$son los conjuntos semilineales . ^{[ 1 ]}

El teorema de McKnight establece que si${\displaystyle N}$Si es finitamente generado, entonces su subconjunto reconocible son conjuntos 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.

Los conjuntos racionales son cerrados bajo homomorfismo: dado${\displaystyle N}$y${\displaystyle M}$dos monoides y${\displaystyle \phi :N\rightarrow M}$un homomorfismo monoide, si${\displaystyle S\in \mathrm {RAT} (N)}$entonces${\displaystyle \phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {RAT} (M)}$.

${\displaystyle \mathrm {RAT} (N)}$no es cerrado bajo complemento como muestra el siguiente ejemplo. ^{[ 2 ]} Sea${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}}$, los conjuntos ${\displaystyle R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}}$y${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(a^{n},b^{m}c^{n})\mid n,m\in \mathbb {N} \}}$son racionales pero${\displaystyle R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}}$no es porque su proyección al segundo elemento${\displaystyle \{b^{n}c^{n}\mid n\in \mathbb {N} \}}$no es racional.

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

Para grupos finitos, es bien conocido el siguiente resultado de A. Anissimov y A. W. 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. ^{[ 3 ]}

Una relación binaria entre monoides M y N es una relación racional si la gráfica de dicha relación, considerada como un subconjunto de M × N, es un conjunto racional en el monoide producto. Una función de M a N es una función racional si la gráfica de dicha función es un conjunto racional. ^{[ 4 ]}

• Series racionales
• Conjunto reconocible
• 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
• Samuel Eilenberg y Marcel-Paul Schützenberger , Conjuntos racionales en monoides conmutativos , Journal of Algebra , 1969.

• 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 .