Complexity of terms, superpositions, and generalized hypersubstitutions

In this paper, we consider the four useful measurements of the complexity of a term, called the maximum depth, the minimum depth, the variable count, and the operation count. We construct a formula for the complexity of the superposition Sm(s, t1, ..., tm) in terms of complexity of the inputs s, t1,...

Full description

Saved in:

Bibliographic Details
Main Authors:	Wattapong Puninagool, Sorasak Leeratanavalee
Format:	Journal
Published:	2018
Subjects:	Computer Science Mathematics
Online Access:	https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=72949120350&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/50734
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Chiang Mai University

id	th-cmuir.6653943832-50734
record_format	dspace
spelling	th-cmuir.6653943832-507342018-09-04T04:49:44Z Complexity of terms, superpositions, and generalized hypersubstitutions Wattapong Puninagool Sorasak Leeratanavalee Computer Science Mathematics In this paper, we consider the four useful measurements of the complexity of a term, called the maximum depth, the minimum depth, the variable count, and the operation count. We construct a formula for the complexity of the superposition Sm(s, t1, ..., tm) in terms of complexity of the inputs s, t1, ..., tmfor each of these measurements. We also obtain formulas for the complexity of over(σ, ̂) [t] in terms of the complexity where t is a compound term and σ is a generalized hypersubstitution. We apply these formulas to the theory of M-strongly solid varieties, examining the k-normalization chains of a variety with respect to these complexity measurements. Crown Copyright © 2009. 2018-09-04T04:44:51Z 2018-09-04T04:44:51Z 2010-01-01 Journal 08981221 2-s2.0-72949120350 10.1016/j.camwa.2009.06.033 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=72949120350&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/50734
institution	Chiang Mai University
building	Chiang Mai University Library
country	Thailand
collection	CMU Intellectual Repository
topic	Computer Science Mathematics
spellingShingle	Computer Science Mathematics Wattapong Puninagool Sorasak Leeratanavalee Complexity of terms, superpositions, and generalized hypersubstitutions
description	In this paper, we consider the four useful measurements of the complexity of a term, called the maximum depth, the minimum depth, the variable count, and the operation count. We construct a formula for the complexity of the superposition Sm(s, t1, ..., tm) in terms of complexity of the inputs s, t1, ..., tmfor each of these measurements. We also obtain formulas for the complexity of over(σ, ̂) [t] in terms of the complexity where t is a compound term and σ is a generalized hypersubstitution. We apply these formulas to the theory of M-strongly solid varieties, examining the k-normalization chains of a variety with respect to these complexity measurements. Crown Copyright © 2009.
format	Journal
author	Wattapong Puninagool Sorasak Leeratanavalee
author_facet	Wattapong Puninagool Sorasak Leeratanavalee
author_sort	Wattapong Puninagool
title	Complexity of terms, superpositions, and generalized hypersubstitutions
title_short	Complexity of terms, superpositions, and generalized hypersubstitutions
title_full	Complexity of terms, superpositions, and generalized hypersubstitutions
title_fullStr	Complexity of terms, superpositions, and generalized hypersubstitutions
title_full_unstemmed	Complexity of terms, superpositions, and generalized hypersubstitutions
title_sort	complexity of terms, superpositions, and generalized hypersubstitutions
publishDate	2018
url	https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=72949120350&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/50734
_version_	1681423643246067712

Complexity of terms, superpositions, and generalized hypersubstitutions

Similar Items