Log in

Relevant bibliographies by topics / Reachability Analysi

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'Reachability Analysi'

Author: Grafiati

Published: 11 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Reachability Analysi.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Reachability Analysi"

1

Gu, Shen Shen. "Scheduling Flexible Manufacturing Systems with Petri Nets Based on the Cell Enumeration Method." Advanced Materials Research 346 (September 2011): 412–18. http://dx.doi.org/10.4028/www.scientific.net/amr.346.412.

Full text

Abstract:

In the field of modern manufacturing, flexible manufacturing systems (FMS) is very important because it can scheduleand optimize multipurpose machines to produce multiple types of products. When applying the FMS technology, Petri Net is used to model the machines, parts and the whole manufacturing progress. The core concern of FMS is to make sure that the manufacturing system can transfer from the original state to the final state, which is called reachabilty. Therefore, reachability analysis is one of the most important problems of FMS. When Petri Net is acyclic, the reachability analysis can be performed by finding a integer solution to a set of linear equation, named fundamental equation, which is known to be NP-complete. In this paper, a novel approach for finding the integer solution is applied by adopting a revised version of the cell enumeration method for an arrangement of hyperplanes in discrete geometry to identify firing count vector solution(s) to the fundamental equation on a bounded integer set with a complexity bound of O((nu)n¡m),where n is the number of nodes, m is the number of arcs and u is the upper bound of the number of firings for all individual arcs.

APA, Harvard, Vancouver, ISO, and other styles

2

Peng, Wuxu, and Kia Makki. "Reachability and reverse reachability analysis of CFSMs." Computer Communications 19, no. 8 (July 1996): 668–74. http://dx.doi.org/10.1016/s0140-3664(97)84932-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Fardigola, Larissa, and Kateryna Khalina. "Reachability and Controllability Problems for the Heat Equation on a Half-Axis." Zurnal matematiceskoj fiziki, analiza, geometrii 15, no. 1 (March 25, 2019): 57–78. http://dx.doi.org/10.15407/mag15.01.057.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Li, Yuanbo, Kris Satya, and Qirun Zhang. "Efficient algorithms for dynamic bidirected Dyck-reachability." Proceedings of the ACM on Programming Languages 6, POPL (January 16, 2022): 1–29. http://dx.doi.org/10.1145/3498724.

Full text

Abstract:

Dyck-reachability is a fundamental formulation for program analysis, which has been widely used to capture properly-matched-parenthesis program properties such as function calls/returns and field writes/reads. Bidirected Dyck-reachability is a relaxation of Dyck-reachability on bidirected graphs where each edge u → ( i v labeled by an open parenthesis “( i ” is accompanied with an inverse edge v → ) i u labeled by the corresponding close parenthesis “) i ”, and vice versa. In practice, many client analyses such as alias analysis adopt the bidirected Dyck-reachability formulation. Bidirected Dyck-reachability admits an optimal reachability algorithm. Specifically, given a graph with n nodes and m edges, the optimal bidirected Dyck-reachability algorithm computes all-pairs reachability information in O ( m ) time. This paper focuses on the dynamic version of bidirected Dyck-reachability. In particular, we consider the problem of maintaining all-pairs Dyck-reachability information in bidirected graphs under a sequence of edge insertions and deletions. Dynamic bidirected Dyck-reachability can formulate many program analysis problems in the presence of code changes. Unfortunately, solving dynamic graph reachability problems is challenging. For example, even for maintaining transitive closure, the fastest deterministic dynamic algorithm requires O ( n 2 ) update time to achieve O (1) query time. All-pairs Dyck-reachability is a generalization of transitive closure. Despite extensive research on incremental computation, there is no algorithmic development on dynamic graph algorithms for program analysis with worst-case guarantees. Our work fills the gap and proposes the first dynamic algorithm for Dyck reachability on bidirected graphs. Our dynamic algorithms can handle each graph update ( i.e. , edge insertion and deletion) in O ( n ·α( n )) time and support any all-pairs reachability query in O (1) time, where α( n ) is the inverse Ackermann function. We have implemented and evaluated our dynamic algorithm on an alias analysis and a context-sensitive data-dependence analysis for Java. We compare our dynamic algorithms against a straightforward approach based on the O ( m )-time optimal bidirected Dyck-reachability algorithm and a recent incremental Datalog solver. Experimental results show that our algorithm achieves orders of magnitude speedup over both approaches.

