On the complexity of universality for partially ordered NFAs

DOI10.4230/LIPICS.MFCS.2016.61MaRDI QIDQ4608624zbMATH OpenFDO

Authors Markus Krötzsch, Tomáš Masopust, Michaël Thomazo

Publication date 21 March 2018

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2016.61

zbMATH Keywords

partial orderautomatanondeterminismuniversality

Mathematics Subject Classification ID

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

Recommendations

• Complexity of universality and related problems for partially ordered NFAs
• Deciding Universality of ptNFAs is PSpace-Complete
• scientific article; zbMATH DE number 1059319
• Partial orders on words, minimal elements of regular languages, and state complexity
• On the Computational Complexity of Partial Word Automata Problems

Cited in

(3)

• Deciding Universality of ptNFAs is PSpace-Complete
• Complexity of universality and related problems for partially ordered NFAs
• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes

This page was built for publication: On the complexity of universality for partially ordered NFAs

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