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 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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references