Journal articles: 'Reachability testing'

1

HWANG, GWAN-HWAN, KUO-CHUNG TAI, and TING-LU HUANG. "REACHABILITY TESTING: AN APPROACH TO TESTING CONCURRENT SOFTWARE." International Journal of Software Engineering and Knowledge Engineering 05, no. 04 (December 1995): 493–510. http://dx.doi.org/10.1142/s0218194095000241.

Full text

Abstract:

Concurrent programs are more difficult to test than sequential programs because of non-deterministic behavior. An execution of a concurrent program non-deterministically exercises a sequence of synchronization events called a synchronization sequence (or SYN-sequence). Non-deterministic testing of a concurrent program P is to execute P with a given input many times in order to exercise distinct SYN-sequences. In this paper, we present a new testing approach called reachability testing. If every execution of P with input X terminates, reachability testing of P with input X derives and executes all possible SYN-sequences of P with input X. We show how to perform reachability testing of concurrent programs using read and write operations. Also, we present results of empirical studies comparing reachability and non-deterministic testing. Our results indicate that reachability testing has advantages over non-deterministic testing.

APA, Harvard, Vancouver, ISO, and other styles

2

Lei, Y., and R. H. Carver. "Reachability testing of concurrent programs." IEEE Transactions on Software Engineering 32, no. 6 (June 2006): 382–403. http://dx.doi.org/10.1109/tse.2006.56.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Carver, Richard H., and Yu Lei. "Distributed reachability testing of concurrent programs." Concurrency and Computation: Practice and Experience 22, no. 18 (November 12, 2010): 2445–66. http://dx.doi.org/10.1002/cpe.1573.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Aceto, Luca, Patricia Bouyer, Augusto Burgueño, and Kim G. Larsen. "The power of reachability testing for timed automata." Theoretical Computer Science 300, no. 1-3 (May 2003): 411–75. http://dx.doi.org/10.1016/s0304-3975(02)00334-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Yim, Jaegeol, Peter C. Nelson, and Tadao Murata. "Predicate-Transition Net Reachability Testing Using Heuristic Search." IEEJ Transactions on Electronics, Information and Systems 114, no. 9 (1994): 907–13. http://dx.doi.org/10.1541/ieejeiss1987.114.9_907.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Ramaswamy, Vidhya, Jayalal Sarma, and K. S. Sunil. "Space complexity of reachability testing in labelled graphs." Journal of Computer and System Sciences 105 (November 2019): 40–53. http://dx.doi.org/10.1016/j.jcss.2019.04.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

WONG, W. ERIC, and YU LEI. "REACHABILITY GRAPH-BASED TEST SEQUENCE GENERATION FOR CONCURRENT PROGRAMS." International Journal of Software Engineering and Knowledge Engineering 18, no. 06 (September 2008): 803–22. http://dx.doi.org/10.1142/s0218194008003878.

Full text

Abstract:

One common approach to test sequence generation for structurally testing concurrent programs involves constructing a reachability graph (RG) and selecting a set of paths from the graph to satisfy some coverage criterion. It is often suggested that test sequence generation methods for testing sequential programs based on a control flow graph (CFG) can also be used to select paths from an RG for testing concurrent programs. However, there is a major difference between these two, as the former suffers from a feasibility problem (i.e., some paths in a CFG may not be feasible at run-time) and the latter does not. As a result, even though test sequence generation methods for sequential programs can be applied to concurrent programs, they may not be efficient. We propose four methods — two based on hot spot prioritization and two based on topological sort — to effectively generate a small set of test sequences that covers all the nodes in an RG. The same methods are also applied to the corresponding dual graph for generating test sequences to cover all the edges. A case study was conducted to demonstrate the use of our methods.

APA, Harvard, Vancouver, ISO, and other styles

8

