State complexity of operations on input-driven pushdown automata

DOI10.1016/J.JCSS.2017.02.001MaRDI QIDQ2396831zbMATH OpenOpenAlexFDO

Authors 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

pushdown automatastate complexitynested word automatavisibly pushdown automatainput-driven automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of operations on input-driven pushdown automata
• Towards exact state complexity bounds for input-driven pushdown automata
• Further closure properties of input-driven pushdown automata
• Descriptional complexity of input-driven pushdown automata
• Further closure properties of input-driven pushdown automata

Cites work

• scientific article; zbMATH DE number 3885334 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• A uniformization theorem for nested word to word transductions
• Adding nesting structure to words
• Automata, Languages and Programming
• Descriptional complexity of input-driven pushdown automata
• Descriptional complexity of unambiguous input-driven pushdown automata
• Early Nested Word Automata for XPath Query Answering on XML Streams
• Input-driven languages are linear conjunctive
• Limitations of lower bound methods for deterministic nested word automata
• Minimizing Variants of Visibly Pushdown Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• Operations on Unambiguous Finite Automata
• Operator precedence and the visibly pushdown property
• Partial orders on words, minimal elements of regular languages, and state complexity
• Regularity Problems for Visibly Pushdown Languages
• State complexity of power
• Streaming tree automata
• Succinct representation of regular languages by Boolean automata
• The state complexity of \(L^{2}\) and \(L^k\)
• Trimming visibly pushdown automata
• Unambiguous finite automata over a unary alphabet
• Weighted nested word automata and logics over strong bimonoids

Cited in

(18)

• Operational accepting state complexity: the unary and finite case
• State complexity of the quotient operation on input-driven pushdown automata
• scientific article; zbMATH DE number 3885334 (Why is no real title available?)
• Operational state complexity of nested word automata
• Input-driven pushdown automata on well-nested infinite strings
• Edit distance neighbourhoods of input-driven pushdown automata
• State complexity of operations on input-driven pushdown automata
• Descriptional complexity of input-driven pushdown automata
• Additive number theory via automata theory
• Sums of Palindromes: an Approach via Automata
• State complexity of reversals of deterministic finite automata with output
• scientific article; zbMATH DE number 3876636 (Why is no real title available?)
• Edit distance neighbourhoods of input-driven pushdown automata
• Further closure properties of input-driven pushdown automata
• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Towards exact state complexity bounds for input-driven pushdown automata
• Exact descriptional complexity of determinization of input-driven pushdown automata
• Further closure properties of input-driven pushdown automata

Describes a project that uses

Uses Software

• XPath

This page was built for publication: State complexity of operations on input-driven pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396831)