A predicative and decidable characterization of the polynomial classes of languages

DOI10.1016/S0304-3975(99)00116-4zbMath0952.68062MaRDI QIDQ1589422

Salvatore Caporaso, Nicola Galesi, Michele Zito

Publication date: 12 December 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityfunctional programmingLisppredicative recursion

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

A decidable characterization of the classes between lintime and exptime

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• Beweistheoretische Untersuchung der verzweigten Analysis
• Undecidability vs transfinite induction for the consistency of hyperarithmetical sets
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• SAFE TURING MACHINES, GRZEGORCZYK CLASSES AND POLYTIME
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A predicative and decidable characterization of the polynomial classes of languages