APA, Harvard, Vancouver, ISO, and other styles

5

Zavattaro, Gianluigi. "Reachability Analysis in BioAmbients." Electronic Notes in Theoretical Computer Science 227 (January 2009): 179–93. http://dx.doi.org/10.1016/j.entcs.2008.12.111.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Szlobodnyik, Gergely, and Gábor Szederkényi. "Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws." Complexity 2019 (March 26, 2019): 1–13. http://dx.doi.org/10.1155/2019/1035974.

Full text

Abstract:

In this paper we study the reachability problem of sub- and superconservative discrete state chemical reaction networks (d-CRNs). It is known that a subconservative network has bounded reachable state space, while that of a superconservative one is unbounded. The reachability problem of superconservative reaction networks is traced back to the reachability of subconservative ones. We consider network structures composed of reactions having at most one input and one output species beyond the possible catalyzers. We give a proof that, assuming all the reactions are charged in the initial and target states, the reachability problems of sub- and superconservative reaction networks are equivalent to the existence of nonnegative integer solution of the corresponding d-CRN state equations. Using this result, the reachability problem is reformulated as an Integer Linear Programming (ILP) feasibility problem. Therefore, the number of feasible trajectories satisfying the reachability relation can be counted in polynomial time in the number of species and in the distance of initial and target states, assuming fixed number of reactions in the system.

APA, Harvard, Vancouver, ISO, and other styles

7

Shi, Qingkai, Yongchao Wang, Peisen Yao, and Charles Zhang. "Indexing the extended Dyck-CFL reachability for context-sensitive program analysis." Proceedings of the ACM on Programming Languages 6, OOPSLA2 (October 31, 2022): 1438–68. http://dx.doi.org/10.1145/3563339.

Full text

Abstract:

Many context-sensitive dataflow analyses can be formulated as an extended Dyck-CFL reachability problem, where function calls and returns are modeled as partially matched parentheses. Unfortunately, despite many works on the standard Dyck-CFL reachability problem, solving the extended version is still of quadratic space complexity and nearly cubic time complexity, significantly limiting the scalability of program analyses. This paper, for the first time to the best of our knowledge, presents a cheap approach to transforming the extended Dyck-CFL reachability problem to conventional graph reachability, a much easier and well-studied problem. This transformation allows us to benefit from recent advances in reachability indexing schemes, making it possible to answer any reachability query in a context-sensitive dataflow analysis within almost constant time plus only a few extra spaces. We have implemented our approach in two common context-sensitive dataflow analyses, one determines pointer alias relations and the other tracks information flows. Experimental results demonstrate that, compared to their original analyses, we can achieve orders of magnitude (10 2 × to 10 5 ×) speedup at the cost of only a moderate space overhead. Our implementation is publicly available.

APA, Harvard, Vancouver, ISO, and other styles

8

Szlobodnyik, Gergely, and Gábor Szederkényi. "Polynomial Time Reachability Analysis in Discrete State Chemical Reaction Networks Obeying Conservation Laws." MATCH - Communications in Mathematical and in Computer Chemistry 89, no. 1 (August 2022): 175–96. http://dx.doi.org/10.46793/match.89-1.175s.

Full text

Abstract:

In this paper the reachability problem of discrete state Chemical Reaction Networks (d-CRNs) is studied. We consider sub-classes of sub-and superconservative d-CRN network structures and prove that the reachability relation can be decided in polynomial time. We make use of the result that in the studied d-CRN sub-classes, the reachability relation is equivalent to the existence of a non-negative integer solution of the d-CRN state equation. The equivalence implies the reformulation of the reachability problem as integer linear programming decision problem. We show that in the studied classes of d-CRN structures, the state equation has a totally unimodular coefficient matrix. As the reachability relation is equivalent to the non-negative integer solution of the state equation, the resulting integer programming decision program can be relaxed to a simple linear program having polynomial time complexity. Hence, in the studied sub-classes of sub and superconservative reaction network structures, the reachability relation can be decided in polynomial time and the number of continuous decision variables is equal to the number of reactions of the d-CRN.

APA, Harvard, Vancouver, ISO, and other styles

9

