Recursion Schemata for NCk

Guillaume Bonfante; Reinhard Kahle; Jean-Yves Marion; Isabel Oitavem

hal-00342366, version 1

Recursion Schemata for NCk

Guillaume Bonfante () ¹, Reinhard Kahle () ², Jean-Yves Marion () ¹, Isabel Oitavem () ²

22nd International Workshop, CSL 2008, 17th Annual Conference of the EACSL, Bertinoro, Italy, September 16-19, 2008. Proceedings 5213 (2008) 49-63

Résumé : We give a recursion-theoretic characterization of the complexity classes NC k for k ≥ 1. In the spirit of implicit computational complexity, it uses no explicit bounds in the recursion and also no separation of variables is needed. It is based on three recursion schemes, one corresponds to time (time iteration), one to space allocation (explicit structural recursion) and one to internal computations (mutual in place recursion). This is, to our knowledge, the first exact characterization of NC k by function algebra over infinite domains in implicit complexity.

1 : CARTE (INRIA Nancy - Grand Est / LORIA)
CNRS : UMR7503 – INRIA – Université de Lorraine
2 : Departamento de Informática
Universidade Nova de Lisboa

hal-00342366, version 1
http://hal.archives-ouvertes.fr/hal-00342366
oai:hal.archives-ouvertes.fr:hal-00342366
Contributeur : Jean-Yves Marion <>
Soumis le : Jeudi 27 Novembre 2008, 15:00:00
Dernière modification le : Lundi 1 Décembre 2008, 11:46:46

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1007/978-3-540-87531-4_6

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="hal-00342366"><analytic>
<author><persName><forename>Guillaume</forename><surname>Bonfante</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA</orgName>
<orgName type="team">CARTE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Reinhard</forename><surname>Kahle</surname></persName>
<affiliation>
<orgName type="team">Departamento de Informática</orgName>
<country>FR</country>
<orgName type="institution">Universidade Nova de Lisboa</orgName>
</affiliation>
</author>
<author><persName><forename>Jean-Yves</forename><surname>Marion</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA</orgName>
<orgName type="team">CARTE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Isabel</forename><surname>Oitavem</surname></persName>
<affiliation>
<orgName type="team">Departamento de Informática</orgName>
<country>FR</country>
<orgName type="institution">Universidade Nova de Lisboa</orgName>
</affiliation>
</author>
<title type="main" level="a">Recursion Schemata for NCk</title></analytic><monogr><title level="m" type="main">Computer Science Logic</title><meeting>22nd International Workshop, CSL 2008, 17th Annual Conference of the EACSL, Bertinoro, Italy, September 16-19, 2008. Proceedings</meeting><imprint><publisher>Springer</publisher><pubPlace><settlement>Bertinoro</settlement><country>Italie</country></pubPlace><biblScope type="publicationDate">2008-00-00</biblScope><biblScope type="vol">5213</biblScope><biblScope type="pp">49-63</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-540-87531-4_6</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00342366</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00342366/PDF/CSL08BKMO.pdf</idno></biblStruct>
</listBibl>
</listBibl>