Succinctness of regular expressions with interleaving, intersection and counting
From MaRDI portal
Publication:982670
DOI10.1016/J.TCS.2010.04.036zbMATH Open1192.68120OpenAlexW1987660690MaRDI QIDQ982670FDOQ982670
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
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity measures for regular expressions
- State complexity of regular languages
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Transition graphs and the star-height of regular events
- A note on the space complexity of some decision problems for finite automata
- Regular expressions into finite automata
- The loop complexity of pure-group events
- Rank-non-increasing transformations on transition graphs
- Provably Shorter Regular Expressions from Deterministic Finite Automata
- The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space
Cited In (15)
- Regular Expressions with Counting: Weak versus Strong Determinism
- Derivatives for Regular Shuffle Expressions
- PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
- Deciding determinism of unary languages
- The tractability frontier for NFA minimization
- On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection
- Succinctness of the Complement and Intersection of Regular Expressions
- Intersection of \(-\omega \)-regular expressions
- Derivatives and partial derivatives for regular shuffle expressions
- Games for succinctness of regular expressions
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- An application of temporal projection to interleaving concurrency
- Descriptional complexity of regular languages
- Position Automaton Construction for Regular Expressions with Intersection
- Automata for regular expressions with shuffle
Uses Software
This page was built for publication: Succinctness of regular expressions with interleaving, intersection and counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q982670)
