Igenkännlig uppsättning

Inom datavetenskap , närmare bestämt inom automatteorin , är en igenkännbar uppsättning av en monoid en delmängd som kan särskiljas av någon morfism till en finit monoid. Igenkännbara uppsättningar är användbara i automatteori, formella språk och algebra .

Denna föreställning skiljer sig från föreställningen om igenkännbart språk . I själva verket har termen "igenkännbar" en annan betydelse i beräkningsbarhetsteorin .

Definition

Låt $N$ vara en monoid , en delmängd $S\subseteq N$ känns igen av en monoid $M$ om det finns en morfism $\phi$ från $N$ till $M$ så att ${\displaystyle S=\phi ^{-1}(\phi (S))} ,$ och känns igen om det är igenkänd av någon finit monoid. Detta betyder att det finns en delmängd $T$ av $M$ (inte nödvändigtvis en submonoid av $M$ ) så att bilden av $S$ är i $T$ och bilden av $N\setminus S$ är i $M\setminus T$ .

Exempel

Låt $A$ vara ett alfabet : mängden $A^{*}$ av ord över $A$ är en monoid, den fria monoiden på $A$ . De igenkännbara delmängderna av $A^{*}$ är just de vanliga språken . Faktum är att ett sådant språk känns igen av övergångsmonoiden hos vilken automat som helst som känner igen språket.

De igenkännbara delmängderna av $\mathbb {N}$ är de slutligen periodiska uppsättningarna av heltal.

Egenskaper

En delmängd av $N$ är igenkännbar om och endast om dess syntaktiska monoid är ändlig.

Uppsättningen $\mathrm {REC} (N)$ av igenkännbara delmängder av $N$ stängs under:

Mezeis sats ^{[ citat behövs ]} säger att om $M$ är produkten av monoiderna $M_{1},\dots ,M_{n}$ , då en delmängd av $M$ känns igen om och endast om det är en finit union av delmängder av formen ${\displaystyle R_{1}\times \cdots \times R_{n}} ,$ där varje $R_{i}$ är en identifierbar delmängd av $M_{i}$ . Till exempel är delmängden $\{1\}$ av $\mathbb {N}$ rationell och därför igenkännbar, eftersom $\mathbb {N}$ är en fri monoid. Det följer att delmängden $S=\{(1,1)\}$ av $\mathbb {N} ^{2}$ är igenkännbar.

McKnights teorem ^{[ citat behövs ]} säger att om $N$ genereras ändligt så är dess igenkännbara delmängder rationella delmä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.

Omvänt kanske en rationell delmängd inte går att känna igen, även om $N$ genereras ändligt. I själva verket är inte ens en ändlig delmängd av $N$ nödvändigtvis igenkännbar. Till exempel är uppsättningen $\{0\}$ inte en identifierbar delmängd av $(\mathbb {Z} ,+)$ . Om en morfism $\phi$ från $\mathbb {Z}$ till $M$ uppfyller ${\displaystyle \{0 \}=\phi ^{-1}(\phi (\{0\}))} ,$ då är $\phi$ en injektiv funktion , därför är $M$ oändlig.

I allmänhet är $\mathrm {REC} (N)$ inte stängd under Kleene star . Till exempel är mängden $S=\{(1,1)\}$ en igenkännbar delmängd av $\mathbb {N} ^{2}$ , men $S^{*}=\{(n,n)\mid n\in \mathbb {N} \}$ går inte att känna igen. Dess syntaktiska monoid är faktiskt oändlig.

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

Igenkännbara uppsättningar är stängda under invers av morfismer. Dvs om $N$ och $M$ är monoider och $\phi :N\rightarrow M$ är en morfism då om $S\in \mathrm {REC} (M)$ sedan $\phi ^{-1}(S) =\{x\mid \phi (x)\in S\}\in \mathrm {REC} (N)$ .

För ändliga grupper är följande resultat av Anissimov och 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.

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-Eric Pin, Mathematical Foundations of Automata Theory , Kapitel IV: Igenkännbara och rationella uppsättningar

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 .