Complexity of term representations of finitary functions

Erhard Aichinger; Nebojsa Mudrinski; Jakub Oprsal

doi:10.1142/S0218196718500480

Complexity of term representations of finitary functions

Erhard Aichinger
, Nebojsa Mudrinski
, Jakub Oprsal

Institute for Algebra

Research output: Contribution to journal › Article › peer-review

Abstract

The clone of term operations of an algebraic structure consists of all operations that can be expressed by a term in the language of the structure. We consider bounds for the length and the height of the terms expressing these functions, and we show that these bounds are often robust against the change of the basic operations of the structure.

Original language	English
Pages (from-to)	1101-1118
Number of pages	18
Journal	International Journal of Algebra and Computation
Volume	28
Issue number	6
DOIs	https://doi.org/10.1142/S0218196718500480
Publication status	Published - 2018

Fields of science

101 Mathematics
101001 Algebra
101005 Computer algebra
101013 Mathematical logic
102031 Theoretical computer science

JKU Focus areas

Computation in Informatics and Mathematics
Engineering and Natural Sciences (in general)

Access to Document

10.1142/S0218196718500480

Cite this

@article{78f66c89331c42be99b7204ae237b8b2,

title = "Complexity of term representations of finitary functions",

abstract = "The clone of term operations of an algebraic structure consists of all operations that can be expressed by a term in the language of the structure. We consider bounds for the length and the height of the terms expressing these functions, and we show that these bounds are often robust against the change of the basic operations of the structure.",

author = "Erhard Aichinger and Nebojsa Mudrinski and Jakub Oprsal",

year = "2018",

doi = "10.1142/S0218196718500480",

language = "English",

volume = "28",

pages = "1101--1118",

journal = "International Journal of Algebra and Computation",

issn = "0218-1967",

publisher = "World Scientific Publishing Company",

number = "6",

}

TY - JOUR

T1 - Complexity of term representations of finitary functions

AU - Aichinger, Erhard

AU - Mudrinski, Nebojsa

AU - Oprsal, Jakub

PY - 2018

Y1 - 2018

N2 - The clone of term operations of an algebraic structure consists of all operations that can be expressed by a term in the language of the structure. We consider bounds for the length and the height of the terms expressing these functions, and we show that these bounds are often robust against the change of the basic operations of the structure.

AB - The clone of term operations of an algebraic structure consists of all operations that can be expressed by a term in the language of the structure. We consider bounds for the length and the height of the terms expressing these functions, and we show that these bounds are often robust against the change of the basic operations of the structure.

UR - https://www.scopus.com/pages/publications/85050296314

U2 - 10.1142/S0218196718500480

DO - 10.1142/S0218196718500480

M3 - Article

SN - 0218-1967

VL - 28

SP - 1101

EP - 1118

JO - International Journal of Algebra and Computation

JF - International Journal of Algebra and Computation

IS - 6

ER -

Complexity of term representations of finitary functions

Abstract

Fields of science

JKU Focus areas

Access to Document

Other files and links

Clonoids: a unifying approach to equational logic and clones

Cite this

Complexity of term representations of finitary functions

Abstract

Fields of science

JKU Focus areas

Access to Document

Other files and links

Projects

Clonoids: a unifying approach to equational logic and clones

Cite this