Aichernig, Bernhard K., and Elisabeth Jöbstl. "Towards Symbolic Model-Based Mutation Testing: Combining Reachability and Refinement Checking." Electronic Proceedings in Theoretical Computer Science 80 (February 27, 2012): 88–102. http://dx.doi.org/10.4204/eptcs.80.7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Cheremisinov, D., and L. Cheremisinova. "Model Based Testing of Concurrent Systems Based on Reachability Graph Reduction." Pattern Recognition and Image Analysis 30, no. 1 (January 2020): 7–15. http://dx.doi.org/10.1134/s1054661820010046.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Lu, Chao, and Yansheng Lu. "Combination reduction: A SYN-sequence selection strategy for reachability testing of concurrent programs." Wuhan University Journal of Natural Sciences 12, no. 6 (November 2007): 1024–28. http://dx.doi.org/10.1007/s11859-007-0054-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Song, Minsun, Kyujin Jung, Namhoon Ki, and Richard C. Feiock. "Testing structural and relational embeddedness in collaboration risk." Rationality and Society 32, no. 1 (January 31, 2020): 67–92. http://dx.doi.org/10.1177/1043463120902279.

Full text

Abstract:

The study investigates the effect of embeddedness, defined as a property of interdependent relations in which organizations are integrated in a network, on collaboration risk emerging from relational uncertainty. Despite efforts to understand the structural effects of network governance, embedded relationships and their influence on collaboration remain relatively unexplored. A case of intergovernmental collaboration for emergency management is used as a test bed to examine the role of embeddedness in disaster networks and to extend the knowledge of collaboration risk within the institutional collective action framework. We hypothesize and test the effect of relational and structural embeddedness on the level of collaboration risk that an organization perceives. Our analysis of 69 organizations engaged in emergency management operations in the Seoul Metropolitan Area, South Korea reveals that both structural and relational embeddedness facilitate organizations to mitigate perceived collaboration risk. The results suggest that reachability secures relief of relational risk, and that commitment relationships bind participants.

APA, Harvard, Vancouver, ISO, and other styles

12

Souza, S. R. S., P. S. L. Souza, M. A. S. Brito, A. S. Simao, and E. J. Zaluska. "Empirical evaluation of a new composite approach to the coverage criteria and reachability testing of concurrent programs." Software Testing, Verification and Reliability 25, no. 3 (February 9, 2015): 310–32. http://dx.doi.org/10.1002/stvr.1568.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Bashkin, V. A. "On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits." Modeling and Analysis of Information Systems 20, no. 2 (March 18, 2015): 139–56. http://dx.doi.org/10.18255/1818-1015-2013-2-139-156.

Full text

Abstract:

A class of infinite-state automata with a simple periodic behaviour and a convenient graphical representation is studied. A positive one-counter circuit is defined as a strongly connected one-counter net (one-counter nondeterministic finite automata without zero-testing) with at least one positive cycle. It is shown that in a positive circuit an infinite part of a reachability set is an arithmetic progression; numerical properties of this progression are estimated. A specific graphical representation of circuits is presented. General one-counter nets are equivalent to Petri Nets with at most one unbounded place and to pushdown automata with a single-symbol stack alphabet. It is shown that an arbitrary one-counter net can be represented by a finite tree of circuits. A one-counter net is called sound, if a counter is used only for “infinite-state” (periodic) behaviour. It is shown that for an arbitrary one-counter net an equivalent sound net can be effectively constructed from the corresponding tree of circuits.

APA, Harvard, Vancouver, ISO, and other styles

14

Chen, Gang, Dan Liu, Yifan Wang, Qingxuan Jia, and Xiaodong Zhang. "Path planning method with obstacle avoidance for manipulators in dynamic environment." International Journal of Advanced Robotic Systems 15, no. 6 (November 1, 2018): 172988141882022. http://dx.doi.org/10.1177/1729881418820223.

Full text

Abstract:

