Zobrazeno 1 - 10
of 20
pro vyhledávání: '"Theory of computation → Parallel computing models"'
Autor:
Finkel, Alain, Praveen, M.
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 4 (October 14, 2020) lmcs:5999
The decidability and complexity of reachability problems and model-checking for flat counter machines have been explored in detail. However, only few results are known for flat (lossy) FIFO machines, only in some particular cases (a single loop or a
Externí odkaz:
http://arxiv.org/abs/1908.07282
Autor:
Alain Finkel, M. Praveen
Publikováno v:
Logical Methods in Computer Science, Vol Volume 16, Issue 4 (2020)
The decidability and complexity of reachability problems and model-checking for flat counter machines have been explored in detail. However, only few results are known for flat (lossy) FIFO machines, only in some particular cases (a single loop or a
Externí odkaz:
https://doaj.org/article/2f04ec861fbf489a9fa1d88014193e29
Publikováno v:
Darya Melnyk
In this paper, we study the notion of mending: given a partial solution to a graph problem, how much effort is needed to take one step towards a proper solution? For example, if we have a partial coloring of a graph, how hard is it to properly color
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::897e331d123bfbfa03dc52f8cbcc7188
SAT/SMT-solvers and model checkers automate formal verification of sequential programs. Formal reasoning about scalable concurrent programs is still manual and requires expert knowledge. But scalability is a fundamental requirement of current and fut
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b19ba06c51c61c74de35762271f45c3b
SAT/SMT-solvers and model checkers automate formal verification of sequential programs. Formal reasoning about scalable concurrent programs is still manual and requires expert knowledge. But scalability is a fundamental requirement of current and fut
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a889a9c3cc1e1ce4ea9e08f13a662056
Nowadays, parallel applications are used every day in high performance computing, scientific computing and also in everyday tasks due to the pervasiveness of multi-core architectures. However, several implementation challenges have so far stifled the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9eafded1e24ac0c7a85422a3ae759d9e
https://zenodo.org/record/6628877
https://zenodo.org/record/6628877
In the maximum satisfiability problem (max-sat) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as possible. We study the parallel parameterized complexity of various versi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0d69c4e0aade091697942653facb3e67
http://arxiv.org/abs/2206.01280
http://arxiv.org/abs/2206.01280
Autor:
Czerwiński, Wojciech, Hofman, Piotr
Publikováno v:
33rd International Conference on Concurrency Theory, CONCUR 2022
We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASSes) with the acceptance condition defined by the set of accepting states (and more generally by some upward-closed conditions). In ge
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6f233c91d96d31476f7c2c1ce563db9a
https://doi.org/10.4230/lipics.concur.2022.16
https://doi.org/10.4230/lipics.concur.2022.16
Autor:
Blikstad, Joakim
Despite a lot of recent progress in obtaining faster sequential matroid intersection algorithms, the fastest parallel poly(n)-query algorithm was still the straightforward O(n)-round parallel implementation of Edmonds' augmenting paths algorithm from
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4bbb4969a9c5d5999d69f8eb7ad4ed61
Autor:
Czerwiński, Wojciech
We briefly describe recent advances on understanding the complexity of the reachability problem for vector addition systems (or equivalently for vector addition systems with states - VASSes). We present a zoo of a few involved VASS examples, which il
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b63fc0cc8a579173cf9e3ab5b42f9856