Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Characterizing TC0 in Terms of Infinite Groups
verfasst von : Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid
Erschienen in: STACS 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We characterize the languages in TC
0
=
$\mathcal{L}(Maj[<,Bit])$
and
$\mathcal{L}(Maj[<])$
as inverse morphic images of certain groups. Necessarily these are infinite, since nonregular sets are concerned. To limit the power of these infinite algebraic objects, we equip them with a finite
type set
and introduce the notion of a
finitely typed
(infinite) monoid. Following this approach we investigate
type respecting
mappings and construct a new type of block product, which is more adequate to deal with infinite monoids. We exhibit two classes of finitely typed groups which exactly characterize TC
0
and
$\mathcal{L}(Maj[<])$
via inverse morphisms.