Search

Your search keyword '"Reachability problem"' showing total 1,499 results
Start Over Descriptor "Reachability problem"

Refine your results

more »

more »

more »
1,499 results on '"Reachability problem"'

3. SMPT: A Testbed for Reachability Methods in Generalized Petri Nets

Author

Amat, Nicolas, Zilio, Silvano Dal, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chechik, Marsha, editor, Katoen, Joost-Pieter, editor, and Leucker, Martin, editor

Published
2023
Full Text
View/download PDF

4. On the power of membrane dissolution in polarizationless P systems with active membranes.

Author

Gazdag, Zsolt and Hajagos, Károly

Subjects
*PROBLEM solving, *UNIFORMITY
Abstract

It is known that dissolution rules are necessary in polarizationless P systems with active membranes to solve problems beyond AC 0 using reasonable tight uniformity conditions (Murphy and Woods, Fundam Inf Series 134:129–152, 2014). On the other hand, no solutions of such problems exist using only dissolution rules. In this paper, we show that the NL -complete reachability problem can be solved in polynomial time by polarizationless P systems with active membranes using only dissolution rules under a suitable uniformity condition. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

5. Continuous One-counter Automata.

Author

BLONDIN, MICHAEL, LEYS, TIM, MAZOWIECKI, FILIP, OFFTERMATT, PHILIP, and PÉREZ, GUILLERMO

Subjects
POLYNOMIAL time algorithms
Abstract

We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper- and lower-bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down by a nonzero factor between zero and one. Our three main results are as follows: we prove (1) that the reachability problem for COCA with global upper- and lower-bound tests is in NC²; (2) that, in general, the problem is decidable in polynomial time; and (3) that it is NP-complete for COCA with parametric counter updates and bound tests. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

6. Intrinsic universality in automata networks III: On symmetry versus asynchrony.

Author

Ríos-Wilson, Martín and Theyssier, Guillaume

Subjects
*BOOLEAN networks, *COMPUTATIONAL complexity, *SYMMETRY, *FORECASTING
Abstract

An automata network is a finite assembly of interconnected entities endowed with a set of local maps defined over a common finite alphabet. These relationships are represented through an interaction graph. Together with the local functions, an assignment known as an update scheme directs the evolution of the network by updating specific subsets of entities at discrete time steps. Despite the scrutiny of interaction graphs and update schemes, their profound impact on automata network dynamics remains largely open. This work investigates the intricate interplay between these aspects, with a focus on how update schemes can counterbalance constraints stemming from symmetric local interactions. This paper is the third of a series about intrinsic universality, a notion that assesses both dynamical and computational complexity, encompassing transient behaviors, attractors, and prediction or reachability problems. We consider four update modes—parallel, block-sequential, local clocks, and general periodic— along with several families of symmetric signed conjunctive boolean networks defined by local constraints on signs. Our main result is to show a diagonal complexity leap in this two-dimensional landscape: the stronger the local constraints the higher the level of asynchrony required to obtain intrinsic universality or increase in complexity. We also show how in some cases asynchronism allows to simulate directed interactions from undirected ones with the same local rules. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

7. The Collatz Process Embeds a Base Conversion Algorithm

Author

Stérin, Tristan, Woods, Damien, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Schmitz, Sylvain, editor, and Potapov, Igor, editor

Published
2020
Full Text
View/download PDF

8. The Timestamp of Timed Automata

Author

Rosenmann, Amnon, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, André, Étienne, editor, and Stoelinga, Mariëlle, editor

Published
2019
Full Text
View/download PDF

9. Enhancing Workflow-Nets with Data for Trace Completion

Author

De Masellis, Riccardo, Di Francescomarino, Chiara, Ghidini, Chiara, Tessaris, Sergio, van der Aalst, Wil M. P., Series editor, Mylopoulos, John, Series editor, Rosemann, Michael, Series editor, Shaw, Michael J., Series editor, Szyperski, Clemens, Series editor, Teniente, Ernest, editor, and Weidlich, Matthias, editor

