scientific article; zbMATH DE number 4041299
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)].
- Programs over aperiodic monoids
- Extensions to Barrington's M-program model
- An ergodic theorem for read-once non-uniform deterministic finite automata
- The complexity of the equation solvability problem over nilpotent groups
- The complexity of solving equations over finite groups
- Learning read-constant polynomials of constant degree modulo composites
- Languages and formations generated by \(D_4\) and \(Q_8\)
- Learning Read-Constant Polynomials of Constant Degree Modulo Composites
- Literal Varieties of Languages Induced by Homomorphisms onto Nilpotent Groups
- Languages recognized by finite supersoluble groups
- An Algebraic Perspective on Boolean Function Learning
- scientific article; zbMATH DE number 4033093 (Why is no real title available?)
- scientific article; zbMATH DE number 1047940 (Why is no real title available?)
- scientific article; zbMATH DE number 1744112 (Why is no real title available?)
- The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
- Non-uniform automata over groups
- Recognizing group languages with OBDDs
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)