Signalautomat

Inom automatteori , ett område inom datavetenskap , är en signalautomat en finit automat utökad med en finit uppsättning klockor med verkligt värde. Under körning av en signalautomat ökar klockvärdena alla med samma hastighet. Längs automatens övergångar kan klockvärden jämföras med heltal. Dessa jämförelser bildar skydd som kan aktivera eller inaktivera övergångar och genom att göra det begränsar automatens möjliga beteenden. Vidare kan klockor återställas.

Exempel

Innan man formellt definierar vad en signalautomat är kommer ett exempel att ges. Låt oss betrakta språket ${\mathcal {L}}$ för signaler, över ett binärt alfabet $\{A,B\}$ , som innehåller signalerna $\gamma$ så att:

• $A$ visas i singulära intervall. Det vill säga uppsättningen av tider $\{t\mid \gamma (t)=A\}$ är diskret, och
• $A$ visas minst en gång under varje intervall med längd ett.

Detta språk kan accepteras av automaten på bilden i närheten.

En signalautomat som säkerställer att A håller diskret och minst en gång per tidsenhet

När det gäller finita automater, representerar inkommande pilar initiala platser och dubbel cirkel representerar accepterande platser. Men i motsats till finita automater förekommer bokstäver på platser och inte i övergång. Detta beror på att bokstäver sänds ut kontinuerligt och övergångar tas diskret. Symbolen $x$ representerar en klocka . Denna klocka gör det möjligt att mäta tiden sedan senaste gången då $A$ sändes ut. Således säkerställer ${\displaystyle x=0} att$$A$ sänds ut diskret. Och $1>x$ säkerställer att inte mer än en tidsenhet kan passera utan att $A$ inträffar.

Formell definition

Signalautomat

Formellt är en signalautomat en tuppel ${\mathcal {A}}=\langle \Sigma ,L,L_{0}, C,F,\alpha ,\beta ,E\rangle$ som består av följande komponenter:

• $\Sigma$ är en ändlig mängd som kallas alfabetet eller åtgärderna för ${\mathcal {A}}$ .
• $L$ är en ändlig mängd . Elementen i $L$ kallas platserna eller tillstånden för ${\mathcal {A}}$ .
• $C$ är en ändlig mängd som kallas klockorna för ${\mathcal {A}}$ .
• $L_{0}\subseteq L$ är uppsättningen startplatser.
• $F\subseteq L$ är uppsättningen av accepterande platser.
• $\alpha :L\to \Sigma$ som associerar en bokstav till varje plats.
• $\beta :L\to {\mathcal {B}}(C)$ som associerar en klockrestriktioner till varje plats, och
• $E\subseteq L\times {\mathcal {P}}(C)\times L$ är en uppsättning kanter som kallas övergångar av ${\mathcal { A}}$ , där
  • ${\mathcal {P}}(C)$ är kraftmängden för $C$ .

En kant $(\ell ,r,\ell ')$ från $E$ är en övergång från platser $\ell$ till $\ ell '$ som återställer klockorna för $r$ .

Förlängt tillstånd

Ett par med en plats $\ell$ och en klockvärdering $\nu$ kallas antingen ett utökat tillstånd eller ett tillstånd .

Observera att ordet tillstånd alltså är tvetydigt, eftersom det, beroende på författaren, kan betyda antingen ett par eller ett element av $L$ . För tydlighetens skull kommer denna artikel att använda termen plats för element i $L$ och termen utökad plats för par.

Här ligger en av de största skillnaderna mellan signalautomater och finita automater . I en ändlig automat, vid någon punkt av exekveringen, beskrivs tillståndet helt av antalet lästa bokstäver och av ett ändligt antal möjliga värden, som egentligen kallas "tillstånd". Det betyder att, givet ett tillstånd och ett suffix av ordet som ska läsas, bestäms återstoden av körningen helt. Alltså ordet "ändlig" i namnet "ändlig automat". Men, som det förklaras i avsnittet "kör" nedan, för att återuppta används klockor för att bestämma vilka övergångar som kan tas. För att veta tillståndet för automaten måste du alltså både nu på vilken plats du befinner dig och klockvärderingen.

Springa

När det gäller finita automater är en körning i huvudsak en sekvens av platser, så att det finns en övergång mellan två platser. Två skillnader måste dock betonas. Bokstaven bestäms inte av övergången utan av platserna; detta beror på att bokstäverna sänds ut kontinuerligt medan övergångar tas diskret. Det går en tid när man befinner sig på en plats; klockbegränsningarna som anger en plats eller dess efterföljare kan begränsa tiden som spenderas på en enda plats.

En körning är en sekvens av formen ${\displaystyle {\xrightarrow[{\nu _{0}}]{C}}( \ell _{0},I_{0}){\xrightarrow[{\nu _{1}}]{r_{1}}}(\ell _{1},I_{1})\dots } uppfyller$ vissa begränsningar. Innan dessa begränsningar anges, introduceras några notationer. Sekvenserna är diskreta men representerar kontinuerliga händelser. En kontinuerlig version av sekvenserna $(\sigma _{i})$ , $(\nu _{i})$ , $(\ell _{i})$ introduceras nu. Låt $i\geq 0$ integral och ${\displaystyle t\in I_{i}} ,$ sedan

• låt $\sigma '_{t}$ vara lika med $\sigma _{i}$ ,
• låt $\nu '_{t}$ vara $\nu _{i}+t-\lceil I_{i}\rceil$ med $\lceil I_{i}\rceil$ är den nedre gränsen för intervallet $I_{i}$ ,
• låt $\ell '_{t}=\ell _{i}$ .

De begränsningar som uppfylls av körning är, för varje $i\geq 0$ integral och $t\geq 0$ reell:

• $\ell _{0}\in L_{0}$ ,
• $(\ell _{i},r_{i},\ell _{i+1})\in E$ ,
• $\nu _{i+1}=(\nu _{i}+\mid I_{i}\mid )[r_ {i}\rightarrow 0]$ ,
• $\nu '_{t}\models \beta (\ell '_{t})$ .