Obstacle avoidance is of great importance for path planning of manipulators in dynamic environment. To help manipulators successfully perform tasks, a method of path planning with obstacle avoidance is proposed in this article. It consists of two consecutive phases, namely, collision detection and obstacle-avoidance path planning. The collision detection is realized by establishing point-cloud model and testing intersection of axis-aligned bounding boxes trees, while obstacle-avoidance path planning is achieved through preplanning a global path and adjusting it in real time. This article has the following contributions. The point-cloud model is of high resolution while the speed of collision detection is improved, and collision points can be found exactly. The preplanned global path is optimized based on the improved D-star algorithm, which reduces inflection points and decreases collision probability. The real-time path adjusting strategy satisfies the requirement of reachability and obstacle avoidance for manipulators in dynamic environment. Simulations and experiments are carried out to evaluate the validity of the proposed method, and the method is available to manipulators of any degree of freedom in dynamic environment.

APA, Harvard, Vancouver, ISO, and other styles

15

Tran, Anh-Tuan, Bui Le Ngoc Minh, Phong Thanh Tran, Van Van Huynh, Van-Duc Phan, Viet-Thanh Pham, and Tam Minh Nguyen. "Adaptive Integral Second-Order Sliding Mode Control Design for Load Frequency Control of Large-Scale Power System with Communication Delays." Complexity 2021 (March 20, 2021): 1–19. http://dx.doi.org/10.1155/2021/5564184.

Full text

Abstract:

Nowadays, the power systems are getting more and more complicated because of the delays introduced by the communication networks. The existence of the delays usually leads to the degradation and/or instability of power system performance. On account of this point, the traditional load frequency control (LFC) approach for power system sketches a destabilizing impact and an unacceptable system performance. Therefore, this paper proposes a new LFC based on adaptive integral second-order sliding mode control (AISOSMC) approach for the large-scale power system with communication delays (LSPSwCD). First, a new linear matrix inequality is derived to ensure the stability of whole power systems using Lyapunov stability theory. Second, an AISOSMC law is designed to ensure the finite time reachability of the system states. To the best of our knowledge, this is the first time the AISOSMC is designed for LFC of the LSPSwCD. In addition, the report of testing results presents that the suggested LFC based on AISOSMC can not only decrease effectively the frequency variation but also make successfully less in mount of power oscillation/fluctuation in tie-line exchange.

APA, Harvard, Vancouver, ISO, and other styles

16

Souri, Alireza, Monire Nourozi, Amir Masoud Rahmani, and Nima Jafari Navimipour. "A model checking approach for user relationship management in the social network." Kybernetes 48, no. 3 (March 4, 2019): 407–23. http://dx.doi.org/10.1108/k-02-2018-0092.

Full text

Abstract:

Purpose The purpose of this paper is to describe how formal verification strategies have been utilized to assess the correctness of Knowledge Creation Process (KCP) in the social systems. This paper analyzes a User Relationship Management (URM) approach in term of human behavior connection in the social systems. A formal framework is displayed for the URM which consolidates behavioral demonstrating strategy. Design/methodology/approach Evaluating the human behavior interactions is an important matter in the social systems. For this analysis, formal verification is an essential section in the complex information systems development. Model checking results satisfied the logical problems in the proposed behavior model analysis. Findings Model checking results represent satisfaction of the logical problems in the proposed behavior model analysis. In the statistical testing, the proposed URM mechanism supported KCP conditions. Also, the percentage of state reachability in the URM with KCP conditions is higher than the URM mechanism without supporting KCP conditions. Originality/value The model checking results show that the proposed URM mechanism with supporting the KCP conditions satisfies comprehensively behavioral interactions rather than the mechanism without KCP conditions in the social networks.

APA, Harvard, Vancouver, ISO, and other styles

17

Zeisler, Marie-Luise, Leman Bilgic, Maria Schumann, Annelene Wengler, Johannes Lemcke, Antje Gößwald, Thomas Lampert, Claudia Santos-Hövener, and Patrick Schmich. "Interventions to Increase the Reachability of Migrants in Germany With Health Interview Surveys: Mixed-Mode Feasibility Study." JMIR Formative Research 4, no. 4 (April 15, 2020): e14747. http://dx.doi.org/10.2196/14747.

