Adding nesting structure to words
From MaRDI portal
Publication:3452213
DOI10.1145/1516512.1516518zbMath1325.68138OpenAlexW2131886132WikidataQ29396124 ScholiaQ29396124MaRDI QIDQ3452213
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1516512.1516518
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
Ramsey-Based Inclusion Checking for Visibly Pushdown Automata, Which XML schemas are streaming bounded repairable?, A Branching Time Variant of CaRet, Realizability of concurrent recursive programs, Visibly Pushdown Transducers with Look-Ahead, Model-checking structured context-free languages, Descriptional Complexity of Input-Driven Pushdown Automata, Linking theorems for tree transducers, Deciding Proper Conjugacy of Classes of One-Sided Finite-Type-Dyck Shifts, The (nested) word problem, Model Checking Procedural Programs, Colored nested words, First-Order Logic Definability of Free Languages, State complexity of operations on input-driven pushdown automata, Symbolic weighted language models, quantitative parsing and automated music transcription, On the power of pushing or stationary moves for input-driven pushdown automata, The complexity of model checking multi-stack systems, Games for active XML revisited, Visibly pushdown transducers, Communicating Finite-State Machines and Two-Variable Logic, Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization, Locally Chain-Parsable Languages, Automata and Logics for Concurrent Systems: Five Models in Five Pages, Interprocedural Reachability for Flat Integer Programs, Beyond operator-precedence grammars and languages, Input-Driven Double-Head Pushdown Automata, Interval Temporal Logic for Visibly Pushdown Systems, Sofic-Dyck shifts, Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages, Extending Wagner's hierarchy to deterministic visibly pushdown automata, State complexity of the concatenation of regular tree languages, A survey of model learning techniques for recurrent neural networks, Queue Automata: Foundations and Developments, Synchronizing deterministic push-down automata can be really hard, Sweeping input-driven pushdown automata, When input-driven pushdown automata meet reversiblity, Generalizing input-driven languages: theoretical and practical benefits, Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Operator precedence temporal logic and model checking, Unnamed Item, Multi-matching nested relations, Temporal logics for concurrent recursive programs: satisfiability and model checking, The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity, Visibly rational expressions, Descriptional complexity of unambiguous input-driven pushdown automata, Minimization of Visibly Pushdown Automata Using Partial Max-SAT, Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete, Precedence Automata and Languages, Additive number theory via automata theory, Visibly pushdown modular games, On the path-width of integer linear programming, Weighted automata and logics for infinite nested words, Operator precedence and the visibly pushdown property, Further closure properties of input-driven pushdown automata, JUMPING FINITE AUTOMATA, Queries on XML streams with bounded delay and concurrency, Limitations of lower bound methods for deterministic nested word automata, Nondeterministic state complexity of nested word automata, Operational state complexity of nested word automata, On the power of pushing or stationary moves for input-driven pushdown automata, Streamable Fragments of Forward XPath, Shifts of \(k\)-nested sequences, Toward a theory of input-driven locally parsable languages, Unnamed Item, Automated Program Verification, Sublinear DTD Validity, Visibly Pushdown Transducers with Well-Nested Outputs, State Complexity of the Quotient Operation on Input-Driven Pushdown Automata, Generalized rewrite theories, coherence completion, and symbolic methods, Input-driven pushdown automata for edit distance neighborhood, Synchronizing Automata over Nested Words, On exteriority notions in book embeddings and treewidth, Unnamed Item, Weighted Automata and Logics on Infinite Graphs, Edit distance neighbourhoods of input-driven pushdown automata, Edit distance neighbourhoods of input-driven pushdown automata, An Automaton over Data Words That Captures EMSO Logic, Weighted operator precedence languages, Logic for \(\omega\)-pushdown automata, Weighted automata, BOUNDED PARIKH AUTOMATA, Weighted Operator Precedence Languages, On the determinization of event-clock input-driven pushdown automata, Deciding path size of nondeterministic (and input-driven) pushdown automata, Trimming visibly pushdown automata, Deterministic input-driven queue automata: finite turns, decidability, and closure properties, Early nested word automata for XPath query answering on XML streams, Digging input-driven pushdown automata, Context-free timed formalisms: robust automata and linear temporal logics, Sums of Palindromes: an Approach via Automata
