Complexity of terms, composition, and hypersubstitution

Klaus Denecke and Shelly L. Wismath

International Journal of Mathematics and Mathematical Sciences, 2003, vol. 2003, 1-11

Abstract:

We consider four useful measures of the complexity of a term: the maximum depth (usually called the depth), the minimum depth, the variable count, and the operation count. For each of these, we produce a formula for the complexity of the composition S m n ( s , t 1 , … , t n ) in terms of the complexity of the inputs s , t 1 , … , t n . As a corollary, we also obtain formulas for the complexity of σ ˆ [ t ] in terms of the complexity of t when t is a compound term and σ is a hypersubstitution. We then apply these formulas to the theory of M -solid varieties, examining the k -normalization chains of a variety with respect to the four complexity measures.

Date: 2003
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/2003/705684.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/2003/705684.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:705684

DOI: 10.1155/S0161171203202118

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().