Published
2018
Full Text
View/download PDF

10. Approximating Any Logic Program by a CS-Program

Author

Boichut, Yohan, Pelletier, Vivien, Réty, Pierre, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, and Rusu, Vlad, editor

Published
2018
Full Text
View/download PDF

11. Perfect Timed Communication Is Hard

Author

Abdulla, Parosh Aziz, Atig, Mohamed Faouzi, Krishna, Shankara Narayanan, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Jansen, David N., editor, and Prabhakar, Pavithra, editor

Published
2018
Full Text
View/download PDF

12. Intrinsic universality in automata networks I: Families and simulations.

Author

Ríos-Wilson, Martín and Theyssier, Guillaume

Subjects
*STATISTICAL decision making, *CELLULAR automata, *FAMILIES, *COMPUTATIONAL complexity, *ORBITS (Astronomy)
Abstract

An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. We also compare our notions of universality to intrinsic universality of cellular automata. This paper is the first of a series of three: in the second one, we develop a proof technique to establish intrinsic universality based on an operation of glueing; in the third one we study the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

13. Petri Nets

Author

Gorrieri, Roberto, Henzinger, Monika, Series editor, Hromkovič, Juraj, Series editor, Nielsen, Mogens, Series editor, Rozenberg, Grzegorz, Series editor, Salomaa, Arto, Series editor, and Gorrieri, Roberto

Published
2017
Full Text
View/download PDF

14. Faster Algorithms for Weighted Recursive State Machines

Author

Chatterjee, Krishnendu, Kragl, Bernhard, Mishra, Samarth, Pavlogiannis, Andreas, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Yang, Hongseok, editor

Published
2017
Full Text
View/download PDF

15. ML and Extended Branching VASS

Author

Cotton-Barratt, Conrad, Murawski, Andrzej S., Ong, C. -H. Luke, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Yang, Hongseok, editor

Published
2017
Full Text
View/download PDF

16. Nested Timed Automata with Invariants

Author

Wang, Yuwei, Li, Guoqiang, Yuen, Shoji, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Larsen, Kim Guldstrand, editor, Sokolsky, Oleg, editor, and Wang, Ji, editor

Published
2017
Full Text
View/download PDF

17. Reachability Problem for Polynomial Iteration Is PSPACE-complete

Author

Niskanen, Reino, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Hague, Matthew, editor, and Potapov, Igor, editor

Published
2017
Full Text
View/download PDF

18. The Complexity of Diagnosability and Opacity Verification for Petri Nets

Author

Bérard, Béatrice, Haar, Stefan, Schmitz, Sylvain, Schwoon, Stefan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, van der Aalst, Wil, editor, and Best, Eike, editor

Published
2017
Full Text
View/download PDF

19. Model Checking Concurrency and Causality

Author

Wolf, Karsten, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, van der Aalst, Wil, editor, and Best, Eike, editor

Published
2017
Full Text
View/download PDF

20. On Termination and Boundedness of Nested Updatable Timed Automata

Author

Wang, Yuwei, Tao, Xiuting, Li, Guoqiang, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Liu, Shaoying, editor, Duan, Zhenhua, editor, Tian, Cong, editor, and Nagoya, Fumiko, editor

Published
2017
Full Text
View/download PDF

21. What Makes Petri Nets Harder to Verify: Stack or Data?

Author

Lazić, Ranko, Totzke, Patrick, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gibson-Robinson, Thomas, editor, Hopcroft, Philippa, editor, and Lazić, Ranko, editor

Published
2017
Full Text
View/download PDF

22. Continuous One-counter Automata

Author

Tim Leys, Michael Blondin, Filip Mazowiecki, Guillermo A. Pérez, and Philip Offtermatt

