Deciding determinism of unary languages is coNP-complete

DOI10.1007/978-3-642-38771-5_31MaRDI QIDQ5300853zbMATH OpenOpenAlexFDO

Authors Ping Lu, Feifei Peng, Haiming Chen

Publication date 28 June 2013

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38771-5_31

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
• Automaticity. II: Descriptional complexity in the unary case
• Deciding determinism of regular languages
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Deciding definability by deterministic regular expressions

Cited in

(3)

• Deciding determinism of unary languages
• A special case of a unary regular language containment
• scientific article; zbMATH DE number 1696827 (Why is no real title available?)

This page was built for publication: Deciding determinism of unary languages is coNP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300853)