Full text

Abstract:

Background Germany is a popular destination for immigrants, and migration has increased in recent years. It is therefore important to collect reliable data on migrants’ health. The Robert Koch Institute, Berlin, Germany, has launched the Improving Health Monitoring in Migrant Populations (IMIRA) project to sustainably integrate migrant populations into health monitoring in Germany. Objective One of IMIRA’s objectives is to implement a feasibility study (the IMIRA survey) that focuses on testing various interventions to increase the reachability of migrants with health interview surveys. Possible causes of nonresponse should be identified so as to increase participation in future surveys. Methods The survey target populations were Turkish, Polish, Romanian, Syrian, and Croatian migrants, who represent the biggest migrant groups living in Germany. We used probability sampling, using data from the registration offices in 2 states (Berlin and Brandenburg); we randomly selected 9068 persons by nationality in 7 sample points. We applied age (3 categories: 18-44, 45-64, and ≥65 years) and sex strata. Modes and methods used to test their usability were culturally sensitive materials, online questionnaires, telephone interviews, personal contact, and personal interviews, using multilingual materials and interviewers. To evaluate the effectiveness of the interventions, we used an intervention group (group A) and a control group (group B). There were also focus groups with the interviewers to get more information about the participants’ motivation. We used the European Health Interview Survey, with additional instruments on religious affiliation, experience of discrimination, and subjective social status. We evaluated results according to their final contact result (disposition code). Results We collected data from January to May 2018 in Berlin and Brandenburg, Germany. The survey had an overall response rate of 15.88% (1190/7494). However, final disposition codes varied greatly with regard to citizenship. In addition to the quantitative results, interviewers reported in the focus groups a “feeling of connectedness” to the participants due to the multilingual interventions. The interviewers were particularly positive about the home visits, because “if you are standing at the front door, you will be let in for sure.” Conclusions The IMIRA survey appraised the usability of mixed-mode or mixed-method approaches among migrant groups with a probability sample in 2 German states. When conducting the survey, we were confronted with issues regarding the translation of the questionnaire, as well as the validity of some instruments in the survey languages. A major result was that personal face-to-face contact was the most effective intervention to recruit our participants. We will implement the findings in the upcoming health monitoring study at the Robert Koch Institute.

APA, Harvard, Vancouver, ISO, and other styles

18

Singla, E., S. Singh, and B. Dasgupta. "Maximizing safety margins in task-based design of redundant manipulators for cluttered environments." Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability 231, no. 3 (April 5, 2017): 275–85. http://dx.doi.org/10.1177/1748006x17698332.

Full text

Abstract:

Kinematically redundant manipulators help in handling environmental constraints with extra degrees of freedom, but a large number of links may also lead to significant cumulative errors at the distal end, increasing the likelihood of collisions. The focus of this paper is to synthesize a robot with maximized tolerance to avoid potential collisions, while maneuvering in the workspace. A maximized-tolerance-based method in the design stage provides a significant margin to be utilized further during architectural planning and/or in error compensation against any joint clearance error. This is the main contribution of this paper. The strategy is applicable with even a large number of degrees of freedom. A measure, named as RoboGin, is defined both for a single configuration and for a set of configurations. Maximizing this metric over the large solution space of all robotic parameters provides an optimized design from the reliability perspective. The other requirements related to robot’s reachability at the specified task space locations (TSLs), kinematic conditioning and path connectivity are framed as constraints in the formulated optimization problem. The global solutions computed through a simulated annealing technique show significant improvements in overall safety margins even in highly cluttered environments and with a large number of links. Implementation of the proposed strategy is demonstrated through realistic cluttered environments of a power plant, for a leakage testing application.

APA, Harvard, Vancouver, ISO, and other styles

19