Signalen som definieras av denna körning är funktionen $\sigma '$ definierad ovan. Det sägs att körningen definierad ovan är en körning för signalen $\sigma '$ .

Begreppet att acceptera körning definieras som i finita automater för finita ord och som i Büchi automata för oändliga ord. Det vill säga om $w$ är ändlig av längden $n$ , så accepterar körningen om $\ell _{n}\in F$ . Om ordet är oändligt, så accepterar körningen om och endast om det finns ett oändligt antal positioner $i$ så att $\ell _{i}\in F$ .

Accepterade signaler och språk

En signal $\gamma$ sägs accepteras av en signalautomat ${\mathcal {A}}$ om det finns en körning av ${\mathcal {A}}$ på $\gamma$ accepterar det. Uppsättningen signaler som accepteras av ${\mathcal {A}}$ kallas språket som accepteras av ${\mathcal {A}}$ och betecknas med ${\mathcal {S(A)}}$ .

Deterministisk signalautomat

Som i fallet med finita och Büchi-automater kan en signalautomat vara deterministisk eller icke-deterministisk. Intuitivt, att vara deterministisk med samma betydelse i vart och ett av dessa fall. Det betyder att uppsättningen startplatser är en singelton, och att, givet ett utökat tillstånd $s$ och en bokstav $a$ , det bara finns ett möjligt utökat tillstånd som kan nås från ${ \displaystyle s}$ genom att läsa $a$ . Närmare bestämt, antingen är det möjligt att stanna på platsen längre, eller så finns det högst en möjlig efterträdarplats.

Formellt kan detta definieras enligt följande:

