No label defined (Q3219765)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3887074
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3887074 |
Statements
1984
0 references
circuits over universal algebras
0 references
straight-line algorithms
0 references
computational functors
0 references
0.8317497968673706
0 references
0.7785241603851318
0 references
0.7573121786117554
0 references
0.7490501403808594
0 references
0.7455343008041382
0 references
[For the entire collection see Zbl 0533.00025.] The paper deals with straight-line algorithms (or shortly, circuits) over universal algebras. This new notion represents a far going generalization of both Boolean and arithmetical circuits. Let (K,\(\Omega)\) be a universal algebra, with K being a set and \(\Omega\) an operator domain; syntactically, a circuit is a linear list of operators from \(\Omega\) which use as arguments foregoing items of the list and/or input variables. A circuit \({\mathfrak a}\) with m inputs and n outputs, over (K,\(\Omega)\), computes, in an ''obvious'' (or standard) way, a function \({\mathfrak f}:K^ m\to K^ n\); or, in other words, the standard (S-) operation mode over \({\mathfrak a}\) generates the standard (S-) functional representation of \({\mathfrak a}\), \({\mathfrak f}=S({\mathfrak a})\), S:\({\mathfrak A}(K,\Omega)\to {\mathfrak F}(K)\), where \({\mathfrak A}(K,\Omega)\) is the set of all circuits over (K,\(\Omega)\) and \({\mathfrak F}(K)\) is the set of allcomputable (over \(\Omega)\) functions over K. Both sets are categories, and the S-representation turns out to be a covariant functor. The central innovative idea of the paper can be stated as follows: Multipurpose Thesis. A circuit can be used for computations according to different operation modes, and the S-mode is only one of them. Or, in other words, along with the S-functor, there exist other (nonstandard) computational functors between the categories \({\mathfrak A}(K,\Omega)\), \({\mathfrak F}(K)\) as well. - Using the construction of one of those nonstandard modes (namely, the mincing (M-)mode), one can prove the important inequality: \(\dim (Image(M({\mathfrak a})))\leq size({\mathfrak a}),\) \({\mathfrak a}\in {\mathfrak A}(K,\Omega)\), which leads to the first nontrivial general lower bound to the size (in other terminologies: circuit, combinational, etc.) complexity \(c({\mathfrak f})\) of a function \({\mathfrak f}\in {\mathfrak F}(K):\) \(m({\mathfrak f})\leq c(f)\), where \(m({\mathfrak f})\) is the new numerical parameter of \({\mathfrak f}\), its mincing complexity: \(m({\mathfrak f}):=\min \{\dim (Image(M({\mathfrak a})))| {\mathfrak a}\in {\mathfrak A}(K,\Omega) \& {\mathfrak f}=S({\mathfrak a})\}.\) The force of this reduction is illustrated by a characteristic example.
0 references