Visibly pushdown languages
From MaRDI portal
Publication:3580970
DOI10.1145/1007352.1007390zbMath1192.68396OpenAlexW2151033407WikidataQ29038653 ScholiaQ29038653MaRDI QIDQ3580970
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://repository.upenn.edu/cis_papers/191
Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Grammars and rewriting systems (68Q42)
Related Items (only showing first 100 items - show all)
A Branching Time Variant of CaRet ⋮ Revisiting Underapproximate Reachability for Multipushdown Systems ⋮ Space Complexity of Stack Automata Models ⋮ Nested Regular Expressions Can Be Compiled to Small Deterministic Nested Word Automata ⋮ Unnamed Item ⋮ Never-stop context-free learning ⋮ Synchronization of Parikh automata ⋮ On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata ⋮ Simulation relations and applications in formal methods ⋮ Interval Temporal Logic for Visibly Pushdown Systems ⋮ Model Checking Temporal Properties of Recursive Probabilistic Programs ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Extending Wagner's hierarchy to deterministic visibly pushdown automata ⋮ From languages to behaviors and back ⋮ Queue Automata: Foundations and Developments ⋮ Unnamed Item ⋮ A survey on automata with translucent letters ⋮ Sweeping input-driven pushdown automata ⋮ Weighted Logics for Nested Words and Algebraic Formal Power Series ⋮ Language Strength Reduction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Infinite Automaton Characterization of Double Exponential Time ⋮ Extensional Uniformity for Boolean Circuits ⋮ Verifying quantitative temporal properties of procedural programs ⋮ Temporal Logic with Recursion. ⋮ An Automata-Theoretic Approach to Infinite-State Systems ⋮ On the power of pushing or stationary moves for input-driven pushdown automata ⋮ Event-Clock Visibly Pushdown Automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Visibly Pushdown Transducers for Approximate Validation of Streaming XML ⋮ Unnamed Item ⋮ State Complexity of the Quotient Operation on Input-Driven Pushdown Automata ⋮ Realizability of Concurrent Recursive Programs ⋮ Bounded Delay and Concurrency for Earliest Query Answering ⋮ Rigid Tree Automata ⋮ Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata ⋮ Input-driven multi-counter automata ⋮ Streaming ranked-tree-to-string transducers ⋮ Input-driven pushdown automata for edit distance neighborhood ⋮ Nested Sibling Tree Automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ CaRet With Forgettable Past ⋮ Unnamed Item ⋮ Digging input-driven pushdown automata ⋮ Space Complexity of Stack Automata Models ⋮ A complete refinement procedure for regular separability of context-free languages ⋮ Visibly Pushdown Transducers with Look-Ahead ⋮ Model-checking structured context-free languages ⋮ The Boolean Formula Value Problem as Formal Language ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Deciding Proper Conjugacy of Classes of One-Sided Finite-Type-Dyck Shifts ⋮ On Distinguishing NC $$^1$$ and NL ⋮ Conjunctive grammars and alternating pushdown automata ⋮ Model Checking Procedural Programs ⋮ Automata-based verification of programs with tree updates ⋮ Summarization for termination: No return! ⋮ Input-driven languages are linear conjunctive ⋮ Notions of hyperbolicity in monoids. ⋮ Weighted Register Automata and Weighted Logic on Data Words ⋮ Synchronization of Regular Automata ⋮ Query Automata for Nested Words ⋮ Colored nested words ⋮ Propositional dynamic logic with recursive programs ⋮ Algorithmic games for full ground references ⋮ Ordered multi-stack visibly pushdown automata ⋮ A Logical Characterization of Timed Pushdown Languages ⋮ Word equations in the context of string solving ⋮ Checking regular invariance under tightly-controlled string modifications ⋮ On the decidability of infix inclusion problem ⋮ On the power of pushing or stationary moves for input-driven pushdown automata ⋮ Visibly pushdown transducers ⋮ Automata for XML -- a survey ⋮ Branching-time logics with path relativisation ⋮ Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization ⋮ Shuffled languages -- representation and recognition ⋮ Parameterized linear temporal logics meet costs: still not costlier than LTL ⋮ Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$ ⋮ Logics for Weighted Timed Pushdown Automata ⋮ Conjunctive Visibly-Pushdown Path Queries ⋮ A survey of timed automata for the development of real-time systems ⋮ Sofic-Dyck shifts ⋮ Program synthesis for interactive-security systems ⋮ P-hardness of the emptiness problem for visibly pushdown languages ⋮ Synchronizing relations on words ⋮ When input-driven pushdown automata meet reversiblity ⋮ Model checking probabilistic systems against pushdown specifications ⋮ Edit-Distance Between Visibly Pushdown Languages ⋮ Evolving schemas for streaming XML ⋮ Generalizing input-driven languages: theoretical and practical benefits ⋮ Unnamed Item ⋮ Parametric random generation of deterministic tree automata ⋮ Regular languages of nested words: fixed points, automata, and synchronization ⋮ Static analysis of XML security views and query rewriting ⋮ Multi-matching nested relations ⋮ ML and Extended Branching VASS
Uses Software
This page was built for publication: Visibly pushdown languages
