Rationell uppsättning

Inom datavetenskap , närmare bestämt inom automatteorin , är en rationell uppsättning av en monoid en del av den minimala klassen av delmängder av denna monoid som innehåller alla finita delmängder och är stängd under union , produkt och Kleene stjärna . Rationella mängder är användbara i automatteori , formella språk och algebra .

En rationell uppsättning generaliserar begreppet rationellt (reguljärt) språk (uppfattat som definierat av reguljära uttryck ) till monoider som inte nödvändigtvis är fria . ^{[ exempel behövs ]}

Definition

Låt $(N,\cdot )$ vara en monoid med identitetselement $e$ . Mängden $\mathrm {RAT} (N)$ av rationella delmängder av $N$ är den minsta mängden som innehåller varje ändlig mängd och stängs under

union : om $A,B\in \mathrm {RAT} (N)$ A $\displaystyle A\cup B\in \mathrm {RAT} (N)}$
produkt: om $A,B\in \mathrm {RAT} (N)$ så är $A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)$
Kleene stjärna : om $A\in \mathrm {RAT} (N)$ så ${\displaystyle A^{ *}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)} där A = { e } {\displaystyle$ A $e \}}$ är singeln som innehåller identitetselementet, och där $A^{n+1}=A^{n}\cdot A$ .

Detta betyder att vilken rationell delmängd som helst av $N$ kan erhållas genom att ta ett ändligt antal ändliga delmängder av $N$ och tillämpa unions-, produkt- och Kleene-stjärnoperationerna ett ändligt antal gånger.

I allmänhet är en rationell delmängd av en monoid inte en submonoid.

Exempel

Låt $A$ vara ett alfabet , mängden $A^{*}$ av ord över $A$ är en monoid. Den rationella delmängden av $A^{*}$ är just de reguljära språken . De reguljära språken kan faktiskt definieras av ett ändligt reguljärt uttryck .

De rationella delmängderna av $\mathbb {N}$ är de ytterst periodiska uppsättningarna av heltal. Mer generellt är de rationella delmängderna av $\mathbb {N} ^{k}$ de semilinjära mängderna .

Egenskaper

McKnights teorem säger att om $N$ genereras ändligt så är dess igenkännbara delmängd rationella mängder. Detta är inte sant i allmänhet, eftersom hela $N$ alltid är igenkännbar men det är inte rationellt om $N$ genereras oändligt.

Rationella mängder är slutna under morfism: givet $N$ och $M$ två monoider och $\phi :N\rightarrow M$ en morfism, om $S\in \mathrm {RAT} (N)$ sedan $\phi (S)=\ {\phi (x)\mid x\in S\}\in \mathrm {RAT} (M)$ .

$\mathrm {RAT} (N)$ är inte stängd under komplement som följande exempel visar. Låt ${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}} ,$ mängderna $R=(a,b)^{*}(1,c)^{*} =\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}$ och ${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(a^{n },b^{m}c^{n})\mid n,m\in \mathbb {N} \}} är$ rationella men ${\displaystyle R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}} beror inte på att dess projektion till det andra$ elementet ${\displaystyle \{b^{n}c^{n}\mid n\in \mathbb {N} \}} är$ inte rationell.

Skärningen mellan en rationell delmängd och en igenkännbar delmängd är rationell.

För ändliga grupper är följande resultat av A. Anissimov och AW Seifert välkänt: en undergrupp H av en ändligt genererad grupp G är igenkännbar om och endast om H har ändligt index i G . Däremot H rationell om och endast om H genereras ändligt.

Rationella relationer och rationella funktioner

En binär relation mellan monoider M och N är en rationell relation om grafen för relationen, betraktad som en delmängd av M × N , är en rationell mängd i produktens monoid. En funktion från M till N är en rationell funktion om grafen för funktionen är en rationell mängd.

Se även

Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Kapitel 7: Automater". Diskreta algebraiska metoder . Berlin/Boston: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8 .
Jean-Éric Pin , Mathematical Foundations of Automatateory , Kapitel IV: Igenkännbara och rationella uppsättningar
Samuel Eilenberg och MP Schützenberger, Rational Sets in Commutative Monoids , Journal of Algebra, 1969.

Vidare läsning

Sakarovitch, Jacques (2009). Element i automatteorin . Översatt från franskan av Reuben Thomas. Cambridge: Cambridge University Press. Del II: Kraften i algebra. ISBN 978-0-521-84425-3 . Zbl 1188.68177 .