Deciding determinism of unary languages is coNP-complete

DOI10.1007/978-3-642-38771-5_31zbMATH Open1381.68127OpenAlexW91306599MaRDI QIDQ5300853FDOQ5300853

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

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

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)

Cited In (3)

• Deciding determinism of unary languages
• A special case of a unary regular language containment
• Title not available (Why is that?)

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)