Vi föreslår klassen av synbart pushdown språk som inbäddningar av sammanhangsfria språk som är tillräckligt rik för att modellera programanalys frågor och ändå är dragbar och robust som klassen av vanliga språk. I vår definition, anger inmatningssymbolen när pushdown automaton kan skjuta eller pop, och därmed stackdjupet på varje position. Vi visar att den resulterande klass Vpl av språk är stängd under union, skärningspunkt, komplettering, namnändring, konkatetering, och Kleene- *, och problem såsom inkludering som är obeslutbara för kontextfria språk är Exptime-komplett för synbart pushdown automata. Vårt ramverk förklarar, sammanställer och generaliserar många av beslutsförfarandena i programanalyslitteraturen, och möjliggör algoritmisk verifiering av rekursiva program med avseende på många kontextfria egenskaper inklusive åtkomstkontrollegenskaper via stackinspektion och korrekthet av förfaranden med avseende på pre- och postförhållanden. Vi visar att klassen Vpl är robust genom att ge två alternativa karakteriseringar: en logisk karakterisering med hjälp av den monadiska andra ordningen (MSO) teori över ord förstärkt med en binär matchande predikat, och en korrespondens till vanliga trädspråk. Vi anser också synbart pushdown språk av oändliga ord och visar att stängning egenskaper, MSO-karakterisering och karakterisering i termer av vanliga träd bär över. Den största skillnaden i fråga om fallet med finita ord visar sig vara determinisability: icke-deterministiska Büchi synbart pushdown automata är strikt mer uttrycksfulla än deterministiska Muller synbart pushdown automata.
I REF består tillstånden för den resulterande deterministiska synbart pushdown automaton av två komponenter (S, R).
Visibly pushdown languages
{'venue': "STOC '04", 'journal': None, 'mag_field_of_study': ['Computer Science']}