Zobrazeno 1 - 10
of 36
pro vyhledávání: '"Daviaud, Laure"'
Autor:
Daviaud, Laure, Johnson, Marianne
Since the seminal work by Angluin, active learning of automata, by membership and equivalence queries, has been extensively studied and several generalisations have been developed to learn various extensions of automata. For weighted automata, restri
Externí odkaz:
http://arxiv.org/abs/2309.07806
We show that the big-O problem for max-plus automata is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing functions f and g, there exists a constant c such that f < cg+ c. This
Externí odkaz:
http://arxiv.org/abs/2304.05229
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smallest Strahler number of the tree of any of its attractor decompositions.
Externí odkaz:
http://arxiv.org/abs/2003.08627
An improved translation from alternating parity automata on infinite words to alternating weak automata is given. The blow-up of the number of states is related to the size of the smallest universal ordered trees and hence it is quasi-polynomial, and
Externí odkaz:
http://arxiv.org/abs/1903.12620
Autor:
Czerwiński, Wojciech, Daviaud, Laure, Fijalkow, Nathanaël, Jurdziński, Marcin, Lazić, Ranko, Parys, Paweł
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and register games. We
Externí odkaz:
http://arxiv.org/abs/1807.10546
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 1 (February 11, 2020) lmcs:5059
We prove the undecidability of MSO on $\omega$-words extended with the second-order predicate $U_1(X)$ which says that the distance between consecutive positions in a set $X \subseteq \mathbb{N}$ is unbounded. This is achieved by showing that adding
Externí odkaz:
http://arxiv.org/abs/1807.08506
Autor:
Daviaud, Laure, Jurdziński, Marcin, Lazić, Ranko, Mazowiecki, Filip, Pérez, Guillermo A., Worrell, James
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean automata. It is well known that both problems are undecidable. In this p
Externí odkaz:
http://arxiv.org/abs/1804.09077
We define two classes of functions, called regular (respectively, first-order) list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of regular expressions
Externí odkaz:
http://arxiv.org/abs/1803.06168
In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zero-sum and hence the aim of the other player is to
Externí odkaz:
http://arxiv.org/abs/1803.04756
Weighted automata (WA) are an important formalism to describe quantitative properties. Obtaining equivalent deterministic machines is a longstanding research problem. In this paper we consider WA with a set semantics, meaning that the semantics is gi
Externí odkaz:
http://arxiv.org/abs/1701.04632