State Complexity of Kleene-Star Operations on Trees
From MaRDI portal
Publication:2891328
DOI10.1007/978-3-642-27654-5_30zbMath1353.68171OpenAlexW2098375093MaRDI QIDQ2891328
Publication date: 15 June 2012
Published in: Computation, Physics and Beyond (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-27654-5_30
Related Items
State complexity of the concatenation of regular tree languages ⋮ Lower bounds for the size of deterministic unranked tree automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptional and computational complexity of finite automata -- a survey
- Finite state complexity
- Automata for XML -- a survey
- On the minimization of XML schemas and tree automata for unranked trees
- State complexity of power
- General varieties of tree languages
- The state complexities of some basic operations on regular languages
- State complexity of combined operations
- STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY
- Undecidability of the State Complexity of Composed Regular Operations
- Nondeterminism Is Essential in Small 2FAs with Few Reversals
- Transformations Between Different Models of Unranked Bottom-Up Tree Automata
- Transition Complexity of Incomplete DFAs
- On the State Complexity of Operations on Two-Way Finite Automata
- A Second Course in Formal Languages and Automata Theory
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal
- State Trade-Offs in Unranked Tree Automata
- Fundamentals of Computation Theory
This page was built for publication: State Complexity of Kleene-Star Operations on Trees