Kapslade ord

Inom datavetenskap , närmare bestämt inom automater och formell språkteori , är kapslade ord ett begrepp som föreslås av Alur och Madhusudan som en gemensam generalisering av ord , som traditionellt används för att modellera linjärt ordnade strukturer, och av ordnade orankade träd , som traditionellt används för modellering. hierarkiska strukturer. Finita-tillståndsacceptorer för kapslade ord, så kallade kapslade ordautomater , ger då en mer uttrycksfull generalisering av finita automater på ord. De linjära kodningarna av språk som accepteras av finita kapslade ordautomater ger klassen av synligt pushdown-språk . Den senare språkklassen ligger korrekt mellan de reguljära språken och de deterministiska kontextfria språken . Sedan de introducerades 2004 har dessa begrepp utlöst mycket forskning på området.

Formell definition

För att definiera kapslade ord , definiera först matchande relationer . För ett icke-negativt heltal ${\displaystyle \ell } anger$ notationen $[\ell ]$ mängden $\{1,2, \ldots ,\ell -1,\ell \}$ , med specialfallet $[0]=\emptyset$ .

En matchande relation ↝ av längden $\ell \geq 0$$\{-\infty ,1,2,\ldots ,\ell -1,\ell \}\times \{1,2,\ldots ,\ell -1,\ell ,\infty \ }$ en delmängd av så att:

1. alla häckande kanter är framåt, det vill säga om i ↝ j så är i < j ;
2. häckande kanter har aldrig en ändlig position gemensamt, det vill säga för −∞ < i < ∞ , finns det högst en position h så att h ↝ i , och det finns högst en position j så att i ↝ j ; och
3. häckande kanter korsar sig aldrig, det vill säga det finns inga i < i ≤ j < j ′ så att både i ↝ j och i ′ ↝ j ′ .

En position i kallas

• en samtalsposition , om i ↝ j för något j ,
• ett väntande samtal om jag ↝ ∞,
• en återgångsposition , om h ↝ i under några h ,
• en väntande avkastning om −∞ ↝ i , och
• en intern position i alla återstående fall.

Ett kapslat ord med längden $\ell$ över ett alfabet Σ är ett par ( w ,↝), där w är ett ord, eller sträng , med längden $\ell$ över Σ och ↝ är en matchning relation av längd $\ell$ .

Koda kapslade ord till vanliga ord

Kapslade ord över alfabetet ${\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{n}\}} kan$ kodas till "vanliga" ord över det taggade alfabetet ${\displaystyle {\hat {\Sigma }}} ,$ där varje symbol a från Σ har tre taggade motsvarigheter: symbolen ⟨a för att koda en anropsposition i ett kapslat ord märkt med a , symbolen a⟩ för att koda en returposition märkt med a , och slutligen symbolen a själv för att representera en intern position märkt med en . Mer exakt, låt φ vara funktionen som mappar kapslade ord över Σ till ord över ${\hat {\Sigma }}$ så att varje kapslat ord ( $w_{1} w_{2}\cdots w_{\ell }$ ,↝) mappas till ordet $x_{1}x_{2}...x_{\ell }$ , där bokstaven $x_{i}$ är lika med ⟨a , a och a⟩ , om $w_{i}=a$ och i är en (eventuellt väntande) samtalsposition, en intern position respektive en (eventuellt väntande) returposition.

Exempel

För illustration, låt n = ( w ,↝) vara det kapslade ordet över ett ternärt alfabet med w = abaabccca och matchande relation ↝ = {(−∞,1),(2,∞),(3,4),(5) ,7),(8,∞) }. Sedan läser dess kodning som ord som φ ( n ) = a ⟩⟨ b ⟨ aa ⟩⟨ bcc ⟩⟨ ca .

Automata

Kapslad ordautomat

En kapslad ordautomat har ett ändligt antal tillstånd och fungerar på nästan samma sätt som en deterministisk finit automat på klassiska strängar: en klassisk finit automat läser ingångsordet $w=w_{1 }\cdots w_{\ell }$ från vänster till höger, och tillståndet för automaten efter att ha läst den j :te bokstaven $w_{j}$ beror på i vilket tillstånd automaten var innan den läste ${ \displaystyle w_{j}}$ .

I en kapslad ordautomat kan positionen $j$ i det kapslade ordet (w,↝) vara en returposition; om så är fallet kommer tillståndet efter läsning av $w_{j}$ inte bara att bero på det linjära tillstånd som automaten var i innan läsningen ${\displaystyle w_{j}} ,$ utan också på ett hierarkiskt tillstånd som sprids av automaten när den var i motsvarande anropsposition. I analogi med vanliga ordspråk kallas en uppsättning L av kapslade ord reguljära om den accepteras av någon (finite-state) kapslad ordautomat.

