A new order-theoretic characterisation of the polytime computable functions()

We propose a new order-theoretic characterisation of the class of polytime computable functions. To this avail we define the small polynomial path order ([Formula: see text] for short). This termination order entails a new syntactic method to analyse the innermost runtime complexity of term rewrite...

Descripción completa

Detalles Bibliográficos
Autores principales: Avanzini, Martin, Eguchi, Naohi, Moser, Georg
Formato: Online Artículo Texto
Lenguaje:English
Publicado: North-Holland Pub. Co 2015
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4567075/
https://www.ncbi.nlm.nih.gov/pubmed/26412933
http://dx.doi.org/10.1016/j.tcs.2015.03.003

Internet

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4567075/
https://www.ncbi.nlm.nih.gov/pubmed/26412933
http://dx.doi.org/10.1016/j.tcs.2015.03.003

Ejemplares similares