Timed Sets, Functional Complexity, and Computability
| Autor: | Pavel Hrubeš, Robin Cockett, JoaquíN DíAz-BoïLs, Jonathan Gallagher |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
complexity measures computability Theoretical computer science General Computer Science Basis (linear algebra) Restriction categories Computability Modulo Turing categories functional complexity Theoretical Computer Science Distributive property Mathematics::Category Theory Complexity class Categorical variable Turing computer Mathematics computer.programming_language Computer Science(all) |
| Zdroj: | MFPS |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/j.entcs.2012.08.009 |
| Popis: | The construction of various categories of “timed sets” is described in which the timing of maps is considered modulo a “complexity order”. The properties of these categories are developed: under appropriate conditions they form discrete, distributive restriction categories with an iteration. They provide a categorical basis for modeling functional complexity classes and allow the development of computability within these settings. Indeed, by considering “program objects” and the functions they compute, one can obtain models of computability – i.e. Turing categories – in which the total maps belong to specific complexity classes. Two examples of this are introduced in some detail which respectively have their total maps corresponding to PTIME and LOGSPACE. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect