State complexity of operations on input-driven pushdown automata

DOI10.1016/j.jcss.2017.02.001zbMath1370.68186OpenAlexW2585141159MaRDI QIDQ2396831

Alexander Okhotin, Kai Salomaa

Publication date: 26 May 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2017.02.001

zbMATH Keywords

state complexitypushdown automatanested word automatavisibly pushdown automatainput-driven automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Additive number theory via automata theory, Further closure properties of input-driven pushdown automata, Operational Accepting State Complexity: The Unary and Finite Case, State Complexity of the Quotient Operation on Input-Driven Pushdown Automata, Edit distance neighbourhoods of input-driven pushdown automata, Edit distance neighbourhoods of input-driven pushdown automata, Deciding path size of nondeterministic (and input-driven) pushdown automata, Input-driven pushdown automata on well-nested infinite strings, Sums of Palindromes: an Approach via Automata

Uses Software

• XPath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unambiguous finite automata over a unary alphabet
• Descriptional complexity of unambiguous input-driven pushdown automata
• Limitations of lower bound methods for deterministic nested word automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• The state complexity of \(L^{2}\) and \(L^k\)
• Streaming tree automata
• State complexity of power
• Succinct representation of regular languages by Boolean automata
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• Input-driven languages are linear conjunctive
• Operations on Unambiguous Finite Automata
• Weighted Nested Word Automata and Logics over Strong Bimonoids
• Descriptional Complexity of Input-Driven Pushdown Automata
• Adding nesting structure to words
• Minimizing Variants of Visibly Pushdown Automata
• Operator Precedence and the Visibly Pushdown Property
• Trimming Visibly Pushdown Automata
• A Uniformization Theorem for Nested Word to Word Transductions
• Early Nested Word Automata for XPath Query Answering on XML Streams
• Regularity Problems for Visibly Pushdown Languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Automata, Languages and Programming