22 citations · 108 across the 38 of their papers we have counts for
6 papers · 1 filter
Agafonov's Theorem for finite and infinite alphabets and probability distributions different from equidistribution
Thomas Seiller, Jakob Grue Simonsen
An infinite sequence over an alphabet is -distributed w.r.t. a probability map if, for every finite string , the limiting frequency of in exists and equal…
Stellar Resolution: Multiplicatives
Boris Eng, Thomas Seiller
We present a new asynchronous model of computation named Stellar Resolution based on first-order unification. This model of computation is obtained as a formalisation of Girard's t…
Agafonov's Proof of Agafonov's Theorem: A Modern Account and New Insights
Thomas Seiller, Jakob Simonsen
We give a modern account of Agafonov's original proof of his eponymous theorem. The original proof was only reported in Russian in a journal not widely available, and the work most…
Lower bounds for algebraic machines, semantically
Luc Pellissier, Thomas Seiller
This paper presents a new semantic method for proving lower bounds in computational complexity. We use it to prove that maxflow, a PTIME complete problem, is not computable in poly…
Probabilistic Complexity Classes through Semantics
Thomas Seiller
In a recent paper, the author has shown how Interaction Graphs models for linear logic can be used to obtain implicit characterisations of non-deterministic complexity classes. In…
Zeta Functions and the (Linear) Logic of Markov Processes
Thomas Seiller
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…