Cargando…
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...
| Autores principales: | , , |
|---|---|
| Formato: | Online Artículo Texto |
| Lenguaje: | English |
| Publicado: |
North-Holland Pub. Co
2015
|
| Materias: | |
| 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 |