Some complexity results for polynomial rational expressions.

DOI10.1016/S0304-3975(01)00342-5zbMath1042.68063MaRDI QIDQ1874419

Pierre-Cyrille Héam

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Straubing-Thérien hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Efficiency of automata in semi-commutation verification techniques ⋮ On Shuffle Ideals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inverse monoids of dot-depth two
• Classification of finite monoids: the language approach
• Polynomial operations and hierarchies of concatenation
• Some results on the dot-depth hierarchy
• Complexity measures for regular expressions
• The dot-depth hierarchy of star-free languages is infinite
• Sur le produit de concatenation non ambigu
• Polynomial closure and unambiguous product
• Finite semigroup varieties of the form V*D
• Complexity of some problems from the theory of automata
• Polynomial closure of group languages and open sets of the Hall topology

This page was built for publication: Some complexity results for polynomial rational expressions.