Skip to main navigation Skip to search Skip to main content

A minimal substitution basis for the Kalmár elementary functions

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

Abstract

We show that the class of Kalmár elementary functions can be inductively generated from the addition, the integer remainder and the base-two exponentiation, hence improving previous results by Marchenkov and Mazzanti. We also prove that the substitution basis defined by these three operations is minimal. Furthermore, we discuss alternative substitution bases under arity constraints.

Original languageEnglish
Article numberexag010
JournalJournal of Logic and Computation
Volume36
Issue number3
DOIs
StatePublished - 1 Apr 2026
Externally publishedYes

Bibliographical note

Publisher Copyright:
© The Author(s) 2026. Published by Oxford University Press. All rights reserved.

Keywords

  • 2020 Mathematics Subject Classification: 03D20 (primary)
  • Grzegorczyk’s hierarchy
  • arithmetic term
  • closed form
  • elementary function
  • elementary operation
  • explicit formula

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Arts and Humanities (miscellaneous)
  • Hardware and Architecture
  • Logic

Fingerprint

Dive into the research topics of 'A minimal substitution basis for the Kalmár elementary functions'. Together they form a unique fingerprint.

Cite this