@inproceedings{1bf27368635c4f2ca0809b7e68ced363,

title = "Functions definable by arithmetic circuits",

abstract = "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. {\textcopyright} 2009 Springer Berlin Heidelberg.",

keywords = "Arithmetic circuit, Complex algebra, Expressive power, Integer expression",

author = "Ian Pratt-Hartmann and Ivo D{\"u}ntsch",

year = "2009",

doi = "10.1007/978-3-642-03073-4_42",

language = "English",

isbn = "3642030726",

volume = "5635",

series = "Lecture notes in computer science",

publisher = "Springer Nature",

pages = "409--418",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.",

address = "United States",

note = "5th Conference on Computability in Europe, CiE 2009 ; Conference date: 01-07-2009",

}