Complexity of terms, composition, and hypersubstitution

DOI10.1155/S0161171203202118MaRDI QIDQ1864336zbMATH OpenOpenAlexFDO

Authors Shelly L. Wismath, Klaus Denecke

Publication date 17 March 2003

Published in International Journal of Mathematics and Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/50113

zbMATH Keywords

complexity of termshypersubstitutionssolid varieties

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Finitary algebras (08A62) Varieties (08B99)

Review text

The authors present formulae for computing the complexity of the composition \(s(t_1,\dots,t_n)\) of an \(n\)-ary term \(s\) and \(n\) terms \(t_1,\dots,t_n\) of some arity \(m\) \((m,n\geq 1)\) for four measures of the complexity of a term: the maximal depth, the minimal depth, the total number of variable occurrences, and the total number of function symbol occurrences. Formulae for the complexities of terms resulting from hypersubstitutions are obtained as special cases; a hypersubstitution maps terms to terms by replacing each function symbol by a term of the same arity. A variety \(V\) of algebras is said to be \(M\)-solid, for a given set \(M\) of hypersubstitutions, if \(V\) satisfies every identity obtained by applying a hypersubstitution from \(M\) to both sides of an identity satisfied by \(V\). The above mentioned results yield some conditions for the preservation of such solidity properties when new varieties are derived in a certain way from an \(M\)-solid variety.

Recommendations

• Complexity of terms, superpositions, and generalized hypersubstitutions
• Compositionality, computability, and complexity
• On the Concept of Compositional Complexity
• Complexity of hypersubstitutions and lattices of varieties
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• Complexity of term representations of finitary functions
• scientific article; zbMATH DE number 1342223
• The complexity of some complementation problems
• Complexity, decidability and completeness
• The complexity of explicit constructions

Cited in

(13)

• Essential variables and positions in terms
• Valuations of terms
• The order of hypersubstitutions of type \((2, 2)\)
• Semigroup properties of linear terms
• The Depth of a Hypersubstitution
• Complexity of hypersubstitutions and lattices of varieties
• The length of terms and their measurement
• Partial Menger algebras of terms
• Semigroups of an inductive composition of terms
• The order of hypersubstitutions of type \((2,1)\)
• The partial clone of completely expanded terms
• Combinatorial results to measure the complexity of quantifier free formulas in algebraic systems
• Complexity of terms, superpositions, and generalized hypersubstitutions

This page was built for publication: Complexity of terms, composition, and hypersubstitution

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