output
20062021
most citedModel-checking ATL under Imperfect Information and Perfect Recall Semantics is Undecidable

77 citations

researchers with a paper here
collaborating institutions
Showing cs.CCShow all

5 papers · 1 filter

cs.CC2020

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…

cs.CC2018★ 2 cited

Unifying lower bounds for algebraic machines, semantically

Thomas Seiller, Luc Pellissier, Ulysse Léchine

This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it…

cs.CC2018

Undecidable word problem in subshift automorphism groups

Pierre Guillon, Emmanuel Jeandel, Jarkko Kari +1

This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing degree, there exists a subshift whose aut…

cs.CC2016★ 1 cited

On entropic convergence of algorithms in terms of domain partitions

Anatol Slissenko

The paper describes an approach to measuring convergence of an algorithm to its result in terms of an entropy-like function of partitions of its inputs of a given length. The goal…

cs.CC2009★ 2 cited

New Choice for Small Universal Devices: Symport/Antiport P Systems

Sergey Verlan, Yurii Rogozhin

Symport/antiport P systems provide a very simple machinery inspired by corresponding operations in the living cell. It turns out that systems of small descriptional complexity are…