scientific article; zbMATH DE number 4041299

From MaRDI portal
Publication:3779765





Denote \([n]=\{1,2,...,n\}\) and let M be a finite monoid. Each element of \([n]\times M^{\{0,1\}}\) is called statement and a finite sequence \(P=v_ 1...v_ t\) of statements is called a program (on M). Such a program defines a mapping of \(\{\) 0,1\(\}^ n \)to M, setting for \(w=w_ 1...w_ n\in \{0,1\}^ n,\) \(P(w)=v_ 1(w)...v_ t(w)\), where \((i,f)(w)=f(w_ i)\). A subset \(L\subseteq \{0,1\}^ n \)is said to be recognized by M if there is a program P and a subset \(F\subseteq M\) such that \(L=P^{-1}(F).\) This notion, generalizing the recognizing by finite automata, has been formalized by \textit{D. Barrington} and the second author [Finite monoids and the fine structure of \(NC_ 1\), Proc. 19th ACM STOC, 1987, 101-107]. The present paper proves that each non-empty subset of \(\{\) 0,1\(\}^ n \)recognized by a nilpotent group has exponential cardinality [this generalizes a result by \textit{D. Barrington} and the second author, Lect. Notes Comput. Sci. 267, 163-173 (1987; Zbl 0634.68054)].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3779765)