THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS

DOI10.1142/S0218196792000050MaRDI QIDQ4711250zbMATH OpenOpenAlexFDO

Authors Dung T. Huynh

Publication date 25 June 1992

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218196792000050

zbMATH Keywords

codecompletenessfinite automatamonoidreducibilityregular setsTuring machine

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4216027
• 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

(3)

• It is decidable whether a monadic thue system is canonical over a regular set
• scientific article; zbMATH DE number 4216027 (Why is no real title available?)
• The complexity of reachability problems in strongly connected finite automata

This page was built for publication: THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS

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