Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time Export

@incollection{citeulike:1527960, abstract = {We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time computable functions over any arbitrary structure can be characterized in term of safe recursive functions. We show that polynomial parallel time decision problems over any arbitrary structure can be characterized in terms of safe recursive functions with substitutions.}, author = {Bournez, Olivier and Cucker, Felipe and Naurois, Paulin J. and Marion, Jean-Yves}, citeulike-article-id = {1527960}, citeulike-linkout-0 = {http://www.springerlink.com/content/6pjgp33yhqrapruv}, citeulike-linkout-1 = {http://www.loria.fr/~bournez/publications.html}, journal = {Foundations of Software Science and Computational Structures: 6th International Conference, FOSSACS 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003, Warsaw, Poland, April 7-11, 2003. Proceedings}, keywords = {complexity, logic, model\_theory}, pages = {185--199}, posted-at = {2007-08-01 16:44:09}, priority = {2}, title = {Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time}, url = {http://www.springerlink.com/content/6pjgp33yhqrapruv}, year = {2003} }

TY - CHAP ID - citeulike:1527960 L3 - citeulike-article-id:1527960 N2 - We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time computable functions over any arbitrary structure can be characterized in term of safe recursive functions. We show that polynomial parallel time decision problems over any arbitrary structure can be characterized in terms of safe recursive functions with substitutions. JF - Foundations of Software Science and Computational Structures: 6th International Conference, FOSSACS 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003, Warsaw, Poland, April 7-11, 2003. Proceedings EP - 199 TI - Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time SP - 185 KW - complexity KW - logic KW - model_theory AU - Bournez, Olivier AU - Cucker, Felipe AU - Naurois, Paulin AU - Marion, Jean-Yves PY - 2003/// UR - http://www.springerlink.com/content/6pjgp33yhqrapruv ER -