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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2014
|
| Online Access: | http://www.scopus.com/inward/record.url?eid=2-s2.0-72949120350&partnerID=40&md5=9db24f2fc57e36bc0796e91567ff67d6 http://cmuir.cmu.ac.th/handle/6653943832/6368 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| Language: | English |
| id |
th-cmuir.6653943832-6368 |
|---|---|
| record_format |
dspace |
| spelling |
th-cmuir.6653943832-63682014-08-30T03:24:08Z Complexity of terms, superpositions, and generalized hypersubstitutions Puninagool W. Leeratanavalee S. 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, ..., tm for 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. 2014-08-30T03:24:08Z 2014-08-30T03:24:08Z 2010 Article 8981221 10.1016/j.camwa.2009.06.033 CMAPD http://www.scopus.com/inward/record.url?eid=2-s2.0-72949120350&partnerID=40&md5=9db24f2fc57e36bc0796e91567ff67d6 http://cmuir.cmu.ac.th/handle/6653943832/6368 English |
| institution |
Chiang Mai University |
| building |
Chiang Mai University Library |
| country |
Thailand |
| collection |
CMU Intellectual Repository |
| language |
English |
| 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, ..., tm for 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 |
Article |
| author |
Puninagool W. Leeratanavalee S. |
| spellingShingle |
Puninagool W. Leeratanavalee S. Complexity of terms, superpositions, and generalized hypersubstitutions |
| author_facet |
Puninagool W. Leeratanavalee S. |
| author_sort |
Puninagool W. |
| 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 |
2014 |
| url |
http://www.scopus.com/inward/record.url?eid=2-s2.0-72949120350&partnerID=40&md5=9db24f2fc57e36bc0796e91567ff67d6 http://cmuir.cmu.ac.th/handle/6653943832/6368 |
| _version_ |
1681420600783929344 |