Zobrazeno 1 - 10
of 52
pro vyhledávání: '"Parys, Pawel"'
Autor:
Parys, Paweł, Wiącek, Aleksander
We improve the complexity of solving parity games (with priorities in vertices) for $d={\omega}(\log n)$ by a factor of ${\theta}(d^2)$: the best complexity known to date was $O(mdn^{1.45+\log_2(d/\log_2(n))})$, while we obtain $O(mn^{1.45+\log_2(d/\
Externí odkaz:
http://arxiv.org/abs/2305.00308
The Rabin tree theorem yields an algorithm to solve the satisfiability problem for monadic second-order logic over infinite trees. Here we solve the probabilistic variant of this problem. Namely, we show how to compute the probability that a randomly
Externí odkaz:
http://arxiv.org/abs/2304.12158
Decidability of the problems of unboundedness and simultaneous unboundedness (aka. the diagonal problem) for higher-order recursion schemes was established by Clemente, Parys, Salvati, and Walukiewicz (2016). Then a procedure of optimal complexity wa
Externí odkaz:
http://arxiv.org/abs/2204.11023
Autor:
Parys, Paweł
We show a new simple algorithm that solves the model-checking problem for recursion schemes: check whether the tree generated by a given higher-order recursion scheme is accepted by a given alternating parity automaton. The algorithm amounts to a pro
Externí odkaz:
http://arxiv.org/abs/2105.01861
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 1 (January 12, 2022) lmcs:7387
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial compl
Externí odkaz:
http://arxiv.org/abs/2104.09717
Autor:
Parys, Paweł
We show a new simple algorithm that checks whether a given higher-order grammar generates a nonempty language of trees. The algorithm amounts to a procedure that transforms a grammar of order n to a grammar of order n-1, preserving nonemptiness, and
Externí odkaz:
http://arxiv.org/abs/2009.08174
Autor:
Parys, Paweł
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 3 (August 20, 2020) lmcs:6692
We show that deterministic collapsible pushdown automata of second order can recognize a language that is not recognizable by any deterministic higher-order pushdown automaton (without collapse) of any order. This implies that there exists a tree gen
Externí odkaz:
http://arxiv.org/abs/2008.00650
Autor:
Göller, Stefan, Parys, Paweł
We show that in case a pushdown system is bisimulation equivalent to a finite system, there is already a bisimulation equivalent finite system whose size is elementarily bounded in the description size of the pushdown system. As a consequence we obta
Externí odkaz:
http://arxiv.org/abs/2005.06285
Autor:
Parys, Paweł
We prove that the MSO+U logic is compositional in the following sense: whether an MSO+U formula holds in a tree T depends only on MSO+U-definable properties of the root of T and of subtrees of T starting directly below the root. Another kind of compo
Externí odkaz:
http://arxiv.org/abs/2005.02384
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