Visibly pushdown languages
From MaRDI portal
Publication:3580970
DOI10.1145/1007352.1007390zbMath1192.68396DBLPconf/stoc/AlurM04OpenAlexW2151033407WikidataQ29038653 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 ⋮ A Context-Free Symbiosis of Runtime Verification and Automata Learning ⋮ Unnamed Item ⋮ Visibly Pushdown Transducers for Approximate Validation of Streaming XML ⋮ Unnamed Item ⋮ Validating streaming JSON documents with learned VPAs ⋮ Stack-aware hyperproperties ⋮ A temporal logic for higher-order functional programs ⋮ From words to pictures: row-column combinations and Chomsky-Schützenberger theorem ⋮ State Complexity of the Quotient Operation on Input-Driven Pushdown Automata ⋮ Realizability of Concurrent Recursive Programs ⋮ A closer look at the expressive power of logics based on word equations ⋮ 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 ⋮ Theoretical computer science: computational complexity ⋮ Descriptional complexity of finite automata -- selected highlights ⋮ Input-driven pushdown automata for edit distance neighborhood ⋮ On the decidability of infix inclusion problem ⋮ Separating the expressive power of propositional dynamic and modal fixpoint logics ⋮ 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
Uses Software
This page was built for publication: Visibly pushdown languages