• $L_{0}$ är en singelton
• för varje plats $\ell \in L$ , för varje övergång ${\displaystyle (\ell ,r,\ell ')\in E} ,$ de två följande zoner är osammanhängande:
  • zonen som definieras av klockrestriktionen $\beta (\ell )$ ,
  • zonen som definieras av klockrestriktionen $\beta (\ell ')$ där begränsningarna på klockorna för $r$ tas bort,
• för varje plats övergångar $(\ell ,r',\ell ')\in E$ och $(\ ell ,r'',\ell '')\i E$ , de två följande zonerna är disjunkta:
  • zonen som definieras av klockrestriktionen $\beta (\ell ')$ där begränsningarna på klockorna för $r'$ tas bort,
  • zonen som definieras av klockrestriktionen $\beta (\ell '')$ där begränsningarna på klockorna för $r''$ tas bort,

Förenklad signalautomat

Beroende på författarna kan den exakta definitionen av signalautomater vara något annorlunda. Två sådana definitioner ges nu.

Halvöppna intervaller

För att förenkla definitionen av en körning kräver vissa författare att varje intervall i en körning är högerstängd och vänsteröppen. Detta begränsar automater att endast acceptera signaler vars underliggande partition uppfyller samma egenskap. Det säkerställer dock att vid varje tillfälle $t\geq 0$ , $\lim _{t\leftarrow x^{+}}f (x)=f(t)$ för $f$ som representerar någon av funktionerna $\sigma '$ , $\nu '$ eller $\ell '$ infört ovan.

Tvådelad signalautomat

En tvådelad signalautomat är en signalautomat där körningen växlar mellan öppna intervall och singulära intervall (dvs intervall som är singletons). Det säkerställer att grafen som ligger bakom automaten är en tvådelad graf , och således att uppsättningen platser kan delas upp i $\{L^{o},L^{s}\}$ , uppsättningen öppna platser och enstaka platser. Eftersom det första intervallet innehåller 0, kan det inte vara en öppen plats, det följer att $L_{0}\subseteq L^{s}$ . För att säkerställa att varje singular plats verkligen är singular, för varje plats $\ell$ , måste det finnas en klocka $x_{\ell }$ som återställs när $\ell anges$ och så att klockrestriktionen för $\ell$ innehåller $x=0$ .

Vilken signalautomat som helst kan omvandlas till en likvärdig tvådelad signalautomat. Det räcker att ersätta varje plats $\ell$ med ett par platser $(\ell ^{o},\ell ^{s})$ och introducera en ny klocka $x$ , så att för varje $\ell$ , $x_{\ell ^{s}}=x$ .

I närheten visas en tvådelad automat som motsvarar signalautomaten från exempeldelen. Rektangeltillstånd representerar singulära platser.

En tvådelad signalautomat som säkerställer att A håller diskret och åtminstone en gång per tidsenhet

Synkronisering av automater

Begreppet produkt av ändlig automat utvidgas till signalautomat. En sådan produkt kallas dock en synkronisering av automat för att betona det faktum att tiden ska passera på liknande sätt i båda automaterna. Den största skillnaden mellan synkronisering och produkt är att när två ändliga automater läser samma ord tar de övergång samtidigt. Detta är inte fallet längre för signalautomater, eftersom de kan ta övergång vid godtycklig tid. Sålunda kan övergångsrelationen för en signalautomat tillåta att övergång tas i en eller två automater.

Låt ${\mathcal {A}}^{1}=\langle \Sigma ,L^ {1},L_{0}^{1},C^{1},F^{1},\alpha ^{1},\beta ^{1},E^{1}\rangle$ och ${\displaystyle {\mathcal {A}}^{2}=\langle \Sigma ,L^$ två signalautomater, deras synkronisering ${\displaystyle {\mathcal {A}}1\otimes {\mathcal {A}}^{2}=\langle \Sigma ,\{(\ell ^{1},\ell ^{2})\in L ^{1}\otimes L^{2}\mid \alpha ^{1}(\ell ^{1})=\alpha ^{2}(\ell ^{2})\},L_{0}^ {1}\otimes L_{0}^{2},C^{1}\cup C^{2},F^{1}\otimes F^{2},(\ell ^{1},\ell ^{2})\mapsto \alpha ^{1}(\ell ^{1}),(\ell ^{1},\ell ^{2})\mapsto \beta ^{1}(\ell ^{ 1})\land \beta ^{2}(\ell ^{2}),E\rangle } ,$ signalautomaten där $E$ innehåller följande övergångar:

• $((\ell ^{1},\ell ^{2}),r^{1},(\ell ^ {\prime 1},\ell ^{2})$ för $(\ell ^{1},r,\ell ^{\prime 1}) \in E^{1}$ , och på liknande sätt för $E^{2}$ ,
• $((\ell ^{1},\ell ^{2}),r^{1}\ kopp r^{2},(\ell ^{\prime 1},\ell ^{\prime 2})$ för $(\ell ^{1 },r,\ell ^{\prime 1})\in E^{1}$ och $(\ell ^{2},r,\ell ^{\prime 2})\in E^{2}$ .

Skillnad med tidsstyrda automater

Tidsinställda automater är en annan förlängning av finita automater, som lägger till en föreställning om tid till ord. Vi anger nu några av de viktigaste skillnaderna mellan tidsstyrda automater och signalautomater.

I tidsstyrda automater sänds bokstäver ut på övergångarna och inte på platserna. Såsom förklarats ovan när man jämför signalautomater med finita automater, sänds bokstäver vid övergångar när orden sänds ut diskret, som för ord och tidsbestämda ord medan de sänds ut på platser där bokstäver sänds ut kontinuerligt, som för signaler.

I tidsstyrda automater kontrolleras väktare endast vid övergångar. Detta förenklar definitionen av deterministisk automat, eftersom det betyder att begränsningen måste uppfyllas innan klockorna startas om.

Se även

• Tidsinställd automat