Complexity of term representations of finitary functions

DOI10.1142/S0218196718500480MaRDI QIDQ4687485zbMATH OpenOpenAlexFDO

Authors Erhard Aichinger, Nebojša Mudrinski, Jakub Opršal

Publication date 12 October 2018

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.01759

zbMATH Keywords

complexityprimal algebrasupernilpotent algebratermterm equivalenceterm function

Mathematics Subject Classification ID

Structure theory of algebraic structures (08A05) Operations and polynomials in algebraic structures, primal algebras (08A40)

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.

Recommendations

• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• scientific article; zbMATH DE number 3869406
• Finite algebras of finite complexity
• Valuations of terms
• scientific article; zbMATH DE number 3895132

Cites work

• A relational description of higher commutators in Mal'cev varieties
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• Congruence modular varieties with small free spectra
• Equivalence and equation solvability problems for the alternating group A₄.
• EVERY (k + 1)-AFFINE COMPLETE NILPOTENT GROUP OF CLASS k IS AFFINE COMPLETE
• Free spectra of nilpotent varieties
• scientific article; zbMATH DE number 3987347 (Why is no real title available?)
• scientific article; zbMATH DE number 4035895 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 1557989 (Why is no real title available?)
• Length of polynomials over finite groups
• On the Direct Decomposition of Nilpotent Expanded Groups
• On the number of finite Mal'tsev algebras
• Reducibility among combinatorial problems
• Some applications of higher commutators in Mal'cev algebras
• Supernilpotence prevents dualizability
• The structure of finite algebras

Cited in

(15)

• Complexity of terms, composition, and hypersubstitution
• Bounding the free spectrum of nilpotent algebras of prime power order
• Valuations of terms
• Three concepts of nilpotence in loops
• scientific article; zbMATH DE number 3869406 (Why is no real title available?)
• The length of terms and their measurement
• Solving systems of equations in supernilpotent algebras
• Congruence preserving expansions of nilpotent algebras
• Menger systems of idempotent cyclic and weak near-unanimity multiplace functions
• Superassociative structures of terms and formulas defined by transformations preserving a partition
• Supernilpotent groups and 3-supernilpotent loops
• Algebras of left variable terms
• Combinatorial results to measure the complexity of quantifier free formulas in algebraic systems
• A finite set of functions with an EXPTIME-complete composition problem
• Complexity of terms, superpositions, and generalized hypersubstitutions

This page was built for publication: Complexity of term representations of finitary functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4687485)