Implicit
发表于 2025-3-26 20:57:58
Hubschrauberrotoren und ihre Antriebe,ng CSPs are either in P or are NP-complete depending on the choice of allowed relations. We apply this result to two concrete examples (generalised linear programming and metric temporal reasoning) and obtain full complexity dichotomies in both cases.
dura-mater
发表于 2025-3-27 03:56:33
https://doi.org/10.1007/978-3-642-92601-3umber of beta steps to normal form is polynomially related to the actual cost (that is, as performed on a Turing machine) of normalization, under weak call-by-value reduction. Orthogonal constructor term rewrite systems and lambda-calculus are thus both polynomially related to Turing machines, taking as notion of cost their natural parameters.
recession
发表于 2025-3-27 05:50:43
https://doi.org/10.1007/978-3-658-12759-6 that the resource usage verification for functional programs can be reduced to the model checking of recursion schemes. As an application, we show that the resource usage verification problem is (. − 1)-EXPTIME complete.
lactic
发表于 2025-3-27 10:10:27
When Are Timed Automata Determinizable?ons, we get for those classes the decidability of the universality and of the inclusion problems, and compute their complexities (the inclusion problem is for instance EXPSPACE-complete for strongly non-Zeno timed automata).
Corporeal
发表于 2025-3-27 16:20:03
http://reply.papertrans.cn/17/1663/166202/166202_35.png
MOAT
发表于 2025-3-27 20:08:47
On Constructor Rewrite Systems and the Lambda-Calculusumber of beta steps to normal form is polynomially related to the actual cost (that is, as performed on a Turing machine) of normalization, under weak call-by-value reduction. Orthogonal constructor term rewrite systems and lambda-calculus are thus both polynomially related to Turing machines, taking as notion of cost their natural parameters.
浮雕
发表于 2025-3-27 22:16:33
Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus that the resource usage verification for functional programs can be reduced to the model checking of recursion schemes. As an application, we show that the resource usage verification problem is (. − 1)-EXPTIME complete.
我要沮丧
发表于 2025-3-28 04:16:38
http://reply.papertrans.cn/17/1663/166202/166202_38.png
idiopathic
发表于 2025-3-28 07:36:50
Stirnräder, Gestaltung und Berechnungmial time. In this paper, larger classes of tractable instances are singled out, by discussing solution approaches based on exploiting hypergraph acyclicity and, more generally, structural decomposition methods, such as (hyper)tree decompositions.
藕床生厌倦
发表于 2025-3-28 12:59:14
Hubschrauberrotoren und ihre Antriebe,nd player does. We show that the problem is undecidable in general, but that it becomes decidable if we restrict to single-clock 1.-player games and ask whether the player can ensure that the probability of reaching the set is =1 (or >0, =0).