Subjects
Computer. Automation, Polynomial hierarchy, Discrete mathematics, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, General Computer Science, Reachability problem, Formal Languages and Automata Theory (cs.FL), Logic, Zero (complex analysis), Computer Science - Formal Languages and Automata Theory, Upper and lower bounds, Decidability, Automaton, Logic in Computer Science (cs.LO), Theoretical Computer Science, Computational Mathematics, Engineering sciences. Technology, Time complexity, Computer Science::Formal Languages and Automata Theory, Parametric statistics, Mathematics
Abstract

We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper- and lower-bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down by a nonzero factor between zero and one. Our three main results are as follows: we prove (1) that the reachability problem for COCA with global upper- and lower-bound tests is in NC 2 ; (2) that, in general, the problem is decidable in polynomial time; and (3) that it is NP-complete for COCA with parametric counter updates and bound tests.

Published
2023
Full Text
View/download PDF

23. Robot Arm Reconfiguration to Minimization Moving Parts

Author

A. Nourollah and N. Behzadpour

Subjects
formal modeling, robot arm, linkage reconfiguration, reachability problem, computational geometry, Computer engineering. Computer hardware, TK7885-7895, Science
Abstract

Background and Objectives: This paper presents a new optimization problem in the field of linkage reconfiguration. This is the problem of minimizing moving parts of a given robot arm for positioning the end effector of the given robot arm at the given target point as well as minimizing the movement of the movable parts. Methods: Initially, formal modeling is accomplished by minimizing the movement problem. At this time, a criterion called AM (Arithmetic Measure) is introduced, and this criterion is used to quantify the motion of the linkage. Afterward, it is indicated that the presented problem is an NP-Hard problem. Consequently, a greedy heuristic algorithm is presented to minimize the movement of the robot's moving components. After identifying the moving components and the movement of these parts, an algorithm is provided to determine the final configuration of the robot arm. Results: The results indicate that the discussed model successfully reduced the moving parts of the robot arm. Moreover, the results show that the proposed approach fulfills the goal of minimization of the linkage components. Furthermore, this method leads to erosion of arm, reduces energy consumption and the required parameters and variables for calculating the final configuration of the linkages. Conclusion: The mentioned algorithm solves the problem by mapping the robot arm with an arbitrary number of links to a robot with a single link or two links. The proposed heuristic approach requires O(n2) time using O(n) space.======================================================================================================Copyrights©2018 The author(s). This is an open access article distributed under the terms of the Creative Commons Attribution (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, as long as the original authors and source are cited. No permission is required from the authors or the publishers.======================================================================================================

Published
2018
Full Text
View/download PDF

26. Acceleration in Multi-PushDown Systems

Author

Atig, Mohamed Faouzi, Narayan Kumar, K., Saivasan, Prakash, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Chechik, Marsha, editor, and Raskin, Jean-François, editor

Published
2016
Full Text
View/download PDF

27. The Invariance Problem for Matrix Semigroups

Author

Dräger, Klaus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jacobs, Bart, editor, and Löding, Christof, editor

Published
2016
Full Text
View/download PDF

28. Reachability Problems for PAMs

Author

Kurganskyy, Oleksiy, Potapov, Igor, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Freivalds, Rūsiņš Mārtiņš, editor, Engels, Gregor, editor, and Catania, Barbara, editor

Published
2016
Full Text
View/download PDF

29. Occam’s Razor Applied to the Petri Net Coverability Problem

Author

Geffroy, Thomas, Leroux, Jérôme, Sutre, Grégoire, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Larsen, Kim Guldstrand, editor, Potapov, Igor, editor, and Srba, Jiří, editor

Published
2016
Full Text
View/download PDF

30. The Ideal Theory for WSTS

Author

Finkel, Alain, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Larsen, Kim Guldstrand, editor, Potapov, Igor, editor, and Srba, Jiří, editor

Published
2016
Full Text
View/download PDF

31. Reachability Problems for Continuous Chemical Reaction Networks

Author

