Zeta Functions and the (Linear) Logic of Markov Processes
| Autor: | Seiller, Thomas |
|---|---|
| Přispěvatelé: | Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, ANR-22-CE48-0003,DySCo,Systèmes Dynamiques et Calcul: une approche logique(2022), European Project: 659920,H2020,H2020-MSCA-IF-2014,ReACT(2015) |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science Probability (math.PR) [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Mathematics - Logic Dynamical Systems (math.DS) ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.2: Semantics of Programming Languages/F.3.2.2: Operational semantics Logic in Computer Science (cs.LO) ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.2: Modes of Computation/F.1.2.4: Probabilistic computation [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS [MATH.MATH-LO]Mathematics [math]/Logic [math.LO] FOS: Mathematics Mathematics - Dynamical Systems Logic (math.LO) ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.2: Semantics of Programming Languages/F.3.2.1: Denotational semantics Mathematics - Probability |
| Popis: | The author introduced models of linear logic known as ''Interaction Graphs'' which generalise Girard's various geometry of interaction constructions. In this work, we establish how these models essentially rely on a deep connection between zeta functions and the execution of programs, expressed as a cocycle. This is first shown in the simple case of graphs, before begin lifted to dynamical systems. Focussing on probabilistic models, we then explain how the notion of graphings used in Interaction Graphs captures a natural class of sub-Markov processes. We then extend the realisability constructions and the notion of zeta function to provide a realisability model of second-order linear logic over the set of all (discrete-time) sub-Markov processes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|