Functions definable by arithmetic circuits

Ian Pratt-Hartmann, Ivo Düntsch

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


    An arithmetic circuit is a labelled, directed, acyclic graph specifying a cascade of arithmetic and logical operations to be performed on sets of non-negative integers. In this paper, we consider the definability of functions from tuples of sets of non-negative integers to sets of non-negative integers by means of arithmetic circuits. We prove two negative results: the first shows, roughly, that a function is not circuit-definable if it has an infinite range and sub-linear growth; the second shows, roughly, that a function is not circuit-definable if it has a finite range and fails to converge on certain 'sparse' chains under inclusion. We observe that various functions of interest fall under these descriptions. © 2009 Springer Berlin Heidelberg.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.
    Place of PublicationBerlin
    PublisherSpringer Nature
    Number of pages9
    ISBN (Print)3642030726, 9783642030727
    Publication statusPublished - 2009
    Event5th Conference on Computability in Europe, CiE 2009 - Heidelberg
    Duration: 1 Jul 2009 → …

    Publication series

    NameLecture notes in computer science


    Conference5th Conference on Computability in Europe, CiE 2009
    Period1/07/09 → …


    • Arithmetic circuit
    • Complex algebra
    • Expressive power
    • Integer expression


    Dive into the research topics of 'Functions definable by arithmetic circuits'. Together they form a unique fingerprint.

    Cite this