Cuvinte născute

Sursă Originală: http://www.cis.upenn.edu/~alur/nw.html

cunoscut sub numele de Limbi vizuale

Ce sunt cuvintele imbricate?

Cuvintele incomplete reprezintă un model pentru reprezentarea datelor atât cu o ordonare liniară, cât și cu o potrivire imbricată ierarhică a elementelor. Exemple de date cu o astfel de structură dual-ierarhică dublă includ execuțiile programelor structurate, datele lingvistice adnotate și documentele HTML / XML. Un cuvânt imbricat constă dintr – o secvență de poziții ordonate liniar, augmentată cu margini cuibărit conectarea apelurilor la randamente (sau -tag – uri deschise pentru a -tag-uri închide). Marginile nu trec prin crearea unei structuri ierarhice imbricate corespunzător și permitem ca unele dintre margini să fie în așteptare. Această structură de cuibărit poate fi reprezentată în mod unic printr-o secvență care specifică tipurile de poziții (apeluri, returnări și interni). Cuvintele înnăscută generalizează atât cuvintele, cât și copacii ordonați și permit atât operațiunile cu cuvinte, cât și cu arbori.

Cuvinte automate încorporate — acceptoare de stare finită pentru cuvinte imbricate, definesc clasa de limbi obișnuite ale cuvintelor imbricate. Această clasă are toate proprietățile teoretice atrăgătoare pe care limbile clasice de limbi obișnuite se bucură: automatele cuvântului determinist, imbricate, sunt la fel de expresive ca și omologii lor nedeterminici; clasa este închisă sub unire, intersecție, complementare, concatenare, Kleene- *, prefixe și homomorfisme de limbă; apartenența, goliciunea, includerea lingvistică și echivalența lingvistică sunt toate hotărâtoare; și definirea în logica monadică a ordinii a doua corespunde exact recunoașterii de stare finită. Aceste rezultate generalizează de asemenea cuvinte infinite imbricate.

Cum se raportează la limbile de cuvinte fără contextual?

Având în vedere o limbă L de cuvinte imbricate peste un alfabet, codarea liniară a cuvintelor imbricate dă o limbă L ‘peste alfabetul marcat, format din simboluri marcate cu tipul poziției. Dacă L este limbajul obișnuit al cuvintelor imbricate, atunci L este fără context. De fapt, automatul de expansiune care acceptă L ‘are o structură specială: în timp ce citiți un apel, automatul trebuie să împingă un simbol, în timp ce citește un simbol de întoarcere, trebuie să apară un simbol (dacă stiva nu este goală) un simbol intern, poate actualiza doar starea sa de control. Noi numim astfel de automate vizibil de retragere automata și clasa de limbi de cuvinte pe care le acceptă vizibil limbi împinge(VPL). Din moment ce automatele noastre pot fi determinate, VPL-urile corespund unei subclase de limbi fără context determinist (DCFL). VPL-urile generalizează limbi paranteze, limbi înclinate și limbi echilibrate și au proprietăți de închidere mai bune decât limbile CFL, DCFL sau paranteză.

Noi susținem că pentru verificarea algoritmică a programelor structurate, în loc să vedeți programul ca un limbaj fără contextual peste cuvinte, trebuie să îl vedeți ca un limbaj obișnuit al cuvintelor imbricate (sau echivalent, o limbă vizibilă de împingere) și acest lucru ar permite modelului verificarea mai multor proprietăți (cum ar fi inspecția stivei, condițiile pre-post) care nu pot fi exprimate în logica specificațiilor existente.

În general, automatele pushdown servesc două scopuri distincte: descoperirea potrivirii ierarhice și procesarea / interogarea potrivirii. În aplicațiile în care numai al doilea scop este relevant (ca în analiza programelor), se pot înlocui automat pushdown cu NWA cu multe avantaje.

Cum se referă la copaci ordonați?

