Language operations with regular expressions of polynomial size
From MaRDI portal
Publication:2271463
DOI10.1016/j.tcs.2009.04.009zbMath1176.68105WikidataQ54152565 ScholiaQ54152565MaRDI QIDQ2271463
Publication date: 7 August 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.009
68Q45: Formal languages and automata
Related Items
The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata, The size-cost of Boolean operations on constant height deterministic pushdown automata, Two double-exponential gaps for automata with a limited pushdown, Boolean language operations on nondeterministic automata with a pushdown of constant height, THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS, Tight Bounds on the Descriptional Complexity of Regular Expressions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- From regular expressions to deterministic automata
- Local languages and the Berry-Sethi algorithm
- Intersection and union of regular languages and state complexity
- Regular expression for a language without empty word
- Follow automata.
- Canonical derivatives, partial derivatives and finite automaton constructions.
- General properties of star height of regular events
- GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
- State complexity of cyclic shift
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- On the State Complexity of Scattered Substrings and Superstrings
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Derivatives of Regular Expressions
- More on the Size of Higman-Haines Sets: Effective Constructions
