Timed Sets, Functional Complexity, and Computability

DOI10.1016/j.entcs.2012.08.009zbMath1342.68127OpenAlexW2059295095WikidataQ113318084 ScholiaQ113318084MaRDI QIDQ3178279

Joaquín Díaz-Boïls, Jonathan Gallagher, J. Robin 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

computabilitycomplexity measuresTuring categoriesfunctional complexityrestriction categories

Mathematics Subject Classification ID

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

Related Items

Total maps of Turing categories, Complexity bounds for container functors and comonads, Quotienting the delay monad by weak bisimilarity, Categorical semantics of a simple differential programming language, Restriction categories as enriched categories, Monoidal computer III: a coalgebraic view of computability and complexity (extended abstract)

Cites Work

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