Closure properties and descriptional complexity of deterministic regular expressions
From MaRDI portal
Publication:265078
DOI10.1016/j.tcs.2016.02.027zbMath1338.68154OpenAlexW2280368318MaRDI QIDQ265078
Matthias Niewerth, Katja Losemann, Wim Martens
Publication date: 1 April 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.027
automata theoryBoolean operationsdescriptional complexitydeterministic regular expressionsone-unambiguous languages
Related Items (3)
Definability by Weakly Deterministic Regular Expressions with Counters is Decidable ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Deterministic regular expressions with back-references
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simplifying XML schema: single-type approximations of regular tree languages
- Deciding determinism of regular languages
- On the state complexity of reversals of regular languages
- Deciding determinism of unary languages
- Amounts of nondeterminism in finite automata
- Complexity measures for regular expressions
- The state complexities of some basic operations on regular languages
- Checking determinism of regular expressions with counting
- One-unambiguity of regular expressions with numeric occurrence indicators
- Descriptional Complexity of Deterministic Regular Expressions
- Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
- Succinctness of the Complement and Intersection of Regular Expressions
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Regular Expressions with Numerical Constraints and Automata with Counters
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- On the State Complexity of Complements, Stars, and Reversals of Regular Languages
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Deciding Definability by Deterministic Regular Expressions
- Generalized One-Unambiguity
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Regular Expressions with Counting: Weak versus Strong Determinism
- One-unambiguous regular languages
This page was built for publication: Closure properties and descriptional complexity of deterministic regular expressions
