Zobrazeno 1 - 10
of 121
pro vyhledávání: '"COLCOMBET, THOMAS"'
We establish that the bisimulation invariant fragment of MSO over finite transition systems is expressively equivalent over finite transition systems to modal mu-calculus, a question that had remained open for several decades. The proof goes by trans
Externí odkaz:
http://arxiv.org/abs/2407.12677
Publikováno v:
TheoretiCS, Volume 3 (April 24, 2024) theoretics:11336
We study transformations of automata and games using Muller conditions into equivalent ones using parity or Rabin conditions. We present two transformations, one that turns a deterministic Muller automaton into an equivalent deterministic parity auto
Externí odkaz:
http://arxiv.org/abs/2305.04323
Publikováno v:
Logical Methods in Computer Science, Volume 20, Issue 1 (January 29, 2024) lmcs:10547
We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety objectives. More specifically, we show that the minimal number of memory states of a strategy ensuring a safety objective is given by the
Externí odkaz:
http://arxiv.org/abs/2212.12024
This paper introduces a robust class of functions from finite words to integers that we call Z-polyregular functions. We show that it admits natural characterizations in terms of logics, Z-rational expressions, Z-rational series and transducers. We t
Externí odkaz:
http://arxiv.org/abs/2207.07450
In this paper, we look at good-for-games Rabin automata that recognise a Muller language (a language that is entirely characterised by the set of letters that appear infinitely often in each word). We establish that minimal such automata are exactly
Externí odkaz:
http://arxiv.org/abs/2204.11333
We show that the existence of a first-order formula separating two monadic second order formulas over countable ordinal words is decidable. This extends the work of Henckell and Almeida on finite words, and of Place and Zeitoun on $\omega$-words. For
Externí odkaz:
http://arxiv.org/abs/2201.03089
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 3 (September 7, 2022) lmcs:7715
We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: showing an e
Externí odkaz:
http://arxiv.org/abs/2104.05262
In this paper, we are interested in automata over infinite words and infinite duration games, that we view as general transition systems. We study transformations of systems using a Muller condition into ones using a parity condition, extending Zielo
Externí odkaz:
http://arxiv.org/abs/2011.13041
In this paper, we present a categorical approach to learning automata over words, in the sense of the $L^*$-algorithm of Angluin. This yields a new generic $L^*$-like algorithm which can be instantiated for learning deterministic automata, automata w
Externí odkaz:
http://arxiv.org/abs/2010.13675
Publikováno v:
Fundamenta Informaticae, Volume 188, Issue 3 (April 18, 2023) fi:8485
In this work we prove decidability of the model-checking problem for safe recursion schemes against properties defined by alternating B-automata. We then exploit this result to show how to compute downward closures of languages of finite trees recogn
Externí odkaz:
http://arxiv.org/abs/2004.12187