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
Recommendations
- Deciding determinism of unary languages is coNP-complete
- Deciding determinism of regular languages
- Deterministic Pushdown Automata and Unary Languages
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
- Decidable unary varieties
- scientific article; zbMATH DE number 1948495
- scientific article
- Deciding FO-definability of regular languages
- scientific article; zbMATH DE number 3907798
- Inference of deterministic one-counter languages
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
- Introduction to algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- On a Problem of Partitions
- Two Families of Languages Related to ALGOL
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
Cited In (7)
- 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
- A special case of a unary regular language containment
- Title not available (Why is that?)
Uses Software
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)