Datele cu structură dublă liniară-ierarhică sunt modelate în mod tradițional utilizând binare și, în general, folosind ordonate ordonate, arbori și interogați folosind automate de copaci. În arborii ordonați, nodurile cu același părinte sunt ordonate liniar, iar traversările clasice de arbori, cum ar fi infix (sau adâncimea primului la stânga-dreapta), pot fi folosite pentru a defini o comandă implicită a tuturor nodurilor. Se pare că gardurile vii, în cazul în care un gard viu este o secvență de arbori ordonați, sunt o clasă specială de cuvinte imbricate, și anume cele care corespund cu cuvintele Dyck, iar limbile de hedging regulate corespund unor limbi echilibrate.

Pentru procesarea documentelor, cuvintele imbricate au multe avantaje față de copaci ordonați. Arhitectura bazată pe arbore implicit presupune că datele liniare de intrare pot fi analizate într-un arbore și, prin urmare, nu se poate reprezenta și prelucra date care ar putea să nu parseze corect. Operațiile cu litere, cum ar fi prefixele, sufixele și concatenarea, în timp ce sunt naturale pentru procesarea documentelor, nu au operații arborice similare. În al doilea rând, automatele de copaci pot exprima în mod firesc constrângerile asupra secvenței etichetelor de-a lungul unei căi ierarhice, dar și de-a lungul fraților din stânga-dreapta, dar au dificultăți în captarea constrângerilor care se referă la ordinea liniară globală. De exemplu, interogarea pe care modelele p1, … pk apar în document în acea ordine compilează într-un cuvânt determinist automat (și deci NWA determinist) de dimensiune liniară, dar arborele standard determinist de jos în sus pentru această interogare trebuie să aibă dimensiuni exponențiale în k. NWA-urile pot fi văzute ca un fel de automate de copaci, astfel încât atât automatele copac de jos în sus, cât și automatele copac de sus în jos sunt cazuri speciale. Aceste rezultate implică faptul că o interogare poate fi codificată mai succint în vizualizarea cuvintelor imbricate cu avantaje complexe. Un cuvânt automat imbricat citește cuvântul de la stânga la dreapta, prelucrând marginile de cuibărit ca și când sosesc. Acest lucru se potrivește cu SAX API pentru XML și, prin urmare, are o utilizare naturală în algoritmii de streaming. Aceste rezultate implică faptul că o interogare poate fi codificată mai succint în vizualizarea cuvintelor imbricate cu avantaje complexe. Un cuvânt automat imbricat citește cuvântul de la stânga la dreapta, prelucrând marginile de cuibărit ca și când sosesc. Acest lucru se potrivește cu SAX API pentru XML și, prin urmare, are o utilizare naturală în algoritmii de streaming. Aceste rezultate implică faptul că o interogare poate fi codificată mai succint în vizualizarea cuvintelor imbricate cu avantaje complexe. Un cuvânt automat imbricat citește cuvântul de la stânga la dreapta, prelucrând marginile de cuibărit ca și când sosesc. Acest lucru se potrivește cu SAX API pentru XML și, prin urmare, are o utilizare naturală în algoritmii de streaming.

Referințe

Modelul de cuvinte imbricate a trecut printr-o serie de iterații: consultați limbile vizibile de împrăștiere ; Alur și Madhusudan; STOC 2004; și adăugarea structurii de cuibărit la cuvinte ; Alur și Madhusudan; DLT 2006. Vă recomandăm să citiți această versiune completă unică (Jurnalul ACM, 2009). Discuția invitată la CSR 2007 este, de asemenea, un bun punct de plecare.

Scopul acestei pagini este de a urmări cercetarea extensivă de urmărire pe această temă. Trimiteți-mi un e-mail cu comentarii și / sau sugestii suplimentare.

Unelte

Probleme de rezolvare suplimentare pentru VPA / NWA

  • Vizibil jocuri de împingere; Loding, Madhusudan și Serre; FSTTCS 2004.
  • Dispozitive vizuale de împingere: de la echivalența lingvistică la simulare și bisimilare; SRBA; CSL 2006.
  • Probleme de regularitate pentru limbile vizibile de împingere; Barany, Loding și Serre; STACS 2006.
  • Cu privire la problema de apartenență la limbile vizibile îndemnizabile; La Torre, Napoli și Parente; ATVA 2006.
  • Simbolice vizibil automate de împingere; D’Antoni și Alur; CAV 2014.