Souri, Alireza, Amir Masoud Rahmani, Nima Jafari Navimipour, and Reza Rezaei. "Formal modeling and verification of a service composition approach in the social customer relationship management system." Information Technology & People 32, no. 6 (December 2, 2019): 1591–607. http://dx.doi.org/10.1108/itp-02-2018-0109.

Full text

Abstract:

Purpose The purpose of this paper is to present a formal verification method to prove the correctness of social customer relationship management (CRM)-based service composition approach. The correctness of the proposed approach is analyzed to evaluate the customer behavioral interactions for discovering, selecting and composing social CRM-based services. In addition, a Kripke structure-based verification method is presented for verifying the behavioral models of the proposed approach. Design/methodology/approach Evaluating the customer behavioral interactions using the social CRM-based service composition approach is an important issue. In addition, formal verification has an important role in assessing the social CRM-based service composition. However, model checking can be efficient as a verification method to evaluate the functional properties of the social CRM-based service composition approach. Findings The results of model checking satisfied the logical problems in the proposed behavior model analysis. In the statistical testing, the proposed URM mechanism supported the four knowledge creation process conditions. It was also shown that the percentage of state reachability in the URM with KCP conditions is higher than the URM mechanism without supporting KCP conditions. Originality/value The comparison of time and memory consumption of the model checking method shows that the social CRM-based service composition approach covers knowledge process features, which makes it an efficient method.

APA, Harvard, Vancouver, ISO, and other styles

20

ZHANG, LEIGANG, SHUAI GUO, and QING SUN. "DEVELOPMENT AND ANALYSIS OF A BILATERAL END-EFFECTER UPPER LIMB REHABILITATION ROBOT." Journal of Mechanics in Medicine and Biology 21, no. 04 (April 10, 2021): 2150032. http://dx.doi.org/10.1142/s0219519421500329.

Full text

Abstract:

Studies have shown that rehabilitation training with the unaffected side guiding affected side is more consistent with the natural movement pattern of human upper limb compared with unilateral rehabilitation training, which is conducive to improve rehabilitation effect of the affected limb motor function. In this paper, a bilateral end-effector upper limb rehabilitation robot (BEULRR) based on two modern commercial manipulators is developed first, then the kinematics, reachability, and dexterity analysis of BEULRR are performed, respectively. Finally, a bilateral symmetric training protocol with the unaffected side guiding the affected side is proposed and evaluated through healthy human subject experiment testing based on BEULRR. The simulation results show that the developed BEULRR could perform spatial rehabilitation training and its rehabilitation training workspace can fully cover the physiological workspace of human upper limb. The preliminary experiment results from the healthy human subject show that the BEULRR system could provide reliable bilateral symmetric training protocol. These simulation and experiment results demonstrated that the developed BEULRR system could be used in bilateral rehabilitation training application, and also show that the BEULRR system has the potential to be applied to clinical rehabilitation training in the further step. In the close future, the proposed BEULRR and bilateral symmetric training protocol are planned to be applied in elderly volunteers and patients with upper limb motor dysfunction for further evaluating.

APA, Harvard, Vancouver, ISO, and other styles

21

Solferino, Nazaria, Viviana Solferino, and Serena Fiona Taurino. "Quantum Entanglement and the Emergence of Collaboration in Social Media." Reports in Advances of Physical Sciences 02, no. 02 (June 2018): 1850004. http://dx.doi.org/10.1142/s2424942418500044.

Full text

Abstract:

In this paper, we devise a slightly modified version of the vote with the wallet game used by Becchetti et al. [L. Becchetti and F. Salustri, The vote with the wallet as a multiplayer prisoner’s dilemma, CEIS Tor Vergata Research Paper No. 359, Vol. 13, Issue 10, Centre for Economic and International Studies, Rome, Italy (2015); L. Becchetti, V. Pelligra and F. Salustri, Testing for heterogeneity of preferences in randomized experiments: A satisfaction-based approach applied to multiple prisoner dilemmas, Appl. Econ. Lett. 24(10) (2017) 722–726] for the use of social media, where the player decides whether to responsibly share social knowledge or not. We follow the point of view of Bennet and Bennet [D. Bennet and A. Bennet, Social learning from the inside out: The creation and sharing of knowledge from the mind/brain perspective, in Social Knowledge: Using Social Media to Know What You Know, eds. J. P. Girard and J. L. Girard (IGI Global, 2011), pp. 1–23] according to which another social settings may emerge through the so-called “process of collaborative entanglement.” In this environment, members of a community interact continuously with strong emotional feelings to combine the sources of knowledge and the beneficiaries of that knowledge and move toward a common direction. The application of the model to the quantum game theory substantially confirms that the cooperative strategy becomes the optimal one depending on the frequency of interactions and people’s cultural, geographical and social reachability and traceability.

APA, Harvard, Vancouver, ISO, and other styles

22

Dilip Babar, Sachin, Neeli Rashmi Prasad, and Ramjee Prasad. "CMKMS." International Journal of Pervasive Computing and Communications 10, no. 2 (May 27, 2014): 196–211. http://dx.doi.org/10.1108/ijpcc-04-2014-0029.

Full text

Abstract:

Purpose – The paper aims to address wireless sensor network (WSN) security by proposing new cluster-based mobile key management scheme (CMKMS). The growing demands of WSNs in variety of real-time and mission-critical applications increase the challenges in terms of energy efficiency, security and mobility. The security is important to avoid malicious attacks and improve the energy efficiency, while mobility helps to improve the reachability of network. The CMKMS algorithm focuses on the management and maintenance of keys under cluster-based mobile WSN network. Design/methodology/approach – The paper studied the related work in the area of key management and compared the different key management algorithms according to the technique used. The comparative study shows that the available key management algorithms are efficient in terms of security, but they are not scaleable enough to the changing conditions of network and do not work efficiently under node mobility. The research uses cluster-based approach for improving scalability, where cluster head (CH) acts as a key manager. The work developed by considering both static and mobile CH. Findings – The CMKMS considers two phases, first for key maintenance which establishes the two private keys, home key for own cluster and foreign key when node moves from one cluster to another. The second phase maintains the keys when CH moves from one cluster to another. The proposed algorithm improves the efficiency of key management algorithm in terms of security, mobility, energy efficiency and scalability of network. The simulation of scheme in different realistic situation shows that proposed solution shows less computational overheads, energy consumption and delay as compared with state-of-art solution. Research limitations/implications – The research is validated using computer-based simulation, which limits the testing of research by considering external environmental conditions. Therefore, research can be further test using WSN test bed. Practical implications – The research address the issues in key management, developed the scaleable, and node mobility supportable key management algorithms, for addressing the demands of growing WSN applications. Originality/value – This paper accomplish the security of WSN using scaleable and mobility-supported key management algorithms.

APA, Harvard, Vancouver, ISO, and other styles

23

Price, Heather E. "Principals’ social interactions with teachers." Journal of Educational Administration 53, no. 1 (February 2, 2015): 116–39. http://dx.doi.org/10.1108/jea-02-2014-0023.

Full text

Abstract:

