Abstrakt. Vi föreslår modellen med inbäddade ord för representation av data med både en linjär ordning och en hierarkiskt inbäddad matchning av objekt. Exempel på data med sådan dubbel linjär hierarkisk struktur inkluderar exekveringar av strukturerade program, kommenterade språkliga data och HTML/XML-dokument. Inbäddade ord generaliserar både ord och beställda träd och tillåter både ord- och trädoperationer. Vi definierar inhägnade ordautomatafinita-state-acceptatorer för inhägnade ord, och visar att den resulterande klassen av vanliga språk av inhägnade ord har alla de tilltalande teoretiska egenskaper som de klassiska vanliga ordspråken har: deterministiska inhägnade ordautomata är lika uttrycksfulla som deras icke-deterministiska motsvarigheter; klassen är stängd under union, skärningspunkt, komplettering, konkatering, Klene-*, prefix och språk homomorfismer; medlemskap, tomhet, språkinblandning och språklikvärdighet är alla decitable; och definibilitet i monadisk andra ordning logik motsvarar exakt finit-stat igenkännbarhet. Vi ser också på vanliga språk med oändliga inbäddade ord och visar att stängningsegenskaperna, MSO-karakteriseringen och beslutsproblemens decisionability för med sig. De linjära kodningarna av inbäddade ord ger klassen synbart nedtryckta ordspråk, och denna klass ligger mellan balanserade språk och deterministiska sammanhangsfria språk. Vi hävdar att för algoritmisk verifiering av strukturerade program, i stället för att visa programmet som ett sammanhangsfritt språk över ord, bör man se det som ett vanligt språk av inbäddade ord (eller motsvarande, ett synligt pushdown språk), och detta skulle tillåta modellkontroll av många egenskaper (såsom stack inspektion, pre-post villkor) som inte är uttryckliga i befintliga specifikationer logiker. Denna forskning stöddes delvis av ARO URI-utmärkelsen DAAD19-01-0473 och NSF-utmärkelsen CCR-0306382 och CPA-0541149. Denna artikel förenar och förlänger resultat som har dykt upp i Alur och Madhusudan [2004, 2006] North Goodwin Avenue, Urbana, IL 61801, e-post: madhu@cs.uiuc.edu Tillstånd att göra digitala eller hårda kopior av delar eller allt detta verk för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en display tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörigheter kan begäras från Publications Department., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) Vi studerar också förhållandet mellan beställda träd och inhägnade ord, och motsvarande automata: medan analysen komplexiteten hos nästäppa ord automata är samma som den klassiska trädautomata, de kombinerar både nedifrån och ned traversaler, och njuta av uttrycksfullhet och framgång fördelar över trädautomata.
Den underklass av sammanhangsfria språk som tydligt kallas pushdown språk [1, REF har många goda egenskaper såsom booleansk stängning och decidability av tomheten problem i polynom tid.
Adding nesting structure to words
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}