Synligt pushdown-automat

Kapslade ordautomater är en automatmodell som accepterar kapslade ord. Det finns en motsvarande automatmodell som verkar på (vanliga) ord. Begreppet en deterministisk synligt nedskjutningsautomat är nämligen en begränsning av begreppet en deterministisk nedskjutningsautomat .

Efter Alur och Madhusudan definieras en deterministisk synligt pushdown-automat formellt som en 6-tuppel $M=(Q,{\hat {\Sigma }} ,\Gamma ,\delta ,q_{0},F)$ där

• $Q$ är en ändlig uppsättning tillstånd ,
• ${\hat {\Sigma }}$ är inmatningsalfabetet , som – i motsats till det för vanliga pushdown-automater – är uppdelat i tre uppsättningar $\Sigma _{\text{c}}$ , $\Sigma _{\text{r}}$ och $\Sigma _{\text{int}}$ . Alfabetet $\Sigma _{\text{c}}$ betecknar uppsättningen anropssymboler , $\Sigma _{\text{r}}$ innehåller retursymbolerna och mängden $\Sigma _{\text{int}}$ innehåller de interna symbolerna ,
• $\Gamma$ är en ändlig mängd som kallas stackalfabetet , som innehåller en speciell symbol $\bot \in \Gamma$ som anger den tomma stacken,
• $\delta =\delta _{\text{c}}\cup \delta _{\text{r}}\cup \delta _{\text{int}}$ är övergångsfunktionen , som är uppdelad i tre delar som motsvarar samtalsövergångar, returövergångar och interna övergångar, nämligen
  • $\delta _{\text{c}}\colon Q\times \Sigma _{\text{c}}\to Q\times \Gamma$ , anropet övergångsfunktion
  • $\delta _{\text{r}}\colon Q\times \Sigma _{\text{r}}\times \Gamma \to Q$ , returen övergångsfunktion
  • ${\displaystyle \delta _{\text{int}}:Q\times \Sigma _{\text{int}}\to Q} ,$ den interna övergångsfunktionen ,
• $q_{0}\in \,Q$ är initialtillståndet , och
• $F\subseteq Q$ är uppsättningen av accepterande tillstånd .

Begreppet beräkning av en synlig pushdown-automat är en begränsning av den som används för pushdown-automater . Synligt nedskjutningsautomater lägger bara till en symbol till stacken när man läser en samtalssymbol ${\displaystyle a_{\text{c}}\i \Sigma _{\text{c}}} ,$ de tar bara bort toppen element från stacken vid läsning av en retursymbol $a_{\text{r}}\in \Sigma _{\text{r}}$ och de ändrar inte stacken vid läsning av en intern händelse $a_{\text{i}}\in \Sigma _{\text{int}}$ . En beräkning som slutar i ett accepterande tillstånd är en accepterande beräkning .

Som ett resultat kan en synligt nedskjutningsautomat inte trycka till och hoppa från stapeln med samma inmatningssymbol. Språket ${\displaystyle L=\{a^{n}ba^{n}\mid n\in \mathrm {N} \}} kan alltså inte accepteras$ av en synlig nedskjutningsautomat för vilken partition som helst av ${\displaystyle \Sigma } ,$ men det finns pushdown-automater som accepterar detta språk.

Om ett språk $L$ över ett taggat alfabet ${\hat {\Sigma }}$ accepteras av en deterministisk synlig pushdown-automat, då kallas ${\displaystyle L} för ett$ synligt pushdown-språk .

Icketerministiska synligt pushdown-automater

Icketerministiska synligt pushdown-automater är lika uttrycksfulla som deterministiska. Därför kan man omvandla en icke-deterministisk, synligt pushdown-automat till en deterministisk, men om den icke-deterministiska automaten hade $s$ -tillstånd, kan den deterministiska ha upp till $2^{s^{2}}$ tillstånd.

Beslutsproblem

Låt $|A|$ är storleken på beskrivningen av en automat $A$ , då är det möjligt att kontrollera om ett ord n ​​accepteras av automaten i tiden ${\ displaystyle O(|A|^{3}\ell )}$ . I synnerhet är tomhetsproblemet lösbart i tiden $O(|A|^{3})$ . Om $A$ är fixerad kan den avgöras i tiden $O(\ell )$ och mellanslag $O(d)$ där $d$ är djupet av n i en strömmande seende. Det kan också bestämmas med mellanslag $O(\log(\ell ))$ och tid $O(\ell ^{2} \log(\ell ))$ , och av en enhetlig boolesk krets med djup $O(\log \ell )$ .

