Characterizing \(\text{TC}^{0}\) in terms of infinite groups
From MaRDI portal
Publication:2643132
DOI10.1007/s00224-006-1310-2zbMath1121.68075MaRDI QIDQ2643132
Stephanie Reifferscheid, Andreas Krebs, Klaus-Joern Lange
Publication date: 23 August 2007
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-006-1310-2
68Q70: Algebraic theory of languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Linear circuits, two-variable logic and weakly blocked monoids, The algebraic theory of Parikh automata, Lamplighter groups and automata, The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\), The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\), A positive extension of Eilenberg's variety theorem for non-regular languages, A Language-Theoretical Approach to Descriptive Complexity, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages