Critical classes for the \(\alpha _ 0\)-product
type: Item
instance of: scholarly article
title: Critical classes for the \(\alpha _ 0\)-product
zbMATH Open document ID: 0693.68033
DOI: 10.1016/0304-3975(88)90104-1
author: Pál Dömösi
author: Zoltán Ésik
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: A class \({\mathcal K}\) of automata is precomplete if it satisfies: (i) there exists an \(A\in {\mathcal K}\) such that the characteristic semigroup of the two-state identity reset automaton is isomorphic to a subsemigroup of the characteristic semigroup S(A) of A; (ii) for every simple group G there is an \(A\in {\mathcal K}\) such that \(G| S(A)\). A class \({\mathcal K}_ 0\) of automata is critical if for every precomplete class \({\mathcal K}\), the inclusion \({\mathcal K}_ 0\subseteq HSP_{\alpha_ 0}({\mathcal K})\) implies that \({\mathcal K}\) is complete for the \(\alpha_ 0\)-product. The paper gives a full description of the critical classes of automata. The notions of weakly precomplete and strongly critical classes are also considered.
reviewed by: G.Gauthier
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 4135406
zbMATH Keywords: \(\alpha_ 0\)-product of automata
zbMATH Keywords: Krohn-Rhodes decomposition theorem
zbMATH Keywords: homomorphic representation
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90104-1
OpenAlex ID: W2037608487
cites work: Q5570933
cites work: Complete classes of automata for the \(\alpha _ 0\)-product
cites work: On a representation of tree automata
cites work: Q5590815
description: scientific article; zbMATH DE number 4135406