Complexity of term representations of finitary functions

Erhard Aichinger; Nebojsa Mudrinski; Jakub Oprsal

doi:10.48550/arXiv.1709.01759

Complexity of term representations of finitary functions

Erhard Aichinger, Nebojsa Mudrinski, Jakub Oprsal

Institute for Algebra

Research output: Working paper and reports › Preprint

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
Number of pages	13
DOIs	https://doi.org/10.48550/arXiv.1709.01759
Publication status	Published - Sept 2017

Publication series

Name	arXiv.org
No.	arXiv:1709.01759
ISSN (Print)	2331-8422

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.48550/arXiv.1709.01759

Clonoids: a unifying approach to equational logic and clones
Aichinger, E. (PI)
01.02.2017 → 31.01.2020
Project: Funded research › FWF - Austrian Science Fund

Cite this

@techreport{e04e13b185fc442bb2f0505a4327381f,

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 = "2017",

month = sep,

doi = "10.48550/arXiv.1709.01759",

language = "English",

series = "arXiv.org",

number = "arXiv:1709.01759",

type = "WorkingPaper",

}

TY - UNPB

T1 - Complexity of term representations of finitary functions

AU - Aichinger, Erhard

AU - Mudrinski, Nebojsa

AU - Oprsal, Jakub

PY - 2017/9

Y1 - 2017/9

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.

U2 - 10.48550/arXiv.1709.01759

DO - 10.48550/arXiv.1709.01759

M3 - Preprint

T3 - arXiv.org

BT - Complexity of term representations of finitary functions

ER -

Complexity of term representations of finitary functions

Abstract

Publication series

Fields of science

JKU Focus areas

Access to Document

Projects

Clonoids: a unifying approach to equational logic and clones

Cite this