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 language | English |
|---|---|
| Article number | exag010 |
| Journal | Journal of Logic and Computation |
| Volume | 36 |
| Issue number | 3 |
| DOIs | |
| State | Published - 1 Apr 2026 |
| Externally published | Yes |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver