Complexity of terms, composition, and hypersubstitution (Q1864336): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Set OpenAlex properties.
 
(3 intermediate revisions by 2 users not shown)
Property / author
 
Property / author: Klaus Denecke / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Magnus Steinby / rank
Normal rank
 
Property / author
 
Property / author: Klaus Denecke / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Magnus Steinby / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2140984997 / rank
 
Normal rank

Latest revision as of 09:14, 30 July 2024

scientific article
Language Label Description Also known as
English
Complexity of terms, composition, and hypersubstitution
scientific article

    Statements

    Complexity of terms, composition, and hypersubstitution (English)
    0 references
    0 references
    0 references
    17 March 2003
    0 references
    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.
    0 references
    complexity of terms
    0 references
    solid varieties
    0 references
    hypersubstitutions
    0 references

    Identifiers