A deterministic (probabilistic) automaton is said to be in TC0 whenever its transitions (stochastic event) can be computed by threshold circuits of polynomial size and constant depth. Here, we prove that: The class of deterministic automata in TC0 is closed under homomorphism, sub-automaton, and alpha0-product operations. The class of k-state deterministic (probabilistic) automata is contained in TC0 if and only if k les 4 (k les 2), unless TC0 = NC1. Moreover, the possibility of ranking regular languages in TC0 is related to the group-structure of their syntactic monoid.
The parallel complexity of deterministic and probabilistic automata / C. Mereghetti, B. Palano. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - 7:1(2002), pp. 95-108. [10.25596/jalc-2002-095]
The parallel complexity of deterministic and probabilistic automata
C. MereghettiPrimo
;B. PalanoUltimo
2002
Abstract
A deterministic (probabilistic) automaton is said to be in TC0 whenever its transitions (stochastic event) can be computed by threshold circuits of polynomial size and constant depth. Here, we prove that: The class of deterministic automata in TC0 is closed under homomorphism, sub-automaton, and alpha0-product operations. The class of k-state deterministic (probabilistic) automata is contained in TC0 if and only if k les 4 (k les 2), unless TC0 = NC1. Moreover, the possibility of ranking regular languages in TC0 is related to the group-structure of their syntactic monoid.File | Dimensione | Formato | |
---|---|---|---|
jalc02.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
262.35 kB
Formato
Adobe PDF
|
262.35 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.