För två icke-deterministiska automater A och B är det EXPTIME -komplett att avgöra om uppsättningen av ord som accepteras av A är en delmängd av ordet som accepteras av B. Det är också EXPTIME-komplett för att ta reda på om det finns ett ord som inte accepteras.

språk

Som definitionen av visibly pushdown-automater visar, kan deterministic visibly pushdown-automater ses som ett specialfall av deterministiska pushdown-automater ; sålunda bildar uppsättningen VPL av synligt pushdown-språk över $\,{\hat {\Sigma }}$ en delmängd av uppsättningen DCFL av deterministiska kontextfria språk över uppsättningen symboler i $\ ,{\hat {\Sigma }}$ . I synnerhet omvandlar funktionen som tar bort matchningsrelationen från kapslade ord vanliga språk över kapslade ord till sammanhangsfria språk.

Stängningsegenskaper

Uppsättningen av synligt pushdown-språk stängs under följande operationer:

• ställ in operationer:
  • union
  • genomskärning
  • komplement,

vilket ger upphov till en boolesk algebra .

• Kleene stjärna
• sammanlänkning
• omkastning
• Stränghomomorfism

För skärningsoperationen kan man konstruera en VPA M som simulerar två givna VPAs $M_{1}$ och $M_{2}$ genom en enkel produktkonstruktion ( Alur & Madhusudan 2004) : För $i=1,2$ , antag att $\displaystyle M_{i}}$$(Q_{i},\ {\hat {\Sigma }},\ \Gamma _{i},\ \delta _{i},\ s_{i},\ Z_{i},\ F_{ i})$ ges som . Sedan för automaten M är uppsättningen tillstånd $\,Q_{1}\ gånger Q_{2}$ , initialtillståndet är $\left( s_{1},s_{2}\right)$ , uppsättningen av sluttillstånd är $F_{1}\ gånger F_{2}$ , stapelalfabetet ges av $\,\Gamma _{1}\times \Gamma _{2}$ och den initiala stacksymbolen är $(Z_{1},Z_{2})$ .

Om $M$ är i tillståndet $(p_{1},p_{2})$ vid läsning av en anropssymbol $\left\langle a\right.$ , sedan trycker $M$ på stacksymbolen $(\gamma _{1},\gamma _{2})$ och går till status $(q_{1},q_{2})$ , där $\gamma _{i}$ är stacksymbolen som trycks av $M_{i}$ vid övergång från tillstånd $p_{i}$ till $q_{i}$ vid läsningsinmatning $\left\langle a\right.$ .

Om $M$ är i tillståndet $(p_{1},p_{2})$ vid läsning av en intern symbol $a$ , då $M$ går till tillstånd $(q_{1},q_{2})$ , närhelst $M_{i}$ övergår från tillstånd $\displaystyle p_{i} }$ till $q_{i}$ vid läsning av en .

Om $M$ är i tillståndet $(p_{1},p_{2})$ vid läsning av en retursymbol $\left.a\right\rangle$ , sedan öppnar $M$ symbolen $(\gamma _{1},\gamma _{2})$ från stacken och går till status $(q_{1},q_{2})$ , där $\gamma _{i}$ är stacksymbolen som visas av $M_{i}$ vid övergång från ange $p_{i}$ till $q_{i}$ vid läsning av $\left.a\right\rangle$ .

Korrektheten av ovanstående konstruktion bygger i avgörande grad på det faktum att push- och pop-aktionerna för de simulerade maskinerna $M_{1}$ och $M_{2}$ synkroniseras längs med de lästa ingångssymbolerna. Faktum är att en liknande simulering inte längre är möjlig för deterministiska pushdown-automater , eftersom den större klassen av deterministiska kontextfria språk inte längre är stängda under skärningspunkten.

I motsats till konstruktionen för sammanlänkning som visas ovan, är komplementkonstruktionen för synligt pushdown-automater parallell med standardkonstruktionen för deterministiska pushdown-automater.

Dessutom, liksom klassen av kontextfria språk, stängs klassen av synligt pushdown-språk under prefix stängning och reversering, därav också suffix stängning.

Relation till andra språkklasser

Alur & Madhusudan (2004) påpekar att de synligt pushdown-språken är mer generella än de parentesspråk som föreslås i McNaughton (1967) . Som framgår av Crespi Reghizzi & Mandrioli (2012) , är de synligt pushdown-språken i sin tur strikt inkluderade i den klass av språk som beskrivs av operatörsprecedensgrammatiker , som introducerades av Floyd (1963) och åtnjuter samma stängningsegenskaper och egenskaper (se Lonati et al (2015) för ω-språk och logik och automatbaserade karakteriseringar). I jämförelse med konjunktiva grammatiker , en generalisering av sammanhangsfria grammatiker, visar Okhotin (2011) Tabellen i slutet av denna artikel sätter familjen av synligt pushdown-språk i relation till andra språkfamiljer i Chomsky-hierarkin . Rajeev Alur och Parthasarathy Madhusudan relaterade en underklass av vanliga binära trädspråk till synligt pushdown-språk.

