State complexity of operations on input-driven pushdown automata
From MaRDI portal
Publication:2396831
DOI10.1016/J.JCSS.2017.02.001zbMATH Open1370.68186OpenAlexW2585141159MaRDI QIDQ2396831FDOQ2396831
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
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
- Adding nesting structure to words
- Streaming tree automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Title not available (Why is that?)
- State complexity of power
- Title not available (Why is that?)
- Title not available (Why is that?)
- The state complexity of \(L^{2}\) and \(L^k\)
- Operational state complexity of nested word automata
- Unambiguous finite automata over a unary alphabet
- Partial orders on words, minimal elements of regular languages, and state complexity
- Succinct representation of regular languages by Boolean automata
- Descriptional complexity of input-driven pushdown automata
- Descriptional complexity of unambiguous input-driven pushdown automata
- Nondeterministic state complexity of nested word automata
- Minimizing Variants of Visibly Pushdown Automata
- Limitations of lower bound methods for deterministic nested word automata
- Automata, Languages and Programming
- Operations on Unambiguous Finite Automata
- Weighted nested word automata and logics over strong bimonoids
- Regularity Problems for Visibly Pushdown Languages
- A uniformization theorem for nested word to word transductions
- Operator precedence and the visibly pushdown property
- Early Nested Word Automata for XPath Query Answering on XML Streams
- Trimming visibly pushdown automata
- Input-driven languages are linear conjunctive
Cited In (18)
- Additive number theory via automata theory
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Title not available (Why is that?)
- Edit distance neighbourhoods of input-driven pushdown automata
- 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
- Sums of Palindromes: an Approach via Automata
- State complexity of operations on input-driven pushdown automata
- Operational state complexity of nested word automata
- State complexity of reversals of deterministic finite automata with output
- Descriptional complexity of input-driven pushdown automata
- Exact descriptional complexity of determinization of input-driven pushdown automata
- Further closure properties of input-driven pushdown automata
- Title not available (Why is that?)
- Input-driven pushdown automata on well-nested infinite strings
- Towards exact state complexity bounds for input-driven pushdown automata
Uses Software
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)
