Results 1 to 10 of about 24,416 (155)
Efficient guided symbolic reachability using reachability expressions [PDF]
International Journal on Software Tools for Technology Transfer, 2006 Asynchronous systems consist of a set of transitions which are non-deterministically chosen and executed. We present a theory of guiding symbolic reachability in such systems by scheduling clusters of transitions. A theory of reachability expressions which specify the schedules is presented. This theory allows proving equivalence of different schedules
Dina Thomas +2 more
openaire +4 more sources
2009 24th Annual IEEE Symposium on Logic In Computer Science, 2009 What is reachability in higher-order functional programs? We formulate reachability as a decision problem in the setting of the prototypical functional language PCF, and show that even in the recursion-free fragment generated from a finite base type, several versions of the reachability problem are undecidable from order 4 onwards, and several other ...
Ong, C, Tzevelekos, N, Soc, I
openaire +3 more sources
, 1998 We show that rigid reachability, the non-symmetric form of rigid E-unification, is undecidable already in the case of a single constraint. From this we infer the undecidability of a new rather restricted kind of second-order unification. We also show that certain decidable subclasses of the problem which are PTIME-complete in the equational case become
Ganzinger, Harald +2 more
openaire +6 more sources
Reducing Context-Bounded Concurrent Reachability to Sequential Reachability [PDF]
, 2009 We give a translation from concurrent programs to sequential programs that reduces the context-bounded reachability problem in the concurrent program to a reachability problem in the sequential one. The translation has two salient features: (a) the sequential program tracks, at any time, the local state of only one thread (though it does track multiple
SALVATORE LA TORRE +2 more
core +6 more sources
Competition-reachability of a graph [PDF]
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Suk Jai Seo, Peter J. Slater
openaire +2 more sources
Reachability Switching Games [PDF]
Logical Methods in Computer Science, 2021 We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case,
John Fearnley +3 more
openaire +8 more sources
Target control for hybrid systems with linear continuous dynamics [PDF]
, 2001 We consider the target control problem for hybrid systems with linear continuous dynamics. The system is modelled as a hybrid automaton. Control action is applied on the discrete level, while the continuous dynamics is subject to constant or set valued ...
Trontis, Anastasios +1 more
core +5 more sources
Minimal reachability problems [PDF]
2015 54th IEEE Conference on Decision and Control (CDC), 2015 Final version (with missing proofs) that appeared in CDC ...
Vasileios Tzoumas +2 more
openaire +3 more sources
On Completely Reachable Automata and Subset Reachability [PDF]
, 2018 This article focuses on subset reachability in synchronizing automata. First, we provide families of synchronizing automata with subsets which cannot be reached with short words. These families do not fulfil Don's Conjecture about subset reachability.
François Gonze, Raphaël M. Jungers
openaire +4 more sources
Journal of the ACM, 2015 Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges. This article confirms their conjecture that the reachability query is in DynFO. As a byproduct, it is shown that the rank of
Samir Datta +4 more
openaire +4 more sources