Purpose – The purpose of this paper is to link the social interactions between principals and their teachers to teachers’ perceptions of their students’ engagement with school, empirically testing the theoretical proposition that principals influence students through their teachers in the US charter school environment. The mediating influence of latent beliefs of trust and support are tested in this process. Design/methodology/approach – By analyzing pooled network and survey data collected in 15 Indianapolis charter schools using stepwise, fixed-effects regression techniques, this study tests the association between interactions of principals and teachers, on the one hand, and teachers’ perceptions of student engagement, on the other. The extent to which latent beliefs about teachers – in particular, trust in teachers and support of teachers by the administrators – mediate this relationship is also tested. Findings – Direct relationships between principal-teacher interactions and latent beliefs of trust and support are confirmed. Direct relationships between latent beliefs and perceptions of academic and school engagement are also confirmed. There is a relationship between principal-teacher interactions and teacher perceptions of student engagement, but the mediating effect of latent beliefs of trust and support accounts for much of the direct association. The reachability of the principal remains a significant and direct influence on teachers’ perceptions of academic engagement after accounting for trust and support. Research limitations/implications – Moving beyond principals’ personality dispositions in management and turning to the social relationships that they form with teachers adds to the understanding of how principal leadership affects student learning. Empirically distinguishing between the actual interactions and social dispositions of principals helps inform practical implications. Focussing on how principals’ social interactions with teachers influence teachers’ perceptions of students’ engagement provides a theoretical link as to how principals indirectly influence student achievement. Practical implications – The relationships that principals build with teachers have real implications on the beliefs of trust and support among teachers in a school and have a ripple effect on teachers’ perceptions of student engagement. These findings therefore suggest that frequently moving principals among schools is not an ideal policy. Originality/value – This study tests the theoretical boundaries of school organization research by using a within-schools design with charter schools. It also links leadership research to outcomes typically restricted to research on school culture and climate.

APA, Harvard, Vancouver, ISO, and other styles

24

Aceto, Luca, Augusto Burgueno, and Kim G. Larsen. "Model Checking via Reachability Testing for Timed Automata." BRICS Report Series 4, no. 29 (January 29, 1997). http://dx.doi.org/10.7146/brics.v4i29.18955.

Full text

Abstract:

In this paper we develop an approach to model-checking for timed automata via reachability testing. As our specification formalism, we consider a dense-time logic with clocks. This logic may be used to express safety and bounded liveness properties of real-time systems. We show how to automatically synthesize, for every logical formula phi, a so-called test automaton T_phi in such a way that checking whether a system S satisfies the property phi can be reduced to a reachability question over the system obtained by making T_phi interact with S. <br />The testable logic we consider is both of practical and theoretical interest. On the practical side, we have used the logic, and the associated approach to model-checking via reachability testing it supports, in the specification and verification in Uppaal of a collision avoidance protocol. On the theoretical side, we show that the logic is powerful enough to permit the definition of characteristic properties, with respect to a timed version of<br />the ready simulation preorder, for nodes of deterministic, tau-free timed automata. This allows one to compute behavioural relations via our model-checking technique, therefore effectively reducing the problem of checking the existence of a behavioural relation among states of a timed automaton to a reachability problem.

APA, Harvard, Vancouver, ISO, and other styles

25

Aceto, Luca, Patricia Bouyer, Augusto Burgueno, and Kim G. Larsen. "The Power of Reachability Testing for Timed Automata." BRICS Report Series 5, no. 48 (June 18, 1998). http://dx.doi.org/10.7146/brics.v5i48.19493.

Full text

Abstract:

In this paper we provide a complete characterization of the class of<br />properties of (networks of) timed automata for which model checking can be reduced to reachability checking in the context of testing automata.

APA, Harvard, Vancouver, ISO, and other styles

26

Husfeldt, Thore, and Theis Rauhe. "Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method." BRICS Report Series 4, no. 32 (June 2, 1997). http://dx.doi.org/10.7146/brics.v4i32.18958.

Full text

Abstract:

We introduce new models for dynamic computation based on the cell probe model of Fredman and Yao. We give these models access to nondeterministic queries or the right answer +-1 as an oracle. We prove that for the dynamic partial sum problem, these new powers do not help, the problem retains its lower bound of Omega(log n/log log n). <br />From these results we easily derive a large number of lower bounds of order Omega(log n/log log n) for conventional dynamic models like the random access machine. We prove lower bounds for dynamic algorithms for reachability in directed graphs, planarity testing, planar point location, incremental parsing, fundamental data structure problems like maintaining the majority of the prefixes of a string of bits and range queries. We characterise the complexity of maintaining the value of any symmetric function on the prefixes of a bit string.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Reachability testing'

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