Deciding determinism of unary languages
From MaRDI portal
Publication:897659
DOI10.1016/j.ic.2015.08.005zbMath1332.68122OpenAlexW1862704942MaRDI QIDQ897659
Haiming Chen, Feifei Peng, Ping Lu, Lixiao Zheng
Publication date: 7 December 2015
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2015.08.005
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
Closure properties and descriptional complexity of deterministic regular expressions ⋮ Efficient testing and matching of deterministic regular expressions ⋮ Unnamed Item
Uses Software
Cites Work
- Deciding determinism of regular languages
- Succinctness of regular expressions with interleaving, intersection and counting
- Finite automata and unary languages
- Regular expressions into finite automata
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Checking determinism of regular expressions with counting
- THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS
- Descriptional Complexity of Deterministic Regular Expressions
- Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
- Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
- Prime Decompositions of Regular Languages
- Deciding Definability by Deterministic Regular Expressions
- Regular Expressions and NFAs Without ε-Transitions
- Two Families of Languages Related to ALGOL
- On a Problem of Partitions
- Regular Expressions with Counting: Weak versus Strong Determinism
- One-unambiguous regular languages
- Unsolved problems in number theory
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Deciding determinism of unary languages
