•  
  •  
 

Turkish Journal of Mathematics

DOI

-

Abstract

A tree is a connected (undirected) graph that contains no cycles. Trees play an important role in Computer Science. There are many applications in this field. Ordered binary decision diagrams are trees in the language of Boolean algebras. For the applications, it is important to measure the complexity of a tree or of a polynomial. The complexity of a polynomial over an arbitrary algebra can be regarded as a valuation. The concept of the valuations of terms was introduced by K. Denecke and S. L. Wismath in [5]. In [6], the author defined the depth of a polynomial which is an example of a complexity measure for polynomials. In this paper we study several other measures of the complexity of polynomials. In each of these measures, we have a mapping v: P_\tau(X, \overline A)\longrightarrow \natur from the set of all polynomials of type \tau over \overline A to the set of natural numbers (including 0) which assigns to each polynomial p a complexity number or a value v(p). We will refer to such a function as a complexity or a cost function or a valuation and we study some properties of these valuations.

Keywords

Polynomials, valuations of polynomials, Order Condition, Algebraic Subpolynomial Condition, Subpolynomial Condition

First Page

413

Last Page

425

Download

Included in

Mathematics Commons

Share

COinS