Case, Adam, Lutz, Jack H., Stull, D. M., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Amos, Martyn, editor, and CONDON, ANNE, editor

Published
2016
Full Text
View/download PDF

32. Higher-Order Model Checking in Direct Style

Author

Terao, Taku, Tsukada, Takeshi, Kobayashi, Naoki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Igarashi, Atsushi, editor

Published
2016
Full Text
View/download PDF

33. Petri Nets and Semilinear Sets (Extended Abstract)

Author

Yen, Hsu-Chun, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Sampaio, Augusto, editor, and Wang, Farn, editor

Published
2016
Full Text
View/download PDF

34. New Lower Bounds for Reachability in Vector Addition Systems

Author

Wojciech Czerwiński and Ismaël Jecker and Sławomir Lasota and Jérôme Leroux and Łukasz Orlikowski, Czerwiński, Wojciech, Jecker, Ismaël, Lasota, Sławomir, Leroux, Jérôme, Orlikowski, Łukasz, Wojciech Czerwiński and Ismaël Jecker and Sławomir Lasota and Jérôme Leroux and Łukasz Orlikowski, Czerwiński, Wojciech, Jecker, Ismaël, Lasota, Sławomir, Leroux, Jérôme, and Orlikowski, Łukasz

Abstract

We investigate the dimension-parametric complexity of the reachability problem in vector addition systems with states (VASS) and its extension with pushdown stack (pushdown VASS). Up to now, the problem is known to be F_d-hard for VASS of dimension 3d+2 (the complexity class F_d corresponds to the kth level of the fast-growing hierarchy), and no essentially better bound is known for pushdown VASS. We provide a new construction that improves the lower bound for VASS: F_d-hardness in dimension 2d+3. Furthermore, building on our new insights we show a new lower bound for pushdown VASS: F_d-hardness in dimension d/2 + 6. This dimension-parametric lower bound is strictly stronger than the upper bound for VASS, which suggests that the (still unknown) complexity of the reachability problem in pushdown VASS is higher than in plain VASS (where it is Ackermann-complete).

Published
2023
Full Text
View/download PDF

35. Efficient Sink-Reachability Analysis via Graph Reduction

Author

Bernhard Scholz, Lijun Chang, Jens Dietrich, Long Qian, Catherine McCartin, and Lyndon M. Henry

Subjects
Power graph analysis, Theoretical computer science, Reachability problem, Computer science, Directed graph, Computer Science Applications, Reduction (complexity), Computational Theory and Mathematics, Reachability, Path (graph theory), Graph reduction, Time complexity, MathematicsofComputing_DISCRETEMATHEMATICS, Information Systems
Abstract

The reachability problem on directed graphs, asking whether two vertices are connected via a directed path, is an elementary problem that has been well-studied. In this paper, we study a variation of the elementary reachability problem, called the sink-reachability problem, which can be found in many applications such as static program analysis, social network analysis, large scale web graph analysis, XML document link path analysis, and the study of gene regulation relationships. To scale sink-reachablity analysis to large graphs, we develop a highly scalable sink-reachability preserving graph reduction strategy for input sink graphs, by using a composition framework. That is, individual sink-reachability preserving condensation operators, each running in linear time, are pipelined together to produce graph reduction algorithms that result in close to maximum reduction, while keeping the computation efficient. Experiments on large real-world sink graphs demonstrate the efficiency and effectiveness of our compositional approach to sink-reachability preserving graph reduction with a reduction rate of up to 99.74% for vertices and a rate of up to 99.46% for edges.

Published
2022
Full Text
View/download PDF

36. An Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Author

Chakraborty, Diptarka, Tewari, Raghunath, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Elbassioni, Khaled, editor, and Makino, Kazuhisa, editor

Published
2015
Full Text
View/download PDF

37. Verification of Concurrent Programs Using Trace Abstraction Refinement

Author