Li, Yuanbo, Qirun Zhang, and Thomas Reps. "Single-Source-Single-Target Interleaved-Dyck Reachability via Integer Linear Programming." Proceedings of the ACM on Programming Languages 7, POPL (January 9, 2023): 1003–26. http://dx.doi.org/10.1145/3571228.

Full text

Abstract:

An interleaved-Dyck (InterDyck) language consists of the interleaving of two or more Dyck languages, where each Dyck language represents a set of strings of balanced parentheses.InterDyck-reachability is a fundamental framework for program analyzers that simultaneously track multiple properly-matched pairs of actions such as call/return, lock/unlock, or write-data/read-data.Existing InterDyck-reachability algorithms are based on the well-known tabulation technique. This paper presents a new perspective on solving InterDyck-reachability. Our key observation is that for the single-source-single-target InterDyck-reachability variant, it is feasible to summarize all paths from the source node to the target node based on path expressions . Therefore, InterDyck-reachability becomes an InterDyck-path-recognition problem over path expressions. Instead of computing summary edges as in traditional tabulation algorithms, this new perspective enables us to express InterDyck-reachability as a parenthesis-counting problem, which can be naturally formulated via integer linear programming (ILP). We implemented our ILP-based algorithm and performed extensive evaluations based on two client analyses (a reachability analysis for concurrent programs and a taint analysis). In particular, we evaluated our algorithm against two types of algorithms: (1) the general all-pairs InterDyck-reachability algorithms based on linear conjunctive language (LCL) reachability and synchronized pushdown system (SPDS) reachability, and (2) two domain-specific algorithms for both client analyses. The experimental results are encouraging. Our algorithm achieves 1.42×, 28.24×, and 11.76× speedup for the concurrency-analysis benchmarks compared to all-pair LCL-reachability, SPDS-reachability, and domain-specific tools, respectively; 1.2×, 69.9×, and 0.98× speedup for the taint-analysis benchmarks. Moreover, the algorithm also provides precision improvements, particularly for taint analysis, where it achieves 4.55%, 11.1%, and 6.8% improvement, respectively.

APA, Harvard, Vancouver, ISO, and other styles

10

Lei, Yuxiang, Yulei Sui, Shuo Ding, and Qirun Zhang. "Taming transitive redundancy for context-free language reachability." Proceedings of the ACM on Programming Languages 6, OOPSLA2 (October 31, 2022): 1556–82. http://dx.doi.org/10.1145/3563343.

Full text

Abstract:

Given an edge-labeled graph, context-free language reachability (CFL-reachability) computes reachable node pairs by deriving new edges and adding them to the graph. The redundancy that limits the scalability of CFL-reachability manifests as redundant derivations, i.e., identical edges can be derived multiple times due to the many paths between two reachable nodes. We observe that most redundancy arises from the derivations involving transitive relations of reachable node pairs. Unfortunately, existing techniques for reducing redundancy in transitive-closure-based problems are either ineffective or inapplicable to identifying and eliminating redundant derivations during on-the-fly CFL-reachability solving. This paper proposes a scalable yet precision-preserving approach to all-pairs CFL-reachability analysis by taming its transitive redundancy. Our key insight is that transitive relations are intrinsically ordered, and utilizing the order for edge derivation can avoid most redundancy. To address the challenges in determining the derivation order from the dynamically changed graph during CFL-reachability solving, we introduce a hybrid graph representation by combining spanning trees and adjacency lists, together with a dynamic construction algorithm. Based on this representation, we propose a fast and effective partially ordered algorithm POCR to boost the performance of CFL-reachability analysis by reducing its transitive redundancy during on-the-fly solving. Our experiments on context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++ demonstrate the promising performance of POCR. On average, POCR eliminates 98.50% and 97.26% redundant derivations respectively for the value-flow and alias analysis, achieving speedups of 21.48× and 19.57× over the standard CFL-reachability algorithm. We also compare POCR with two recent open-source tools, Graspan (a CFL-reachability solver) and Soufflé (a Datalog engine). The results demonstrate that POCR is over 3.67× faster than Graspan and Soufflé on average for both value-flow analysis and alias analysis.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Reachability Analysi"

1