Congruențe și minimalizare

  • Congrudențe pentru limbi vizibile de împingere; Alur, Kumar, Madhusudan și Viswanathan; ICALP 2005.
  • Minimizarea, învățarea și testarea conformității programelor booleene; Kumar, Madhusudan și Viswanathan; CONCUR 2006.
  • Minimizarea variantelor automatelor de deplasare vizibile; Chervet și Walukiewicz; MFCS 2007.
  • Minimizarea automatelor de deplasare cu vizibilitate maximă folosind Max-SAT parțial; Heizmann, Schilling și Tischner; TACAS 2017.

Logica temporară și fixă; Expresivitate

  • O logică temporală a apelurilor și întoarcerilor imbricate; Alur, Etessami și Madhusudan; TACAS 2004.
  • Limbile regulate ale cuvintelor imbricate: puncte fixe, automate și sincronizare; Arenas, Barcelo și Libkin; ICALP 2007.
  • Logica întâi și logica temporală pentru cuvintele imbricate, Alur, Arenas, Barcelo, Etessami, Immerman și Libkin; LICS 2007.
  • Automate alternante și un calcul temporal de punct fix pentru limbi vizibile de împingere; Bozzelli; CONCUR 2007.
  • O reprezentare gramaticală a limbajelor vizibile îndemnate; Baran și Barringer; WoLLIC 2007.
  • Instrumente logice ponderate pentru cuvinte imbricate și serii de putere formală algebrică; Matissen; ICALP 2008.
  • Expresii raționale vizibile; Bozzelli și Sanchez; FSTTCS 2012.
  • Vizibil logică temporală liniară; Bozzelli și Sanchez; IJCAR 2014.

Specificații pentru analiza programelor

  • Aspecte bazate pe aspectele bazate pe VPA: Sprijin mai bun pentru protocoalele AOP; Nguyen și Sudholt; SEFM 2006.
  • Instrumente C programe cu monitoare de cuvinte imbricate; Chaudhuri și Alur; SPIN 2007.
  • Sintetizarea monitoarelor pentru proprietățile de siguranță – de data aceasta cu apeluri și returnări; Rosu, Chen și Ball; RV 2008.
  • Raționamentul temporal al programelor procedurale; Alur și Chaudhuri; VMCAI 2010.
  • Noduri interpolate; Heizmann, Hoenicke și Podelski; POPL 2010.
  • Verificarea compatibilității unui producător și a unui consumator; Drscoll, Burton și Reps; FSE 2011.
  • Securizarea programării prin intermediul jocurilor vizuale de siguranță; Harris, Jha și Reps; CAV 2012.

Procesarea XML și automatele copacilor

  • Vizibil efecte de exprimare în expresie pentru procesarea fluxului XML; Ulcior; PLAN-X 2005.
  • Vizibil limbi de împingere pentru streaming XML; Kumar, Madhusudan și Viswanathan; WWW 2007.
  • Căsătorit cu cuvinte și copaci; Alur; PODS 2007.
  • Redenumirea limbajelor vizuale de împingere pentru integrarea datelor XML; Thomo și Venkatesh; CIKM 2008.
  • Streaming tree automata; Gauwin, Niehren și Roos; Scrisori de procesare a informațiilor 2009.
  • Raspunsul cel mai timpuriu al interogarii pentru automate cu cuvinte determinate; Gauwin, Niehren și Tison; FCT 2009.
  • Automate de interogare pentru cuvinte imbricate; Madhusudan și Viswanathan; MFCS 2009.
  • De la expresii regulate la cuvinte imbricate: Limbi unificatoare și executarea interogărilor pentru secvențe relaționale și XML; Mozafari, Zeng, Zaniolo; VLDB 2010.
  • Procesarea complexă a evenimentelor de înaltă performanță peste fluxurile XML; Mozafari, Zeng, Zaniolo; SIGMOD 2012.
  • Fragmente fragile de XPath înainte; Gauwin și Niehren; CIAA 2012.
  • Early XPath selecție nod pe fluxuri XML; Debarbieux, Gauwin, Niehren, Sebastian și Zergaoui; 2012.

