scientific article; zbMATH DE number 4216027

MaRDI QIDQ3363320zbMATH OpenFDO

Authors Dung T. Huynh

Publication date 1992

zbMATH Keywords

codecompletenessfinite automatamonoidreducibilityregular setsTuring machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
• scientific article; zbMATH DE number 1254106
• Complexity results on the conjugacy problem for monoids
• Bounds on the variety generated by completely regular syntactic monoids from finite prefix codes
• scientific article; zbMATH DE number 4210423
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Developments in Language Theory
• scientific article; zbMATH DE number 1916674
• Computations over finite monoids and their test complexity
• Generic complexity of finitely presented monoids and semigroups

Cited in

(5)

• Checking whether an automaton is monotonic is NP-complete
• It is decidable whether a monadic thue system is canonical over a regular set
• THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
• scientific article; zbMATH DE number 826059 (Why is no real title available?)
• Parallel complexity of the regular code problem

This page was built for publication:

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