Further closure properties of input-driven pushdown automata
From MaRDI portal
Publication:5919707
DOI10.1016/J.TCS.2019.04.006zbMath1435.68179OpenAlexW2841042379WikidataQ127849674 ScholiaQ127849674MaRDI QIDQ5919707
Alexander Okhotin, Kai Salomaa
Publication date: 7 November 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01905626/file/470153_1_En_19_Chapter.pdf
cyclic shiftsquare rootdeletioninsertionvisibly pushdown automatainput-driven automataproportional removals
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptional complexity of unambiguous input-driven pushdown automata
- On the state complexity of closures and interiors of regular languages with subwords and superwords
- Intersection and union of regular languages and state complexity
- Regularity-preserving relations
- Effective constructions in well-partially-ordered free monoids
- Towards exact state complexity bounds for input-driven pushdown automata
- Parikh's theorem: a simple and direct automaton construction
- Nondeterministic state complexity of nested word automata
- Operational state complexity of nested word automata
- State complexity of operations on input-driven pushdown automata
- The quotient operation on input-driven pushdown automata
- Input-driven languages are linear conjunctive
- State Complexity of Insertion
- Adding nesting structure to words
- State complexity of cyclic shift
- On the State Complexity of Scattered Substrings and Superstrings
- NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS
- On free monoids partially ordered by embedding
- Ordering by Divisibility in Abstract Algebras
- More on the Size of Higman-Haines Sets: Effective Constructions
- Edit distance neighbourhoods of input-driven pushdown automata
- State complexity of deletion and bipolar deletion
This page was built for publication: Further closure properties of input-driven pushdown automata
