Zobrazeno 1 - 10
of 15
pro vyhledávání: '"Thejaswini, K. S."'
We provide an algorithm to solve Rabin and Streett games over graphs with $n$ vertices, $m$ edges, and $k$ colours that runs in $\tilde{O}\left(mn(k!)^{1+o(1)} \right)$ time and $O(nk\log k \log n)$ space, where $\tilde{O}$ hides poly-logarithmic fac
Externí odkaz:
http://arxiv.org/abs/2401.07548
Autor:
Casares, Antonio, Pilipczuk, Marcin, Pilipczuk, Michał, Souza, Uéverton S., Thejaswini, K. S.
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o(k \log k)} \cdot n^{O(1)}$, where $k$ is the number of pairs of vertex subsets involved in the winning con
Externí odkaz:
http://arxiv.org/abs/2310.20433
This paper considers the problem of solving infinite two-player games over finite graphs under various classes of progress assumptions motivated by applications in cyber-physical system (CPS) design. Formally, we consider a game graph G, a temporal s
Externí odkaz:
http://arxiv.org/abs/2310.12767
Autor:
Prakash, Aditya, Thejaswini, K. S.
We consider the model of history-deterministic one-counter nets (OCNs). History-determinism is a property of transition systems that allows for a limited kind of non-determinism which can be resolved 'on-the-fly'. Token games, which have been used to
Externí odkaz:
http://arxiv.org/abs/2210.10084
We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown automaton, but can observe the contents of the stack. The observer would th
Externí odkaz:
http://arxiv.org/abs/2102.06897
Progress-measure lifting algorithms for solving parity games have the best worst-case asymptotic runtime, but are limited by their asymmetric nature, and known from the work of Czerwi\'nski et al. (2018) to be subject to a matching quasi-polynomial l
Externí odkaz:
http://arxiv.org/abs/2010.08288
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 attractor decomposition meta-algorithm for solving parity games is given that generalises the classic McNaughton-Zielonka algorithm and its recent quasi-polynomial variants due to Parys (2019), and to Lehtinen, Schewe, and Wojtczak (2019). The cen
Externí odkaz:
http://arxiv.org/abs/2001.04333
The classic McNaughton-Zielonka algorithm for solving parity games has excellent performance in practice, but its worst-case asymptotic complexity is worse than that of the state-of-the-art algorithms. This work pinpoints the mechanism that is respon
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3d419bd677f7af0526201a5b89d7045b
Progress-measure lifting algorithms for solving parity games have the best worst-case asymptotic runtime, but are limited by their asymmetric nature, and known from the work of Czerwi\'nski et al. (2018) to be subject to a matching quasi-polynomial l
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::24b8ee41b21c7097fa11021122df1f10
http://arxiv.org/abs/2010.08288
http://arxiv.org/abs/2010.08288