Cassez, Franck, Ziegler, Frowin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Davis, Martin, editor, Fehnker, Ansgar, editor, McIver, Annabelle, editor, and Voronkov, Andrei, editor

Published
2015
Full Text
View/download PDF

38. Synchronized Recursive Timed Automata

Author

Uezato, Yuya, Minamide, Yasuhiko, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Davis, Martin, editor, Fehnker, Ansgar, editor, McIver, Annabelle, editor, and Voronkov, Andrei, editor

Published
2015
Full Text
View/download PDF

39. On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension

Author

Leroux, Jérôme, Sutre, Grégoire, Totzke, Patrick, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Halldórsson, Magnús M., editor, Iwama, Kazuo, editor, Kobayashi, Naoki, editor, and Speckmann, Bettina, editor

Published
2015
Full Text
View/download PDF

40. Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes

Author

Etessami, Kousha, Stewart, Alistair, Yannakakis, Mihalis, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Halldórsson, Magnús M., editor, Iwama, Kazuo, editor, Kobayashi, Naoki, editor, and Speckmann, Bettina, editor

Published
2015
Full Text
View/download PDF

41. dReach: δ-Reachability Analysis for Hybrid Systems

Author

Kong, Soonho, Gao, Sicun, Chen, Wei, Clarke, Edmund, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Baier, Christel, editor, and Tinelli, Cesare, editor

Published
2015
Full Text
View/download PDF

42. Lazy TSO Reachability

Author

Bouajjani, Ahmed, Calin, Georgel, Derevenetc, Egor, Meyer, Roland, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Egyed, Alexander, editor, and Schaefer, Ina, editor

Published
2015
Full Text
View/download PDF

43. Analysis of Asynchronous Programs with Event-Based Synchronization

Author

Emmi, Michael, Ganty, Pierre, Majumdar, Rupak, Rosa-Velardo, Fernando, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Vitek, Jan, editor

Published
2015
Full Text
View/download PDF

44. The Best of Both Worlds: Trading Efficiency and Optimality in Fence Insertion for TSO

Author

Abdulla, Parosh Aziz, Atig, Mohamed Faouzi, Ngo, Tuan-Phong, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Vitek, Jan, editor

Published
2015
Full Text
View/download PDF

45. Discrete vs. Dense Times in the Analysis of Cyber-Physical Security Protocols

Author

Kanovich, Max, Kirigin, Tajana Ban, Nigam, Vivek, Scedrov, Andre, Talcott, Carolyn, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Focardi, Riccardo, editor, and Myers, Andrew, editor

Published
2015
Full Text
View/download PDF

46. Automated Verification of Stochastic Spiking Neural P Systems

Author

Aman, Bogdan, Ciobanu, Gabriel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, Sempere, José M., editor, and Zandron, Claudio, editor

Published
2015
Full Text
View/download PDF

47. Precise and Sound Automatic Fence Insertion Procedure under PSO

Author

Abdulla, Parosh Aziz, Atig, Mohamed Faouzi, Lång, Magnus, Ngo, Tuan Phong, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bouajjani, Ahmed, editor, and Fauconnier, Hugues, editor

Published
2015
Full Text
View/download PDF

48. Reachability in Succinct One-Counter Games

Author

Hunter, Paul, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bojanczyk, Mikolai, editor, Lasota, Slawomir, editor, and Potapov, Igor, editor

Published
2015
Full Text
View/download PDF

49. On Reachability-Related Games on Vector Addition Systems with States

Author

Jančar, Petr, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bojanczyk, Mikolai, editor, Lasota, Slawomir, editor, and Potapov, Igor, editor

Published
2015
Full Text
View/download PDF

50. Polynomial Interrupt Timed Automata

Author

Bérard, Béatrice, Haddad, Serge, Picaronny, Claudine, El Din, Mohab Safey, Sassolas, Mathieu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bojanczyk, Mikolai, editor, Lasota, Slawomir, editor, and Potapov, Igor, editor

Published
2015
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results