The Power of Diversity

DOI10.1007/978-3-642-22600-7_4zbMath1341.68127OpenAlexW152473595MaRDI QIDQ5200079

Denis Thérien

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_4

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (1)

Generic results for concatenation hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• \(NC^ 1\): The automata-theoretic viewpoint
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Classification of finite monoids: the language approach
• The dot-depth hierarchy of star-free languages is infinite
• Superlinear lower bounds for bounded-width branching programs
• Varieties of finite supersolvable groups with the M.~Hall property.
• Parity, circuits, and the polynomial-time hierarchy
• Bounds for Width Two Branching Programs
• Finite monoids and the fine structure of NC ¹
• On finite monoids having only trivial subgroups
• A Property of Finite Simple Non-Abelian Groups
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines

This page was built for publication: The Power of Diversity