Andra beskrivningsmodeller

Synligt pushdown-grammatik

Synligt pushdown-språk är exakt de språk som kan beskrivas med synligt pushdown-grammatik .

Synligt pushdown-grammatik kan definieras som en begränsning av sammanhangsfria grammatiker . En synligt pushdown grammatik G definieras av 4- tupeln :

$G=(V=V^{0}\cup V^{1}\,,\Sigma \,,R\,,S\ ,)$ var

• $V^{0}\,$ och $V^{1}\,$ är disjunkta ändliga mängder; varje element $v\in V$ kallas ett icke-terminalt tecken eller en variabel . Varje variabel representerar en annan typ av fras eller klausul i meningen. Varje variabel definierar ett underspråk till språket som definieras av $G\,$ , och underspråken för $V^{0}\,$ är det utan väntande anrop eller väntande returer.
• $\Sigma \,$ är en ändlig uppsättning terminal s, disjunkt från $V\,$ , som utgör meningens faktiska innehåll. Uppsättningen av terminaler är alfabetet för språket som definieras av grammatiken $G\,$ .
• $R\,$ är en ändlig relation från $V\,$ till $(V\cup \Sigma )^{*}$ så att $\exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R$ . Medlemmarna av $R\,$ kallas (omskriv)regeln eller produktionen av grammatiken. Det finns tre typer av omskrivningsregler. För ${\displaystyle X,Y\in V,Z\in V^{0}} ,$ a $\displaystyle a\in {\hat {\Sigma }}}$ och $b\in {\hat {\Sigma }}$
  • $X\to \epsilon$
  • $X\to aY$ och om $X\in V^{0}$ så $Y\in V^{0}$ och ${ \displaystyle a\in \Sigma }$
  • $X\to \langle aZb\rangle Y$ och om $X\in V^{0}$ så $Y\in V^ {0}$
• $S\in V\,$ är startvariabeln (eller startsymbolen ), som används för att representera hela meningen (eller programmet).

Här representerar asterisken Kleene stjärnoperationen och $\epsilon$ är det tomma ordet.

Uniforma booleska kretsar

Problemet om ett ord med längden $\ell$ accepteras av en given kapslad ordautomat kan lösas med enhetliga booleska kretsar med djup $\mathrm {O} (\log \ell )$ .

Logisk beskrivning

Reguljära språk över kapslade ord är exakt den uppsättning språk som beskrivs av monadisk andra ordningens logik med två unära predikat call and return , linjär efterföljare och matchningsrelationen ↝.

Se även

• Modellkontroll

Anteckningar

•   Floyd, RW (juli 1963). "Syntaktisk analys och operatörsföreträde". Journal of the ACM . 10 (3): 316–333. doi : 10.1145/321172.321179 . S2CID 19785090 .
•   McNaughton, R. (1967). "Grammatik för parentes" . Journal of the ACM . 14 (3): 490–500. doi : 10.1145/321406.321411 . S2CID 10926200 .
•   Alur, R.; Arenas, M.; Barcelo, P.; Etessami, K.; Immerman, N.; Libkin, L. (2008). Grädel, Erich (red.). "Första ordningens och tidsmässiga logik för kapslade ord". Logiska metoder i datavetenskap . 4 (4). arXiv : 0811.0537 . doi : 10.2168/LMCS-4(4:11)2008 . S2CID 220091601 .
• Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operatörsföreträde och den synliga pushdown-egenskapen" . Tidskrift för data- och systemvetenskap . 78 (6): 1837–1867. doi : 10.1016/j.jcss.2011.12.006 .
• Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Operatorprecedensspråk: deras automatteoretiska och logiska karaktärisering". SIAM Journal on Computing . 44 (4): 1026–1088. doi : 10.1137/140978818 . hdl : 2434/352809 .
• Okhotin, Alexander: Jämföra linjära konjunktiva språk med underfamiljer av de kontextfria språken, 37:e internationella konferensen om aktuella trender inom teori och praktik inom datavetenskap (SOFSEM 2011).
•   Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduktion till automatteori, språk och beräkningar . Addison-Wesley. ISBN 978-0-201-02988-8 .

externa länkar

• Kapslade ord och synligt pushdown-språk
• Visibly pushdown automata – Automata på kapslade ord
• klass VPL på Complexity Zoo