conjunto racional

En informática , más precisamente en 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 está cerrado bajo unión , producto y estrella de Kleene . Los conjuntos racionales son útiles en teoría de autómatas , lenguajes formales y álgebra .

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

Definición

Sea un monoide con elemento de identidad . El conjunto de subconjuntos racionales de es el conjunto más pequeño que contiene todo conjunto finito y está cerrado bajo ${\displaystyle (N,\cdot )}$ ${\displaystyle e}$ ${\displaystyle \mathrm {RAT} (N)}$ ${\displaystyle N}$

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

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

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

Ejemplo

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

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

Propiedades

El teorema de McKnight establece que si se genera de forma finita, entonces su subconjunto reconocible son conjuntos 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}$

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

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

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

Para grupos finitos, el siguiente resultado de A. Anissimov y AW 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. ^[3]

Relaciones racionales y funciones racionales.

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

Ver también

• Serie racional
• Conjunto reconocible
• monoide racional

Referencias

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

1. Fundamentos matemáticos de la teoría de los autómatas
2. cf. Jean-Éric Pin, Fundamentos matemáticos de la teoría de los autómatas, p. 76, Ejemplo 1.3
3. 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
4. Hoffman, Michael; Kuske, Dietrich; Otto, Federico; Thomas, Richard M. (2002). "Algunos familiares de grupos automáticos e hiperbólicos". En Gomes, Gracinda MS (ed.). Semigrupos, algoritmos, autómatas y lenguajes. Actas de talleres realizados en el Centro Internacional de Matemáticas, CIM, Coimbra, Portugal, mayo, junio y julio de 2001 . Singapur: World Scientific. págs. 379–406. Zbl  1031.20047.

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.