Timed Sets, Functional Complexity, and Computability

DOI10.1016/J.ENTCS.2012.08.009MaRDI QIDQ3178279zbMATH OpenOpenAlexWikidataFDO

Authors Joaquín Díaz-Boïls, Jonathan Gallagher, J. R. B. Cockett, Pavel Hrubeš

Publication date 8 July 2016

Published in Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.entcs.2012.08.009

zbMATH Keywords

complexity measurescomputabilityfunctional complexityrestriction categoriesTuring categories

Mathematics Subject Classification ID

Special categories (18B99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 17551
• scientific article; zbMATH DE number 7156375
• scientific article; zbMATH DE number 4130363
• On genuinely time bounded computations
• The complexity types of computable sets
• Complexity and algorithms for reasoning about time
• TIME BOUNDED COMPUTATIONS OVER THE REALS
• scientific article; zbMATH DE number 1361127
• Undecidability results for low complexity time classes

Cites work

• A categorical setting for lower complexity
• Boolean and classical restriction categories
• Categories of partial maps
• Computational Complexity
• Dominical categories: recursion theory without elements
• Introduction to Turing categories
• On traced monoidal closed categories
• Restriction categories III: colimits, partial limits and extensivity
• Restriction categories. I: Categories of partial maps
• Traced monoidal categories

Cited in

(12)

• Implicit characterizations of FPTIME and NC revisited
• Complexity bounds for container functors and comonads
• Monoidal computer. III: A coalgebraic view of computability and complexity (extended abstract)
• Restriction categories as enriched categories
• Total maps of Turing categories
• Categorical complexity
• scientific article; zbMATH DE number 5622695 (Why is no real title available?)
• scientific article; zbMATH DE number 17551 (Why is no real title available?)
• An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras
• Quotienting the delay monad by weak bisimilarity
• Categorical semantics of a simple differential programming language
• scientific article; zbMATH DE number 7156375 (Why is no real title available?)

This page was built for publication: Timed Sets, Functional Complexity, and Computability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3178279)