Deciding determinism of unary languages

DOI10.1016/J.IC.2015.08.005MaRDI QIDQ897659zbMATH OpenOpenAlexFDO

Authors Ping Lu, Feifei Peng, Haiming Chen, 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

zbMATH Keywords

regular expressionscoNP-completedeterministic languagesminimal DFAregular expressions with counting

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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; zbMATH DE number 165816
• Deciding FO-definability of regular languages
• scientific article; zbMATH DE number 3907798
• Inference of deterministic one-counter languages

Cites work

• scientific article; zbMATH DE number 1801402 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 3335736 (Why is no real title available?)
• scientific article; zbMATH DE number 3063030 (Why is no real title available?)
• Checking determinism of regular expressions with counting
• Deciding definability by deterministic regular expressions
• Deciding determinism of regular languages
• Definability by weakly deterministic regular expressions with counters is decidable
• Descriptional complexity of deterministic regular expressions
• Efficient construction of semilinear representations of languages accepted by unary NFA
• Finite automata and unary languages
• Introduction to algorithms
• On a Problem of Partitions
• One-unambiguous regular languages
• Prime Decompositions of Regular Languages
• Regular Expressions and NFAs Without ε-Transitions
• Regular expressions into finite automata
• Regular expressions with counting: weak versus strong determinism
• Succinctness of regular expressions with interleaving, intersection and counting
• The complexity of regular(-like) expressions
• Two Families of Languages Related to ALGOL
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Unsolved problems in number theory

Cited in

(9)

• Closure properties and descriptional complexity of deterministic regular expressions
• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Usefulness of information and unary languages
• Efficient testing and matching of deterministic regular expressions
• The complexity of SORE-definability problems
• A special case of a unary regular language containment
• Deciding determinism of unary languages is coNP-complete
• scientific article; zbMATH DE number 1670861 (Why is no real title available?)
• Deciding definability by deterministic regular expressions

Describes a project that uses

Uses Software

• ALGOL 60

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)