Deciding determinism of unary languages
DOI10.1016/J.IC.2015.08.005zbMATH Open1332.68122OpenAlexW1862704942MaRDI QIDQ897659FDOQ897659
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
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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?)
- Introduction to algorithms
- Checking determinism of regular expressions with counting
- Descriptional Complexity of Deterministic Regular Expressions
- Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
- Deciding Definability by Deterministic Regular Expressions
- Deciding determinism of regular languages
- Regular expressions with counting: weak versus strong determinism
- Unsolved problems in number theory
- On a Problem of Partitions
- Two Families of Languages Related to ALGOL
- Finite automata and unary languages
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Regular Expressions and NFAs Without Ξ΅-Transitions
- Succinctness of regular expressions with interleaving, intersection and counting
- One-unambiguous regular languages
- Regular expressions into finite automata
- Prime Decompositions of Regular Languages
- The complexity of regular(-like) expressions
- Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
Cited In (6)
- Closure properties and descriptional complexity of deterministic regular expressions
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
- Title not available (Why is that?)
- Usefulness of information and unary languages
- Efficient testing and matching of deterministic regular expressions
- Title not available (Why is that?)
Uses Software
Recommendations
- Deciding determinism of regular languages π π
- Decidable unary varieties π π
- Inference of deterministic one-counter languages π π
- Deciding FO-definability of regular languages π π
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES π π
- Deterministic Pushdown Automata and Unary Languages π π
- Deciding Determinism of Unary Languages Is coNP-Complete π π
- Title not available (Why is that?) π π
- Title not available (Why is that?) π π
- Title not available (Why is that?) π π
This page was built for publication: Deciding determinism of unary languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897659)