Jouda, Fatma, and Sagar Mehdi. "Safety Verification in Vehicle Test Applications : Using Reachability Analysis With the Focus on Reachability Tools." Thesis, Högskolan i Halmstad, Halmstad Embedded and Intelligent Systems Research (EIS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-38947.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hui, Daniel Hang-Yan. "Protocol validation via reachability analysis : an implementation." Thesis, University of British Columbia, 1985. http://hdl.handle.net/2429/24689.

Full text

Abstract:

Reachability analysis is one of the earliest and most common techniques for protocol validation. It is well suited to checking the protocol syntactic properties since they are a direct consequence of the structure of the reachability tree. However, validations of unbounded protocols via reachability analysis always lead to the "state explosion" problem. To overcome this, a new approach in reachability analysis has been proposed by Vuong et al [Vuong 82a, 83a]. While not loosing any information on protocol syntactic properties, the Teachability tree constructed by the new approach for all non-FIFO and for a particular set of FIFO protocols (called well-ordered protocols) will become finite. This thesis is concerned with the implementation of an integrated package called VALIRA (VALIdation via Reachability Analysis) which bases on both the proposed technique and the conventional technique. Details and implementation of the various approaches used in VALIRA are presented in order to provide an insight to the package. Various features of the package are demonstrated with examples on different types of protocols, such as the FIFO, the non-FIFO, and the priority protocols. The use of VALIRA was found to be practical in general, despite some limitations of the package. Further enhancements on the VALIRA are also suggested.
Science, Faculty of
Computer Science, Department of
Graduate

APA, Harvard, Vancouver, ISO, and other styles

3

Lång, Magnus. "Sound and Complete Reachability Analysis under PSO." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-213286.

Full text

Abstract:

Modern multiprocessor systems use weak (relaxed) memory models in order to execute memory sharing multi-threaded code in an efficient manner, but are much harder for programmers to reason about than systems using the sequential consistency memory model. The SB abstraction and its implementation in the Memorax tool allows sound and complete checking of control state reachability under the TSO memory model, used in modern x86 processors. In this paper, I present a formalisation of the PSO memory model using the semantics of the Sun SPARC documentation and an alternate semantic, called Partial Write Serialisation, I conjecture to be equivalent with my formalisation under the control state reachability problem. PWS is proved to be a well-structured system which allows sound and complete reachability analysis. An implementation of PWS is presented as part of the Memorax tool and demonstrated experimentally to be capable of analysing reachability and inferring minimal fence sets on many non-trivial and real world examples in reasonable time and memory usage.

APA, Harvard, Vancouver, ISO, and other styles

4

Ganesan, Sudakshin. "Real Time Reachability Analysis for Marine Vessels." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-247878.

Full text

Abstract:

Safety verification of continuous dynamical systems require the computationof the reachable set. The reachable set comprises those states the systemcan reach at a specific point in time. The present work aims to compute thisreachable set for the marine vessel, in the presence of uncertainties in thedynamic modeling of the system and in the presence of external disturbancesin the form of wind, waves and currents. The reachable set can then be usedto check if the vessel collides with an obstacle. The dynamic model used isthat of a nonlinear maneuvering model for the marine vessel. The dynamicson the azipod actuators are also considered.Several methods are considered to solve the reachability problem for themarine vessel. The first method considered is that of the Hamilton JacobiReachability analysis, where a dynamic game between the control input andthe disturbance input is played. This results in a dynamic programmingproblem known as the Hamilton Jacobi Bellman Isaacs (HJBI) equation. Itis solved using the Level-Set method, but it suffers from the curse of dimensionality.The other method considered is the use of set-theoretic approach,where an over-approximation of the reachable set is computed, in the contextof safety verification. But on the downside, large sets of admissible controlyields highly over-approximated reachable sets, which cannot be usedIn order to overcome the disadvantages posed by the first two methods,emphasizing on the real-time computation, a third method is developed, wherea supervised classification algorithm is used to compute the reachable setboundary. The dataset required for the classification algorithm is computedby solving a 2 Point Boundary Value Optimal Control Problem for the marinevessel. The features for classification algorithm can be extended, so as toinclude the uncertainties and disturbances in the system. The computationtime is greatly reduced and the accuracy of the method is comparable to theexact reachable set computation.
Säkerhetsverifiering av kontinuerliga dynamiska system kräver beräkningav mängden av tillstånd som kan nås vid en specifik tidpunkt, givet dess initialtillstånd.Detta arbete fokuserar påatt bestämma denna mängd av nåbaratillstånd för ett marint fartyg under modellosäkerheter och externa störningari form av vind, vågor och strömmar. Den nåbara mängden av tillstånd användssedan för att kontrollera om fartyget riskerar att kollidera med hinder.Den dynamiska modell som används i våra studier är en icke-linjär modelldär även dynamiken hos azipod-ställdonen betraktas.Arbetet studerar flera metoder för att lösa problemet: en klassisk Hamilton-Jacobi nåbarhetsanalys, en mängd-teoretisk teknik, samt en ny metod baseradpåmaskininlärning. Numeriska simuleringsstudier bekräftar att den föreslagnamaskininlärningsmetoden är snabbare än de tvåalternativen.

APA, Harvard, Vancouver, ISO, and other styles

5

Hollingum, Nicholas. "On the Practice and Application of Context-Free Language Reachability." Thesis, The University of Sydney, 2017. http://hdl.handle.net/2123/17866.

Full text

Abstract:

The Context-Free Language Reachability (CFL-R) formalism relates to some of the most important computational problems facing researchers and industry practitioners. CFL-R is a generalisation of graph reachability and language recognition, such that pairs in a labelled graph are reachable if and only if there is a path between them whose labels, joined together in the order they were encountered, spell a word in a given context-free language. The formalism finds particular use as a vehicle for phrasing and reasoning about program analysis, since complex relationships within the data, logic or structure of computer programs are easily expressed and discovered in CFL-R. Unfortunately, The potential of CFL-R can not be met by state of the art solvers. Current algorithms have scalability and expressibility issues that prevent them from being used on large graph instances or complex grammars. This work outlines our efforts in understanding the practical concerns surrounding CFL-R, and applying this knowledge to improve the performance of CFL-R applications. We examine the major difficulties with solving CFL-R-based analyses at-scale, via a case-study of points-to analysis as a CFL-R problem. Points-to analysis is fundamentally important to many modern research and industry efforts, and is relevant to optimisation, bug-checking and security technologies. Our understanding of the scalability challenge motivates work in developing practical CFL-R techniques. We present improved evaluation algorithms and declarative optimisation techniques for CFL-R, capitalising on the simplicity of CFL-R to creating fully automatic methodologies. The culmination of our work is a general-purpose and high-performance tool called Cauliflower, a solver-generator for CFL-R problems. We describe Cauliflower and evaluate its performance experimentally, showing significant improvement over alternative general techniques.

APA, Harvard, Vancouver, ISO, and other styles

6

Ausmees, Kristiina. "Zone-Based Reachability Analysis of Dense-Timed Pushdown Automata." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-179802.

Full text

Abstract:

Proving that programs behave correctly is a matter of both great theoretical interest as well as practical use. One way to do this is by analyzing a model of the system in question in order to determine if it meets a given specification. Real-time recursive systems can be modeled by dense-timed pushdown automata, a model which combines the behaviours of classical timed automata and pushdown automata. The problem of reachability has been proven to be decidable for this model. The algorithm that solves this problem relies on constructing a classical pushdown automaton that mimics the behaviour of a given timed pushdown automaton by means of an abstraction that uses regions as a symbolic representation of states. The drawback of this approach is that the untimed automaton produced generally contains a very large number of states. This report proposes a method of generalizing this abstraction by using zones instead of regions, in order to minimize the number of states in the untimed automaton.

APA, Harvard, Vancouver, ISO, and other styles

7

Yan, Chao. "Projectagon-based reachability analysis for circuit-level formal verification." Thesis, University of British Columbia, 2011. http://hdl.handle.net/2429/37135.

Full text

Abstract:

This dissertation presents a novel verification technique for analog and mixed signal circuits. Analog circuits are widely used in many applications include consumer electronics, telecommunications, medical electronics. Furthermore, in deep sub-micron design, physical effects might undermine common digital abstractions of circuit behavior. Therefore, it is necessary to develop systematic methodologies to formally verify hardware design using circuit-level models. We present a formal method for circuit-level verification. Our approach is based on translating verification problems to reachability analysis problems. It applies nonlinear ODEs to model circuit dynamics using modified nodal analysis. Forward reachable regions are computed from given initial states to explore all possible circuit behaviors. Analog properties are checked on all circuit states to ensure full correctness or find a design flaw. Our specification language extends LTL logic with continuous time and values and applies Brockett’s annuli to specify analog signals. We also introduced probability into the specification to support practical analog properties such as metastability behavior. We developed and implemented a reachability analysis tool COHO for a simple class of moderate-dimensional hybrid systems with nonlinear ODE dynamics. COHO employs projectagons to represent and manipulate moderate-dimensional, non-convex reachable regions. COHO solves nonlinear ODEs by conservatively approximating ODEs as linear differential inclusions. COHO is robust and efficient. It uses arbitrary precision rational numbers to implement exact computation and trims projectagons to remove infeasible regions. To improve performance and reduce error, several techniques are developed, including a guess-verify strategy, hybrid computation, approximate algorithms, and so on. The correctness and efficiency of our methods have been demonstrated by the success of verifying several circuits, including a toggle circuit, a flip-flop circuit, an arbiter circuit, and a ring-oscillator circuit proposed by researchers from Rambus Inc. Several important properties of these circuits have been verified and a design flaw was spotted during the toggle verification. During the reachability computation, we recognized new problems (e.g., stiffness) and proposed our solutions to these problems. We also developed new methods to analyze complex properties such as metastable behaviors. The combination of these methods and reachability analysis is capable of verifying practical circuits.

APA, Harvard, Vancouver, ISO, and other styles

8

Lin, Yi-Tzer. "Modeling and analysis for message reachability in distributed manufacturing systems." Diss., Georgia Institute of Technology, 1994. http://hdl.handle.net/1853/24292.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Scott, Joseph Kirk. "Reachability analysis and deterministic global optimization of differential-algebraic systems." Thesis, Massachusetts Institute of Technology, 2012. http://hdl.handle.net/1721.1/76539.

Full text

Abstract:

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Chemical Engineering, 2012.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (p. 447-460).
Systems of differential-algebraic equations (DAEs) are used to model an incredible variety of dynamic phenomena. In the chemical process industry in particular, the numerical simulation of detailed DAE models has become a cornerstone of many core activities including, process development, economic optimization, control system design and safety analysis. In such applications, one is primarily interested in the behavior of the model solution with respect variations in the model inputs or uncertainties in the model itself. This thesis addresses two computational problems of general interest in this regard. In the first, we are interested in computing a guaranteed enclosure of all solutions of a given DAE model subject to a specified set of inputs. This analysis has natural applications in uncertainty quantification and process safety verification, and is used for many important tasks in process control. However, for nonlinear dynamic systems, this task is very difficult. Existing methods apply only to ordinary differential equation (ODE) models, and either provide very conservative enclosures or require excessive computational effort. Here, we present new methods for computing interval bounds on the solutions of ODEs and DAEs. For ODEs, the focus is on efficient methods for using physical information that is often available in applications to greatly reduce the conservatism of existing methods. These methods are then extended for the first time to the class of semi-explicit index-one DAEs. The latter portion of the thesis concerns the global solution of optimization problems constrained by DAEs. Such problems arise in optimal control of batch processes, determination of optimal start-up and shut-down procedures, and parameter estimation for dynamic models. In nearly all conceivable applications, there is significant economic and/or intellectual impetus to locate a globally optimal solution. Yet again, this problem has proven to be extremely difficult for nonlinear dynamic models. A small number of practical algorithms have been proposed, all of which are limited to ODE models and require significant computational effort. Here, we present improved lower-bounding procedures for ODE constrained problems and develop a complete deterministic algorithm for problems constrained by semi-explicit index-one DAEs for the first time.
by Joseph Kirk Scott.
Ph.D.

APA, Harvard, Vancouver, ISO, and other styles

10

Chai, Xinwei. "Reachability Analysis and Revision of Dynamics of Biological Regulatory Networks." Thesis, Ecole centrale de Nantes, 2019. http://www.theses.fr/2019ECDN0014/document.

Full text

Abstract:

Les systèmes concurrents sont un bon choix pour ajuster les données et analyser les mécanismes sous-jacents pour leur sémantique simple mais expressive. Cependant, l’apprentissage et l’analyse de tels systèmes concurrents sont difficiles pour ce qui concerne les calculs. Lorsqu’il s’agit de grands ensembles de données, les techniques les plus récentes semblent insuffisantes, que ce soit en termes d’efficacité ou de précision. Ici, nous proposons un cadre de modélisation raffiné ABAN (Asynchronous Binary Automata Network) et développons des outils pour analyser l’atteignabilité : PermReach (Reachability via Permutation search) et ASPReach (Reachability via Answer Set Programming). Nous proposons ensuite deux méthodes de construction et d’apprentissage des modèles: CRAC (Completion via Reachability And Correlations) et M2RIT (Model Revision via Reachability and Interpretation Transitions) en utilisant des données continues et discrètes pour s’ajuster au modèle et des propriétés d’accessibilité afin de contraindre les modèles en sortie
Concurrent systems become a good choice to fit the data and analyze the underlying mechanics for their simple but expressive semantics. However, learning and analyzing such concurrent systems are computationally difficult. When dealing with big data sets, the state-of-the-art techniques appear to be insufficient, either in term of efficiency or in term of precision. In this thesis, we propose a refined modeling framework ABAN (Asynchronous Binary Automata Network) and develop reachability analysis techniques based on ABAN: PermReach (Reachability via Permutation search) and ASPReach (Reachability via Answer Set Programming). Then we propose two model learning/constructing methods: CRAC (Completion via Reachability And Correlations) and M2RIT (Model Revision via Reachability and Interpretation Transitions) using continuous and discrete data to fit the model and using reachability properties to constrain the output models

APA, Harvard, Vancouver, ISO, and other styles

More sources

Books on the topic "Reachability Analysi"

1

Meyer, Pierre-Jean, Alex Devonport, and Murat Arcak. Interval Reachability Analysis. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-65110-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Bujorianu, Luminita Manuela. Stochastic Reachability Analysis of Hybrid Systems. London: Springer London, 2012. http://dx.doi.org/10.1007/978-1-4471-2795-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Bujorianu, Luminita Manuela. Stochastic reachability analysis of hybrid systems. London: Springer, 2012.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Validation of communications systems with SDL: The art of SDL simulation and reachability analysis. Chichester: Wiley, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Jérôme, Leroux, Potapov Igor, and SpringerLink (Online service), eds. Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

Bujorianu, Luminita Manuela. Stochastic Reachability Analysis of Hybrid Systems. Springer, 2012.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

7

Bujorianu, Luminita Manuela. Stochastic Reachability Analysis of Hybrid Systems. Springer, 2014.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Doldi, Laurent. Validation of Communications Systems with SDL: The Art of SDL Simulation and Reachability Analysis. Wiley & Sons, Limited, John, 2005.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

9

Meyer, Pierre-Jean, Alex Devonport, and Murat Arcak. Interval Reachability Analysis: Bounding Trajectories of Uncertain Systems with Boxes for Control and Verification. Springer International Publishing AG, 2021.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

10

Doldi, Laurent. Validation of Communications Systems with SDL: The Art of SDL Simulation and Reachability Analysis. Wiley & Sons, Incorporated, John, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Reachability Analysi"

1

Sun, Dawei, and Sayan Mitra. "NeuReach: Learning Reachability Functions from Simulations." In Tools and Algorithms for the Construction and Analysis of Systems, 322–37. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99524-9_17.

Full text

Abstract:

AbstractWe present , a tool that uses neural networks for predicting reachable sets from executions of a dynamical system. Unlike existing reachability tools, computes a reachability function that outputs an accurate over-approximation of the reachable set for any initial set in a parameterized family. Such reachability functions are useful for online monitoring, verification, and safe planning. implements empirical risk minimization for learning reachability functions. We discuss the design rationale behind the optimization problem and establish that the computed output is probably approximately correct. Our experimental evaluations over a variety of systems show promise. can learn accurate reachability functions for complex nonlinear systems, including some that are beyond existing methods. From a learned reachability function, arbitrary reachtubes can be computed in milliseconds. is available at https://github.com/sundw2014/NeuReach.

APA, Harvard, Vancouver, ISO, and other styles

2

McMillan, Ken L. "Craig Interpolation and Reachability Analysis." In Static Analysis, 336. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-44898-5_18.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Thomas, Dina, Supratik Chakraborty, and Paritosh Pandya. "Efficient Guided Symbolic Reachability Using Reachability Expressions." In Tools and Algorithms for the Construction and Analysis of Systems, 120–34. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11691372_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Cacciari, Leo, and Omar Rafiq. "A temporal reachability analysis." In Protocol Specification, Testing and Verification XV, 35–49. Boston, MA: Springer US, 1996. http://dx.doi.org/10.1007/978-0-387-34892-6_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Balasubramanian, A. R., Lucie Guillou, and Chana Weil-Kennedy. "Parameterized Analysis of Reconfigurable Broadcast Networks." In Lecture Notes in Computer Science, 61–80. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99253-8_4.

Full text

Abstract:

AbstractReconfigurable broadcast networks (RBN) are a model of distributed computation in which agents can broadcast messages to other agents using some underlying communication topology which can change arbitrarily over the course of executions. In this paper, we conduct parameterized analysis of RBN. We consider cubes, (infinite) sets of configurations in the form of lower and upper bounds on the number of agents in each state, and we show that we can evaluate boolean combinations over cubes and reachability sets of cubes in . In particular, reachability from a cube to another cube is a -complete problem.To prove the upper bound for this parameterized analysis, we prove some structural properties about the reachability sets and the symbolic graph abstraction of RBN, which might be of independent interest. We justify this claim by providing two applications of these results. First, we show that the almost-sure coverability problem is -complete for RBN, thereby closing a complexity gap from a previous paper [3]. Second, we define a computation model using RBN, à la population protocols, called RBN protocols. We characterize precisely the set of predicates that can be computed by such protocols.

APA, Harvard, Vancouver, ISO, and other styles

6

Madsen, Magnus, and Anders Møller. "Sparse Dataflow Analysis with Pointers and Reachability." In Static Analysis, 201–18. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-10936-7_13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Pratikakis, Polyvios, Jeffrey S. Foster, and Michael Hicks. "Existential Label Flow Inference Via CFL Reachability." In Static Analysis, 88–106. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11823230_7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Busi, Nadia, and Gianluigi Zavattaro. "Reachability Analysis in Boxed Ambients." In Lecture Notes in Computer Science, 143–59. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11560586_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Dang, Thao, and Oded Maler. "Reachability analysis via face lifting." In Hybrid Systems: Computation and Control, 96–109. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-64358-3_34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Fisher, Andrew N., Chris J. Myers, and Peng Li. "Reachability Analysis Using Extremal Rates." In Lecture Notes in Computer Science, 158–72. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-17524-9_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Reachability Analysi"

1

Goubault, Eric, Olivier Mullier, Sylvie Putot, and Michel Kieffer. "Inner approximated reachability analysis." In HSCC'14: 17th International Conference on Hybrid Systems: Computation and Control. New York, NY, USA: ACM, 2014. http://dx.doi.org/10.1145/2562059.2562113.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hansen, Hallstein A., and Gerardo Schneider. "Reachability analysis of GSPDIs." In the 2010 ACM Symposium. New York, New York, USA: ACM Press, 2010. http://dx.doi.org/10.1145/1774088.1774609.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

"Front cover." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479374.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

"Copyright." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479375.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Duracz, Adam, Ferenc A. Bartha, and Walid Taha. "Accurate rigorous simulation should be possible for good designs." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479376.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Basagiannis, Stylianos. "Software certification of airborne cyber-physical systems under DO-178C." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479378.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Adimoolam, Arvind S., and Thao Dang. "Template complex zonotopes: a new set representation for verification of hybrid systems." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479379.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ratschan, Stefan. "Computing ODE-barriers in hyper-rectangles." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479380.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Vignali, Riccardo, and Maria Prandini. "Model reduction of discrete time hybrid systems: A structural approach based on observability." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479381.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Gao, Yang, and Martin Franzle. "CSiSAT: A satisfiability solver for SMT formulas with continuous probability distributions." In 2016 International Workshop on Symbolic and Numerical Methods for Reachability Analysis (SNR). IEEE, 2016. http://dx.doi.org/10.1109/snr.2016.7479382.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Reachability Analysi"

1

Gao, Sicun, Soonho Kong, and Edmund M. Clarke. Delta-Complete Reachability Analysis (Part 1). Fort Belvoir, VA: Defense Technical Information Center, December 2013. http://dx.doi.org/10.21236/ada600179.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Gao, Sicun, Soonho Kong, Wei Chen, and Edmund M. Clarke. Delta-Complete Analysis for Bounded Reachability of Hybrid Systems. Fort Belvoir, VA: Defense Technical Information Center, July 2014. http://dx.doi.org/10.21236/ada613813.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!