@inproceedings{e9570f64466e472ba0e14135a28374d4,
title = "A recursion-theoretic characterisation of the positive polynomial-time functions",
abstract = "We extend work of Lautemann, Schwentick and Stewart [14] on characterisations of the {"}positive{"} polynomial-time predicates (posP, also called mP by Grigni and Sipser [11]) to function classes. Our main result is the obtention of a function algebra for the positive polynomial-time functions (posFP) by imposing a simple uniformity constraint on the bounded recursion operator in Cobham's characterisation of FP. We show that a similar constraint on a function algebra based on safe recursion, in the style of Bellantoni and Cook [3], yields an {"}implicit{"} characterisation of posFP, mentioning neither explicit bounds nor explicit monotonicity constraints.",
keywords = "Function algebras, Function classes, Implicit complexity, Logic, Monotone complexity, Positive complexity, Recursion-theoretic characterisations",
author = "Anupam Das and Isabel Oitavem",
year = "2018",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.CSL.2018.18",
language = "English",
isbn = "9783959770880",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl",
editor = "Ghica, {Dan R.} and Achim Jung",
booktitle = "27th EASCL Annual Conference on Computer Science Logic 2018 (CSL 2018)",
address = "Germany",
note = "27th Annual EACSL Conference Computer Science Logic, CSL 2018 ; Conference date: 04-09-2018 Through 07-09-2018",
}