Succinctness of regular expressions with interleaving, intersection and counting
From MaRDI portal
Publication:982670
DOI10.1016/j.tcs.2010.04.036zbMath1192.68120OpenAlexW1987660690MaRDI QIDQ982670
Publication date: 7 July 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1942/12824
Related Items
An application of temporal projection to interleaving concurrency ⋮ Deciding determinism of unary languages ⋮ Derivatives and partial derivatives for regular shuffle expressions ⋮ The tractability frontier for NFA minimization ⋮ Automata for regular expressions with shuffle ⋮ PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA ⋮ Derivatives for Regular Shuffle Expressions ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Position Automaton Construction for Regular Expressions with Intersection ⋮ On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection ⋮ Descriptional complexity of regular languages
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space
- A note on the space complexity of some decision problems for finite automata
- Complexity measures for regular expressions
- Regular expressions into finite automata
- Transition graphs and the star-height of regular events
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- Provably Shorter Regular Expressions from Deterministic Finite Automata
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- The loop complexity of pure-group events
- Rank-non-increasing transformations on transition graphs