traductoare

  • Traductoare de redresare vizibile pentru validarea aproximativă a fluxului XML; Thomo, Venkatesh și Ye; FoIKS 2008.
  • Traductoare de împingere vizibile; Raskin și Servais; ICALP 2008.
  • Echivalența traductoarelor determinate de Word în Word; Staworko, Laurence, Lemay, Niehren; FCT 2009.
  • Proprietăți ale traductoarelor vizibile; E. Filiot, J.-F. Raskin, P.-A. Reynier, F. Servais și J.-M. Talbot; MFCS 2010.
  • XEvolve: un schemă XML Schema Evolution; F. Picalausa, F. Servais și E. Zimànyi; SACSVT 2011.
  • Streamabilitatea Transductiilor de cuvinte încorporate; E. Filiot, O. Gauwin, P.-A. Reynier, F. Servais. FSTTCS 2011.
  • Transductori de copaci strecurori; R. Alur și L. D’Antoni; ICALP 2012.
  • Traductoare vizibile cu deplasare în sus. E. Filiot și F. Servais. SOFSEM 2012.

Copacii născuți

  • Un calcul al punctelor fixe pentru fluxurile programelor locale și globale; Alur, Chaudhuri și Madhusudan; POPL 2006.
  • Limbile copacilor imbricate; Alur, Chaudhuri și Madhusudan; CAV 2006.
  • Vizibil limbi de retragere și rescriere pe termen; Chabin și Rety; FroCos 2007.
  • Vizibil automat de copaci cu memorie și constrângeri; Comon-Lundh, Jacquemard, Perrin; Metode logice în informatică 2008.

Cuvintele cu mai multe nestinguri

  • O notă privind cuvintele imbricate; Blass și Gurevich; Microsoft Research TR; 2006.
  • O clasă solidă de limbi sensibile la context; La Torre, Madhusudan și Parlato; LICS 2007.
  • 2-automat automat de deplasare; Carotenuto, Murano și Peron; DLT 2007.
  • Realizabilitatea programelor recurente concurente; Bollig, Grindei și Habermehl; FoSSaCS 2009.

Rezultate noi utilizând vizibilitatea apelurilor / returnărilor

  • Algol al treilea ordin, idealizat cu iterație, este decisiv; Murawski și Walukiewicz; FoSSaCS 2005.
  • Sincronizarea automatelor de deplasare; Caucal; DLT 2006.
  • Logica dinamică logică cu programe recursive; Loding și Serre; FoSSaCS 2006.
  • Înaltime-deterministe automate de împingere; Nowotka și Srba; MFCS 2007.
  • O caracterizare automată infinită a timpului exponențial dublu; La Torre, Madhusudan și Parlato; CSL 2008.

O provocare problemă deschisă (rezolvată acum!)

Luați în considerare următoarea problemă de decizie: dacă există două limbi obișnuite L1 și L2 ale cuvintelor imbricate, există o limbă regulată R de cuvinte peste alfabetul marcat astfel încât intersecția (R, L1) să fie egală cu L2? Nu se știe că acest lucru este decisiv, chiar și pentru cazul special în care L1 este setul tuturor cuvintelor potrivite. Motivația este următoarea: în general, pentru a verifica dacă intrarea aparține L2, mașina de procesare are nevoie de un teanc. Dar presupunem că avem deja unele cunoștințe suplimentare despre intrare, că aparține setului L1 (de exemplu, este posibil să știm că intrarea este potrivită), poate fi folosită această cunoaștere pentru a construi un DFA A astfel încât pentru intrările în L1, A este capabil să decidă apartenența la L2. Această problemă este inspirată de lucrarea “Validarea documentelor XML streaming” de Segoufin și Vianu, PODS 2002,

Recent, Eryk Kopczynski a demonstrat imposibilitatea acestei probleme: a se vedea limbile de invadare invizibile , LICS 2016.