Descriptional complexity of unambiguous input-driven pushdown automata
From MaRDI portal
Publication:484313
DOI10.1016/J.TCS.2014.11.015zbMATH Open1318.68111OpenAlexW2079567772MaRDI QIDQ484313FDOQ484313
Authors: Alexander Okhotin, Kai Salomaa 
Publication date: 6 January 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.11.015
Recommendations
- Descriptional complexity of input-driven pushdown automata
- Descriptional complexity of unambiguous nested word automata
- Towards exact state complexity bounds for input-driven pushdown automata
- State complexity of operations on input-driven pushdown automata
- Input-Driven Pushdown Automata with Limited Nondeterminism
descriptional complexitynondeterminismunambiguityinput-driven pushdown automatanested word automatavisibly pushdown automata
Cites Work
- Title not available (Why is that?)
- Visibly pushdown languages
- Adding nesting structure to words
- Streaming tree automata
- A Second Course in Formal Languages and Automata Theory
- On the Expressive Power of 2-Stack Visibly Pushdown Automata
- Descriptional and computational complexity of finite automata -- a survey
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Complementing two-way finite automata
- Title not available (Why is that?)
- State complexity of some operations on binary regular languages
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- State complexity of operations on input-driven pushdown automata
- Title not available (Why is that?)
- Intersection and union of regular languages and state complexity
- Communication complexity method for measuring nondeterminism in finite automata
- Operational state complexity of nested word automata
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Unambiguous finite automata over a unary alphabet
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Descriptional complexity of input-driven pushdown automata
- Mathematical Foundations of Computer Science 2005
- An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
- On the relation between ambiguity and nondeterminism in finite automata
- Nondeterministic state complexity of nested word automata
- Minimizing Variants of Visibly Pushdown Automata
- Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
- Limitations of lower bound methods for deterministic nested word automata
- Automata, Languages and Programming
Cited In (17)
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
- Edit distance neighbourhoods of input-driven pushdown automata
- State complexity of the quotient operation on input-driven pushdown automata
- Edit distance neighbourhoods of input-driven pushdown automata
- Title not available (Why is that?)
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- State complexity of operations on input-driven pushdown automata
- Descriptional complexity of unambiguous nested word automata
- Title not available (Why is that?)
- Descriptional complexity of (un)ambiguous finite state machines and pushdown automata
- Descriptional complexity of input-driven pushdown automata
- Title not available (Why is that?)
- A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
- Unambiguity in automata theory
- Further closure properties of input-driven pushdown automata
- Input-driven pushdown automata on well-nested infinite strings
- Towards exact state complexity bounds for input-driven pushdown automata
This page was built for publication: Descriptional complexity of unambiguous input-driven pushdown automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484313)
