Zhi-Hong Tao; Cong-Hua Zhou; Zhong Chen; Li-Fu Wang
2007-01-01
Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems.This technique reduces model checking of linear temporal logic to propositional satisfiability.In this paper we first present how quantified Boolean decision procedures can replace BDDs.We introduce a bounded model checking procedure for temporal logic CTL* which reduces model checking to the satisfiability of quantified Boolean formulas.Our new technique avoids the space blow up of BDDs, and extends the concept of bounded model checking.
A PSL Bounded Model Checking Method
YU Lei; ZHAO Zongtao
2012-01-01
SAT-based bounded model checking （BMC） is introduced as an important complementary technique to OBDD-based symbolic model checking, and is an efficient verification method for parallel and reactive systems. However, until now the properties verified by bounded model checking are very finite. Temporal logic PSL is a property specification language （IEEE-1850） describing parallel systems and is divided into two parts, i.e. the linear time logic FL and the branch time logic OBE. In this paper, the specification checked by BMC is extended to PSL and its algorithm is also proposed. Firstly, define the bounded semantics of PSL, and then reduce the bounded semantics into SAT by translating PSL specification formula and the state transition relation of the system to the propositional formula A and B, respectively. Finally, verify the satisfiability of the conjunction propositional formula of A and B. The algorithm results in the translation of the existential model checking of the temporal logic PSL into the satisfiability problem of propositional formula. An example of a queue controlling circuit is used to interpret detailedly the executing procedure of the algorithm.
A Metric Encoding for Bounded Model Checking
Pradella, Matteo; Morzenti, Angelo; San Pietro, Pierluigi
In Bounded Model Checking, both the system model and the checked property are translated into a Boolean formula to be analyzed by a SAT-solver. We introduce a new encoding technique which is particularly optimized for managing quantitative future and past metric temporal operators, typically found in properties of hard real time systems. The encoding is simple and intuitive in principle, but it is made more complex by the presence, typical of the Bounded Model Checking technique, of backward and forward loops used to represent an ultimately periodic infinite domain by a finite structure. We report and comment on the new encoding technique and on an extensive set of experiments carried out to assess its feasibility and effectiveness.
Bounded Model Checking of Temporal Formulas with Alloy
Cunha, Alcino
2012-01-01
Alloy is formal modeling language based on first-order relational logic, with no specific support for specifying reactive systems. We propose the usage of temporal logic to specify such systems, and show how bounded model checking can be performed with the Alloy Analyzer.
A Metric Encoding for Bounded Model Checking (extended version)
Pradella, Matteo; Pietro, Pierluigi San
2009-01-01
In Bounded Model Checking both the system model and the checked property are translated into a Boolean formula to be analyzed by a SAT-solver. We introduce a new encoding technique which is particularly optimized for managing quantitative future and past metric temporal operators, typically found in properties of hard real time systems. The encoding is simple and intuitive in principle, but it is made more complex by the presence, typical of the Bounded Model Checking technique, of backward and forward loops used to represent an ultimately periodic infinite domain by a finite structure. We report and comment on the new encoding technique and on an extensive set of experiments carried out to assess its feasibility and effectiveness.
Applied Bounded Model Checking for Interlocking System Designs
Haxthausen, Anne Elisabeth; Peleska, Jan; Pinger, Ralf
2013-01-01
In this article the verification and validation of interlocking systems is investigated. Reviewing both geographical and route-related interlocking, the verification objectives can be structured from a perspective of computer science into (1) verification of static semantics, and (2) verification...... of behavioural (operational) semantics. The former checks that the plant model – that is, the software components reflecting the physical components of the interlocking system – has been set up in an adequate way. The latter investigates trains moving through the network, with the objective to uncover potential...... safety violations. From a formal methods perspective, these verification objectives can be approached by theorem proving, global, or bounded model checking. This article explains the techniques for application of bounded model checking techniques, and discusses their advantages in comparison...
Applied Bounded Model Checking for Interlocking System Designs
Haxthausen, Anne Elisabeth; Peleska, Jan; Pinger, Ralf
2014-01-01
In this paper the verification and validation of interlocking systems is investigated. Reviewing both geographical and route-related interlocking, the verification objectives can be structured from a perspective of computer science into (1) verification of static semantics, and (2) verification of...... behavioural (operational) semantics. The former checks that the plant model – that is, the software components reflecting the physical components of the interlocking system – has been set up in an adequate way. The latter investigates trains moving through the network, with the objective to uncover potential...... safety violations. From a formal methods perspective, these verification objectives can be approached by theorem proving, global, or bounded model checking. This paper explains the techniques for application of bounded model checking techniques, and discusses their advantages in comparison to the...
Improved Bounded Model Checking for the Universal Fragment of CTL
Liang Xu; Wei Chen; Yan-Yan Xu; Wen-Hui Zhang
2009-01-01
SAT-based bounded model checking (BMC) has been introduced as a complementary technique to BDD-based symbolic model checking in recent years, and a lot of successful work has been done in this direction. The approach was first introduced by A. Biere et al. in checking linear temporal logic (LTL) formulae and then also adapted to check formulae of the universal fragment of computation tree logic (ACTL) by W. Penczek et al. As the efficiency of model checking is still an important issue, we present an improved BMC approach for ACTL based on Penczek's method. We consider two aspects of the approach. One is reduction of the number of variables and transitions in the k-model by distinguishing the temporal operator EX from the others. The other is simplification of the transformation of formulae by using uniform path encoding instead of a disjunction of all paths needed in the k-model. With these improvements, for an ACTI, formula, the length of the final encoding of the formula in the worst case is reduced. The improved approach is implemented in the tool BMV and is compared with the original one by applying both to two well known examples, mutual exclusion and dining philosophers. The comparison shows the advantages of the improved approach with respect to the efficiency of model checking.
Correctness of Sensor Network Applications by Software Bounded Model Checking
Werner, Frank; Faragó, David
We investigate the application of the software bounded model checking tool CBMC to the domain of wireless sensor networks (WSNs). We automatically generate a software behavior model from a network protocol (ESAWN) implementation in a WSN development and deployment platform (TinyOS), which is used to rigorously verify the protocol. Our work is a proof of concept that automatic verification of programs of practical size (≈ 21 000 LoC) and complexity is possible with CBMC and can be integrated into TinyOS. The developer can automatically check for pointer dereference and array index out of bound errors. She can also check additional, e.g., functional, properties that she provides by assume- and assert-statements. This experience paper shows that our approach is in general feasible since we managed to verify about half of the properties. We made the verification process scalable in the size of the code by abstraction (eg, from hardware) and by simplification heuristics. The latter also achieved scalability in data type complexity for the properties that were verifiable. The others require technical advancements for complex data types within CBMC's core.
SMT-based Bounded Model Checking with Difference Logic Constraints
Bersani, Marcello M; Morzenti, Angelo; Pradella, Matteo; Rossi, Matteo; Pietro, Pierluigi San
2010-01-01
Traditional Bounded Model Checking (BMC) is based on translating the model checking problem into SAT, the Boolean satisfiability problem. This paper introduces an encoding of Linear Temporal Logic with Past operators (PLTL) into the Quantifier-Free Difference Logic with Uninterpreted Functions (QF-UFIDL). The resulting encoding is a simpler and more concise version of existing SATbased encodings, currently used in BMC. In addition, we present an extension of PLTL augmented with arithmetic relations over integers, which can express unbounded counters; as such, the extended logic is more expressive than PLTL. We introduce suitable restrictions and assumptions that are shown to make the verification problem for the extended logic decidable, and we define an encoding of the new logic into QF-UFIDL. Finally, a performance comparison with the SAT-based approach on purely PLTL examples shows significant improvements in terms of both execution time and memory occupation.
Efficient Proof Engines for Bounded Model Checking of Hybrid Systems
Fränzle, Martin; Herde, Christian
2005-01-01
In this paper we present HySat, a new bounded model checker for linear hybrid systems, incorporating a tight integration of a DPLL-based pseudo-Boolean SAT solver and a linear programming routine as core engine. In contrast to related tools like MathSAT, ICS, or CVC, our tool exploits all of the...
Local Model Checking of Weighted CTL with Upper-Bound Constraints
Jensen, Jonas Finnemann; Larsen, Kim Guldstrand; Srba, Jiri; Østergaard, Lars
We present a symbolic extension of dependency graphs by Liu and Smolka in order to model-check weighted Kripke structures against the logic CTL with upper-bound weight constraints. Our extension introduces a new type of edges into dependency graphs and lifts the computation of fixed-points from...... boolean domain to nonnegative integers in order to cope with the weights. We present both global and local algorithms for the fixed-point computation on symbolic dependency graphs and argue for the advantages of our approach compared to the direct encoding of the model checking problem into dependency...
SMT-Based Bounded Model Checking for Embedded ANSI-C Software
Cordeiro, Lucas; Marques-Silva, Joao
2009-01-01
Propositional bounded model checking has been applied successfully to verify embedded software but is limited by the increasing propositional formula size and the loss of structure during the translation. These limitations can be reduced by encoding word-level information in theories richer than propositional logic and using SMT solvers for the generated verification conditions. Here, we investigate the application of different SMT solvers to the verification of embedded software written in ANSI-C. We have extended the encodings from previous SMT-based bounded model checkers to provide more accurate support for finite variables, bit-vector operations, arrays, structures, unions and pointers. We have integrated the CVC3, Boolector, and Z3 solvers with the CBMC front-end and evaluated them using both standard software model checking benchmarks and typical embedded applications from telecommunications, control systems and medical devices. The experiments show that our approach can analyze larger problems and sub...
Continuous Verification of Large Embedded Software using SMT-Based Bounded Model Checking
Cordeiro, Lucas; Marques-Silva, Joao
2009-01-01
The complexity of software in embedded systems has increased significantly over the last years so that software verification now plays an important role in ensuring the overall product quality. In this context, SAT-based bounded model checking has been successfully applied to discover subtle errors, but for larger applications, it often suffers from the state space explosion problem. This paper describes a new approach called continuous verification to detect design errors as quickly as possible by looking at the Software Configuration Management (SCM) system and by combining dynamic and static verification to reduce the state space to be explored. We also give a set of encodings that provide accurate support for program verification and use different background theories in order to improve scalability and precision in a completely automatic way. A case study from the telecommunications domain shows that the proposed approach improves the error-detection capability and reduces the overall verification time by...
Bounded Model Checking and Inductive Verification of Hybrid Discrete-Continuous Systems
Becker, Bernd; Behle, Markus; Eisenbrand, Fritz;
2004-01-01
verication, bounded plan- ning and heuristic search, combinatorial optimization and integer programming. Af- ter sketching the overall verication ow we present rst results indicating that the combination and tight integration of dierent verication engines is a rst step to pave the way to fully automated BMC...
Model composition in model checking
Felscher, Ingo
2014-01-01
Model-checking allows one to formally check properties of systems: these properties are modeled as logic formulas and the systems as structures like transition systems. These transition systems are often composed, i.e., they arise in form of products or sums. The composition technique allows us to deduce the truth of a formula in the composed system from "interface information": the truth of formulas for the component systems and information in which components which of these formulas hold. W...
Compositional and Quantitative Model Checking
Larsen, Kim Guldstrand
This paper gives a survey of a composition model checking methodology and its succesfull instantiation to the model checking of networks of finite-state, timed, hybrid and probabilistic systems with respect; to suitable quantitative versions of the modal mu-calculus [Koz82]. The method is based on...
Model Checking Is Static Analysis of Modal Logic
Nielson, Flemming; Nielson, Hanne Riis
2010-01-01
it can give an exact characterisation of the semantics of formulae in a modal logic. This shows that model checking can be performed by means of state-of-the-art approaches to static analysis and allow us to conclude that the problems of model checking and static analysis are reducible to each other....... In terms of computational complexity we show that model checking by means of static analysis gives the same complexity bounds as are known for traditional approaches to model checking....
Model Checking as Static Analysis
Zhang, Fuyuan
properties which can predict safe approximations to program behaviors. In this thesis, we have developed several static analysis based techniques to solve model checking problems, aiming at showing the link between static analysis and model checking. We focus on logical approaches to static analysis......Both model checking and static analysis are prominent approaches to detecting software errors. Model Checking is a successful formal method for verifying properties specified in temporal logics with respect to transition systems. Static analysis is also a powerful method for validating program...... multi-valued setting, and we therefore obtain a multivalued analysis for temporal properties specied by CTL formulas. In particular, we have shown that the three-valued CTL model checking problem over Kripke modal transition systems can be exactly encoded in three-valued ALFP. Last, we come back to two...
Checking Model Transformation Refinement
Büttner, Fabian; Egea, Marina; Guerra, Esther; Lara, Juan De
2013-01-01
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-38883-5_15 Proceedings of 6th International Conference, ICMT 2013, Budapest, Hungary, June 18-19, 2013 Refinement is a central notion in computer science, meaning that some artefact S can be safely replaced by a refinement R, which preserves S’s properties. Having available techniques and tools to check transformation refinement would enable (a) the reasoning on whether a transformation correctly impl...
Model Checking Algorithms for CTMDPs
Buchholz, Peter; Hahn, Ernst Moritz; Hermanns, Holger;
2011-01-01
Continuous Stochastic Logic (CSL) can be interpreted over continuoustime Markov decision processes (CTMDPs) to specify quantitative properties of stochastic systems that allow some external control. Model checking CSL formulae over CTMDPs requires then the computation of optimal control strategie...
Advances in Probabilistic Model Checking
Kwiatkowska, Marta; Parker, David
2012-01-01
Probabilistic model checking is an automated verification method that aims to establish the correctness of probabilistic systems. Probability may arise, for example, due to failures of unreliable components, communication across lossy media, or through the use of randomisation in distributed protocols. Probabilistic model checking enables a range of exhaustive, quantitative analyses of properties such as "the probability of a message being delivered within 5ms is at least 0.89". In the last t...
Model checking PSL safety properties
Launiainen, Tuomas
2009-01-01
Model checking is a modern, efficient approach to gaining confidence of the correctness of complex systems. It outperforms conventional testing methods especially in cases where a high degree of confidence in the correctness of the system is required, or when the test runs of the system are difficult to reproduce accurately. In model checking the system is verified against a specification that is expressed in a formal specification language. The main challenges are that the process requires q...
Jansen, D.N.
2002-01-01
The logic ATCTL is a convenient logic to specify properties with actions and real-time. It is intended as a property language for Lightweight UML models [12], which consist mainly of simplified class diagrams and statecharts. ATCTL combines two known extensions of CTL, namely ACTL and TCTL. The reas
Direct Model Checking Matrix Algorithm
Zhi-Hong Tao; Hans Kleine Büning; Li-Fu Wang
2006-01-01
During the last decade, Model Checking has proven its efficacy and power in circuit design, network protocol analysis and bug hunting. Recent research on automatic verification has shown that no single model-checking technique has the edge over all others in all application areas. So, it is very difficult to determine which technique is the most suitable for a given model. It is thus sensible to apply different techniques to the same model. However, this is a very tedious and time-consuming task, for each algorithm uses its own description language. Applying Model Checking in software design and verification has been proved very difficult. Software architectures (SA) are engineering artifacts that provide high-level and abstract descriptions of complex software systems. In this paper a Direct Model Checking (DMC) method based on Kripke Structure and Matrix Algorithm is provided. Combined and integrated with domain specific software architecture description languages (ADLs), DMC can be used for computing consistency and other critical properties.
A k-Bounded Symbolic Execution for Checking Strong Heap Properties of Open Systems
Lee, Jooyong; Deng, Xianghua; Bogor, Robby
2006-01-01
strong heap properties, and it is fully automatic and flexible in terms of its cost and the guarantees it provides. It allows a user-adjustable mixed compositional/non-compositional reasoning and naturally produces error traces as fault evidence. We implemented Kiasan using the Bogor model checking......This paper presents Kiasan, a bounded technique to reason about open systems based on a path sensitive, relatively sound and complete symbolic execution instead of the usual compositional reasoning through weakest precondition calculation that summarizes all execution paths. Kiasan is able to check...
刘怡文; 李伟琴
2002-01-01
Strand Spaces serve as a model of security protocol analysis. In this paper, the main characteristics of Strand Spaces are briefly introduced, and its advantages and disadvantages are presented . An algorithm of building an ideal model of a protocol is proposed, which is used to bound both the abilities of the penetrator and the number of concurrent protocol runs. Combining Model Checking and Strand Spaces, a method is proposed to use both the automatic reasoning mechanism of the Model Checking and the bounds on security protocol analysis to achieve effective analysis of security protocols, avoiding state explosion problems.%Strand Spaces是一种用于分析安全协议的机器证明方法.简要介绍了Strand Spaces的基本特点,分析了其优劣,提出了构造协议的理想子环的算法,并以此来约束协议入侵者的能力和协议并行运行的次数.将模型检查与Strand Spaces结合在一起,提出了一种综合分析方法来验证协议的安全特性,该方法可充分发挥模型检查与Strand Spaces二者的优势.
Bounding species distribution models
Thomas J. STOHLGREN; Catherine S. JARNEVICH; Wayne E. ESAIAS; Jeffrey T. MORISETTE
2011-01-01
Species distribution models are increasing in popularity for mapping suitable habitat for species of management concern.Many investigators now recognize that extrapolations of these models with geographic information systems (GIS) might be sensitive to the environmental bounds of the data used in their development,yet there is no recommended best practice for “clamping” model extrapolations.We relied on two commonly used modeling approaches:classification and regression tree (CART) and maximum entropy (Maxent) models,and we tested a simple alteration of the model extrapolations,bounding extrapolations to the maximum and minimum values of primary environmental predictors,to provide a more realistic map of suitable habitat of hybridized Africanized honey bees in the southwestern United States.Findings suggest that multiple models of bounding,and the most conservative bounding of species distribution models,like those presented here,should probably replace the unbounded or loosely bounded techniques currently used [Current Zoology 57 (5):642-647,2011].
From model checking to model measuring
Henzinger, Thomas A.; Otop, Jan
2013-01-01
We define the model-measuring problem: given a model $M$ and specification~$\\varphi$, what is the maximal distance $\\rho$ such that all models $M'$ within distance $\\rho$ from $M$ satisfy (or violate)~$\\varphi$. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, qu...
Heteroscedasticity checks for regression models
无
2001-01-01
For checking on heteroscedasticity in regression models, a unified approach is proposed to constructing test statistics in parametric and nonparametric regression models. For nonparametric regression, the test is not affected sensitively by the choice of smoothing parameters which are involved in estimation of the nonparametric regression function. The limiting null distribution of the test statistic remains the same in a wide range of the smoothing parameters. When the covariate is one-dimensional, the tests are, under some conditions, asymptotically distribution-free. In the high-dimensional cases, the validity of bootstrap approximations is investigated. It is shown that a variant of the wild bootstrap is consistent while the classical bootstrap is not in the general case, but is applicable if some extra assumption on conditional variance of the squared error is imposed. A simulation study is performed to provide evidence of how the tests work and compare with tests that have appeared in the literature. The approach may readily be extended to handle partial linear, and linear autoregressive models.
Heteroscedasticity checks for regression models
ZHU; Lixing
2001-01-01
［1］Carroll, R. J., Ruppert, D., Transformation and Weighting in Regression, New York: Chapman and Hall, 1988.［2］Cook, R. D., Weisberg, S., Diagnostics for heteroscedasticity in regression, Biometrika, 1988, 70: 1—10.［3］Davidian, M., Carroll, R. J., Variance function estimation, J. Amer. Statist. Assoc., 1987, 82: 1079—1091.［4］Bickel, P., Using residuals robustly I: Tests for heteroscedasticity, Ann. Statist., 1978, 6: 266—291.［5］Carroll, R. J., Ruppert, D., On robust tests for heteroscedasticity, Ann. Statist., 1981, 9: 205—209.［6］Eubank, R. L., Thomas, W., Detecting heteroscedasticity in nonparametric regression, J. Roy. Statist. Soc., Ser. B, 1993, 55: 145—155.［7］Diblasi, A., Bowman, A., Testing for constant variance in a linear model, Statist. and Probab. Letters, 1997, 33: 95—103.［8］Dette, H., Munk, A., Testing heteoscedasticity in nonparametric regression, J. R. Statist. Soc. B, 1998, 60: 693—708.［9］Müller, H. G., Zhao, P. L., On a semi-parametric variance function model and a test for heteroscedasticity, Ann. Statist., 1995, 23: 946—967.［10］Stute, W., Manteiga, G., Quindimil, M. P., Bootstrap approximations in model checks for regression, J. Amer. Statist. Asso., 1998, 93: 141—149.［11］Stute, W., Thies, G., Zhu, L. X., Model checks for regression: An innovation approach, Ann. Statist., 1998, 26: 1916—1939.［12］Shorack, G. R., Wellner, J. A., Empirical Processes with Applications to Statistics, New York: Wiley, 1986.［13］Efron, B., Bootstrap methods: Another look at the jackknife, Ann. Statist., 1979, 7: 1—26.［14］Wu, C. F. J., Jackknife, bootstrap and other re-sampling methods in regression analysis, Ann. Statist., 1986, 14: 1261—1295.［15］H rdle, W., Mammen, E., Comparing non-parametric versus parametric regression fits, Ann. Statist., 1993, 21: 1926—1947.［16］Liu, R. Y., Bootstrap procedures under some non-i.i.d. models, Ann. Statist., 1988, 16: 1696—1708.［17
The model checking fingerprints of CTL operators
Krebs, Andreas; Meier, Arne; Mundhenk, Martin
2015-01-01
The aim of this study is to understand the inherent expressive power of CTL operators. We investigate the complexity of model checking for all CTL fragments with one CTL operator and arbitrary Boolean operators. This gives us a fingerprint of each CTL operator. The comparison between the fingerprints yields a hierarchy of the operators that mirrors their strength with respect to model checking.
Program Analysis as Model Checking
Olesen, Mads Chr.
of an abstract interpretation. For the generalisation to lattice automata to have benefit it is important that efficient tools exist. This thesis presents multi-core tools for efficient and scalable reachability and Büchi emptiness checking of timed/lattice automata. Finally, a number of case studies...... overapproximation of the hardware is needed; the case of identifying timing anomalous hardware for which such abstractions are hard to find is considered....
Engineering Abstractions in Model Checking and Testing
Achenbach, Michael; Ostermann, Klaus
2009-01-01
Abstractions are used in model checking to tackle problems like state space explosion or modeling of IO. The application of these abstractions in real software development processes, however, lacks engineering support. This is one reason why model checking is not widely used in practice yet and testing is still state of the art in falsification. We show how user-defined abstractions can be integrated into a Java PathFinder setting with tools like AspectJ or Javassist and discuss implicati...
Model Checking Discounted Temporal Properties
Alfaro, de Luca; Faella, Marco; Henzinger, Thomas A.; Majumdar, Rupak; Stoelinga, Mariëlle
2004-01-01
Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We
Model Checking Discounted Temporal Properties
Alfaro, de Luca; Faella, Marco; Henzinger, Thomas A.; Majumdar, Rupak; Stoelinga, Mariëlle
2005-01-01
Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We
Model Checking Implantable Cardioverter Defibrillators
Abbas, Houssam; Jang, Kuk Jin; Jiang, Zhihao; Mangharam, Rahul
2015-01-01
Ventricular Fibrillation is a disorganized electrical excitation of the heart that results in inadequate blood flow to the body. It usually ends in death within seconds. The most common way to treat the symptoms of fibrillation is to implant a medical device, known as an Implantable Cardioverter Defibrillator (ICD), in the patient's body. Model-based verification can supply rigorous proofs of safety and efficacy. In this paper, we build a hybrid system model of the human heart+ICD closed loop...
Graded CTL Model Checking for Test Generation
Napoli, Margherita
2011-01-01
Recently there has been a great attention from the scientific community towards the use of the model-checking technique as a tool for test generation in the simulation field. This paper aims to provide a useful mean to get more insights along these lines. By applying recent results in the field of graded temporal logics, we present a new efficient model-checking algorithm for Hierarchical Finite State Machines (HSM), a well established symbolism long and widely used for representing hierarchical models of discrete systems. Performing model-checking against specifications expressed using graded temporal logics has the peculiarity of returning more counterexamples within a unique run. We think that this can greatly improve the efficacy of automatically getting test cases. In particular we verify two different models of HSM against branching time temporal properties.
Engineering Abstractions in Model Checking and Testing
Achenbach, Michael; Ostermann, Klaus
2009-01-01
Abstractions are used in model checking to tackle problems like state space explosion or modeling of IO. The application of these abstractions in real software development processes, however, lacks engineering support. This is one reason why model checking is not widely used in practice yet and...... testing is still state of the art in falsification. We show how user-defined abstractions can be integrated into a Java PathFinder setting with tools like AspectJ or Javassist and discuss implications of remaining weaknesses of these tools. We believe that a principled engineering approach to designing...
Model Checking Classes of Metric LTL Properties of Object-Oriented Real-Time Maude Specifications
Erika Ábrahám; Peter Csaba Ölveczky; Daniela Lepri
2010-01-01
This paper presents a transformational approach for model checking two important classes of metric temporal logic (MTL) properties, namely, bounded response and minimum separation, for nonhierarchical object-oriented Real-Time Maude specifications. We prove the correctness of our model checking algorithms, which terminate under reasonable non-Zeno-ness assumptions when the reachable state space is finite. These new model checking features have been integrated into Real-Time Maude, and are use...
Statistical Model Checking for Biological Systems
David, Alexandre; Larsen, Kim Guldstrand; Legay, Axel;
2014-01-01
Statistical Model Checking (SMC) is a highly scalable simulation-based verification approach for testing and estimating the probability that a stochastic system satisfies a given linear temporal property. The technique has been applied to (discrete and continuous time) Markov chains, stochastic...
Using chemical organization theory for model checking
Kaleta, Christoph; Richter, Stephan; Dittrich, Peter
2009-01-01
Motivation: The increasing number and complexity of biomodels makes automatic procedures for checking the models' properties and quality necessary. Approaches like elementary mode analysis, flux balance analysis, deficiency analysis and chemical organization theory (OT) require only the stoichiometric structure of the reaction network for derivation of valuable information. In formalisms like Systems Biology Markup Language (SBML), however, information about the stoichiometric coefficients re...
Efficient CSL Model Checking Using Stratification
Zhang, Lijun; Jansen, David N.; Nielson, Flemming; Hermanns, Holger
2012-01-01
For continuous-time Markov chains, the model-checking problem with respect to continuous-time stochastic logic (CSL) has been introduced and shown to be decidable by Aziz, Sanwal, Singhal and Brayton in 1996 [ 1, 2]. Their proof can be turned into an approximation algorithm with worse than...
Automata-Based CSL Model Checking
Zhang, Lijun; Jansen, David N.; Nielson, Flemming; Hermanns, Holger
For continuous-time Markov chains, the model-checking problem with respect to continuous-time stochastic logic (CSL) has been introduced and shown to be decidable by Aziz, Sanwal, Singhal and Brayton in 1996. The presented decision procedure, however, has exponential complexity. In this paper, we...
Statistical Model Checking for Stochastic Hybrid Systems
David, Alexandre; Du, Dehui; Larsen, Kim Guldstrand; Legay, Axel; Mikučionis, Marius; Poulsen, Danny Bøgsted; Sedwards, Sean
This paper presents novel extensions and applications of the UPPAAL-SMC model checker. The extensions allow for statistical model checking of stochastic hybrid systems. We show how our race-based stochastic semantics extends to networks of hybrid systems, and indicate the integration technique...... applied for implementing this semantics in the UPPAAL-SMC simulation engine. We report on two applications of the resulting tool-set coming from systems biology and energy aware buildings....
Three Notes on the Complexity of Model Checking Fixpoint Logic with Chop
Lange, Martin
2007-01-01
This paper provides lower complexity bounds of deterministic exponential time for the combined, data and expression complexity of Fixpoint Logic with Chop. This matches the previously known upper bound showing that its model checking problem is EXPTIME-complete, even when the transition system or...
Howard, Y; Gravell, A; Ferreira, C; Augusto, J C
2011-01-01
Trace analysis can be a useful way to discover problems in a program under test. Rather than writing a special purpose trace analysis tool, this paper proposes that traces can usefully be analysed by checking them against a formal model using a standard model-checker or else an animator for executable specifications. These techniques are illustrated using a Travel Agent case study implemented in J2EE. We added trace beans to this code that write trace information to a database. The traces are then extracted and converted into a form suitable for analysis by Spin, a popular model-checker, and Pro-B, a model-checker and animator for the B notation. This illustrates the technique, and also the fact that such a system can have a variety of models, in different notations, that capture different features. These experiments have demonstrated that model-based trace-checking is feasible. Future work is focussed on scaling up the approach to larger systems by increasing the level of automation.
Model Checking over Paraconsistent Temporal Logic
CHEN Dong-huo; WANG Lin-zhang; CUI Jia-lin
2008-01-01
Classical logic cannot be used to effectively reason about concurrent systems with inconsistencies (inconsistencies often occur, especially in the early stage of the development, when large and complex concurrent systems are developed). In this paper, we propose the use of a guasi-classical temporal logic (QCTL) for supporting the verification of temporal properties of such systems even where the consistent model is not available. Our models are paraKripke structures ( extended standard Kripke structures), in which both a formula and its negation are satisfied in a same state, and properties to be verified are expressed by QCTL with paraKripke structures semantics. We introduce a novel notion of paraKripke models, which grasps the paraconsistent character of the entailment relation of QCTL. Furthermore, we explore the methodology of model checking over QCTL, and describe the detailed algorithm of implementing QCTL model checker. In the sequel, a simple example is presented, showing how to exploit the proposed model checking technique to verify the temporal properties of inconsistent concurrent systems.
Statistical Model Checking of Rich Models and Properties
Poulsen, Danny Bøgsted
undecidability issues for the traditional model checking approaches. Statistical model checking has proven itself a valuable supplement to model checking and this thesis is concerned with extending this software validation technique to stochastic hybrid systems. The thesis consists of two parts: the first part...... motivates why existing model checking technology should be supplemented by new techniques. It also contains a brief introduction to probability theory and concepts covered by the six papers making up the second part. The first two papers are concerned with developing online monitoring techniques for...... systems. The fifth paper shows how stochastic hybrid automata are useful for modelling biological systems and the final paper is concerned with showing how statistical model checking is efficiently distributed. In parallel with developing the theory contained in the papers, a substantial part of this work...
SAT-Based Model Checking without Unrolling
Bradley, Aaron R.
A new form of SAT-based symbolic model checking is described. Instead of unrolling the transition relation, it incrementally generates clauses that are inductive relative to (and augment) stepwise approximate reachability information. In this way, the algorithm gradually refines the property, eventually producing either an inductive strengthening of the property or a counterexample trace. Our experimental studies show that induction is a powerful tool for generalizing the unreachability of given error states: it can refine away many states at once, and it is effective at focusing the proof search on aspects of the transition system relevant to the property. Furthermore, the incremental structure of the algorithm lends itself to a parallel implementation.
Distributed Parametric and Statistical Model Checking
Peter Bulychev
2011-10-01
Full Text Available Statistical Model Checking (SMC is a trade-off between testing and formal verification. The core idea of the approach is to conduct some simulations of the system and verify if they satisfy some given property. In this paper we show that SMC is easily parallelizable on a master/slaves architecture by introducing a series of algorithms that scale almost linearly with respect to the number of slave computers. Our approach has been implemented in the UPPAAL SMC toolset and applied on non-trivial case studies.
Workflow Fault Tree Generation Through Model Checking
Herbert, Luke Thomas; Sharp, Robin
2014-01-01
probabilistic structure of the system being modelled. From these calculations, a comprehensive fault tree is generated. Further, we show that annotating the model with rewards (data) allows the expected mean values of reward structures to be calculated at points of failure....... with probabilistic non-deterministic branching. We present an algorithm that allows for exhaustive generation of possible error states that could arise in execution of the model, where the generated error states allow for both fail-stop behaviour and continued system execution. We employ stochastic...... model checking to calculate the probabilities of reaching each non-error system state. Each generated error state is assigned a variable indicating its individual probability of occurrence. Our method can determine the probability of combined faults occurring, while accounting for the basic...
Model Checking JAVA Programs Using Java Pathfinder
Havelund, Klaus; Pressburger, Thomas
2000-01-01
This paper describes a translator called JAVA PATHFINDER from JAVA to PROMELA, the "programming language" of the SPIN model checker. The purpose is to establish a framework for verification and debugging of JAVA programs based on model checking. This work should be seen in a broader attempt to make formal methods applicable "in the loop" of programming within NASA's areas such as space, aviation, and robotics. Our main goal is to create automated formal methods such that programmers themselves can apply these in their daily work (in the loop) without the need for specialists to manually reformulate a program into a different notation in order to analyze the program. This work is a continuation of an effort to formally verify, using SPIN, a multi-threaded operating system programmed in Lisp for the Deep-Space 1 spacecraft, and of previous work in applying existing model checkers and theorem provers to real applications.
Probabilistic Model--Checking of Quantum Protocols
Gay, S; Papanikolaou, N; Gay, Simon; Nagarajan, Rajagopal; Papanikolaou, Nikolaos
2005-01-01
We establish fundamental and general techniques for formal verification of quantum protocols. Quantum protocols are novel communication schemes involving the use of quantum-mechanical phenomena for representation, storage and transmission of data. As opposed to quantum computers, quantum communication systems can and have been implemented using present-day technology; therefore, the ability to model and analyse such systems rigorously is of primary importance. While current analyses of quantum protocols use a traditional mathematical approach and require considerable understanding of the underlying physics, we argue that automated verification techniques provide an elegant alternative. We demonstrate these techniques through the use of PRISM, a probabilistic model-checking tool. Our approach is conceptually simpler than existing proofs, and allows us to disambiguate protocol definitions and assess their properties. It also facilitates detailed analyses of actual implemented systems. We illustrate our techniqu...
Model Checking of Boolean Process Models
Schneider, Christoph; Wehler, Joachim
2011-01-01
In the field of Business Process Management formal models for the control flow of business processes have been designed since more than 15 years. Which methods are best suited to verify the bulk of these models? The first step is to select a formal language which fixes the semantics of the models. We adopt the language of Boolean systems as reference language for Boolean process models. Boolean systems form a simple subclass of coloured Petri nets. Their characteristics are low tokens to mode...
Probabilistic and hybrid model checking deployments for wireless sensor networks
In the early stages of system development, model checking is a good practice for examining the WSNs (Wireless Sensor Networks). Model checking involves verifying a system's properties based on the system's finite state model. For varying applications like computers and wireless communication prior to expensive simulations, model checking has become a vital requirement in order to investigate the performance and reliability. In this paper for the first time, we are presenting probabilistic and hybrid model checking tools which are being implemented to analyse and verify the WSN applications and their examples. Here we are categorizing the model checking tools and presenting how they have been used for the investigation of various behaviours of WSN solutions. Consequently, this paper helps readers/researchers to choose the appropriate model checking tool and to get benefited in shape of validating their solutions. The paper has also highlighted the problems of existing model checking tools within WSN domain. (author)
Conformant Planning via Symbolic Model Checking
Cimatti, A; 10.1613/jair.774
2011-01-01
We tackle the problem of planning in nondeterministic domains, by presenting a new approach to conformant planning. Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal despite the nondeterminism of the domain. Our approach is based on the representation of the planning domain as a finite state automaton. We use Symbolic Model Checking techniques, in particular Binary Decision Diagrams, to compactly represent and efficiently search the automaton. In this paper we make the following contributions. First, we present a general planning algorithm for conformant planning, which applies to fully nondeterministic domains, with uncertainty in the initial condition and in action effects. The algorithm is based on a breadth-first, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists, otherwise it terminates concluding that the problem admits no conformant solution. Second, we provide a symbolic representation ...
Using Model Checking to Validate AI Planner Domain Models
Penix, John; Pecheur, Charles; Havelund, Klaus
1999-01-01
This report describes an investigation into using model checking to assist validation of domain models for the HSTS planner. The planner models are specified using a qualitative temporal interval logic with quantitative duration constraints. We conducted several experiments to translate the domain modeling language into the SMV, Spin and Murphi model checkers. This allowed a direct comparison of how the different systems would support specific types of validation tasks. The preliminary results indicate that model checking is useful for finding faults in models that may not be easily identified by generating test plans.
Model Checking and Model-based Testing in the Railway Domain
Haxthausen, Anne Elisabeth; Peleska, Jan
2015-01-01
This chapter describes some approaches and emerging trends for verification and model-based testing of railway control systems. We describe state-of-the-art methods and associated tools for verifying interlocking systems and their configuration data, using bounded model checking and k-induction. ......This chapter describes some approaches and emerging trends for verification and model-based testing of railway control systems. We describe state-of-the-art methods and associated tools for verifying interlocking systems and their configuration data, using bounded model checking and k......-induction. Using real-world models of novel Danish interlocking systems, it is exemplified how this method scales up and is suitable for industrial application. For verification of the integrated HW/SW system performing the interlocking control tasks, a modelbased hardware-in-the-loop testing approach is presented...
Analyzing Interoperability of Protocols Using Model Checking
WUPeng
2005-01-01
In practical terms, protocol interoperability testing is still laborious and error-prone with little effect, even for those products that have passed conformance testing. Deadlock and unsymmetrical data communication are familiar in interoperability testing, and it is always very hard to trace their causes. The previous work has not provided a coherent way to analyze why the interoperability was broken among protocol implementations under test. In this paper, an alternative approach is presented to analyzing these problems from a viewpoint of implementation structures. Sequential and concurrent structures are both representative implementation structures, especially in event-driven development model. Our research mainly discusses the influence of sequential and concurrent structures on interoperability, with two instructive conclusions: (a) a sequential structure may lead to deadlock; (b) a concurrent structure may lead to unsymmetrical data communication. Therefore, implementation structures carry weight on interoperability, which may not gain much attention before. To some extent, they are decisive on the result of interoperability testing. Moreover, a concurrent structure with a sound task-scheduling strategy may contribute to the interoperability of a protocol implementation. Herein model checking technique is introduced into interoperability analysis for the first time. As the paper shows, it is an effective way to validate developers' selections on implementation structures or strategies.
Checking for normality in linear mixed models
WU Ping; ZHU LiXing; FANG Yun
2012-01-01
Linear mixed models are popularly used to fit continuous longitudinal data,and the random effects are commonly assumed to have normal distribution.However,this assumption needs to be tested so that further analysis can be proceeded well.In this paper,we consider the Baringhaus-Henze-Epps-Pulley (BHEP) tests,which are based on an empirical characteristic function.Differing from their case,we consider the normality checking for the random effects which are unobservable and the test should be based on their predictors.The test is consistent against global alternatives,and is sensitive to the local alternatives converging to the null at a certain rate arbitrarily close to 1/(√)n where n is sample size.Furthermore,to overcome the problem that the limiting null distribution of the test is not tractable,we suggest a new method:use a conditional Monte Carlo test (CMCT) to approximate the null distribution,and then to simulate p-values.The test is compared with existing methods,the power is examined,and several examples are applied to illustrate the usefulness of our test in the analysis of longitudinal data.
Modelling Chinese Smart Grid : A stochastic model checking case study
Yuksel, E.; Nielson, H.R.; Nielson, F. (Technical Univ. of Denmark. DTU Informatics, Kgs. Lyngby (Denmark)); Zhu, H. (East China Normal Univ. (China)); Huang, H. (Wuxi SensingNet Industrialization Research Institute (China))
2012-07-01
In this document, we consider a specific Chinese Smart Grid implementation and try to address the verification problem for certain quantitative properties including performance and battery consumption. We employ stochastic model checking approach and present our modelling and analysis study using PRISM model checker. (Author)
Verifying Multi-Agent Systems via Unbounded Model Checking
Kacprzak, M.; Lomuscio, A.; Lasica, T.; Penczek, W.; Szreter, M.
2004-01-01
We present an approach to the problem of verification of epistemic properties in multi-agent systems by means of symbolic model checking. In particular, it is shown how to extend the technique of unbounded model checking from a purely temporal setting to a temporal-epistemic one. In order to achieve this, we base our discussion on interpreted systems semantics, a popular semantics used in multi-agent systems literature. We give details of the technique and show how it can be applied to the well known train, gate and controller problem. Keywords: model checking, unbounded model checking, multi-agent systems
A Method for Model Checking Feature Interactions
Pedersen, Thomas; Le Guilly, Thibaut; Ravn, Anders Peter; Skou, Arne Joachim
This paper presents a method to check for feature interactions in a system assembled from independently developed concurrent processes as found in many reactive systems. The method combines and refines existing definitions and adds a set of activities. The activities describe how to populate the ...
Modeling Environment for Component Model Checking from Hierarchical Architecture
Pařízek, P.; Plášil, František
2007-01-01
Roč. 182, - (2007), s. 139-153. ISSN 1571-0661 R&D Projects: GA ČR GA201/06/0770 Institutional research plan: CEZ:AV0Z10300504 Keywords : software components * behavior protocols * environment model checking * hierarchical component architecture Subject RIV: JC - Computer Hardware ; Software
Implementing Model-Check for Employee and Management Satisfaction
Jones, Corey; LaPha, Steven
2013-01-01
This presentation will discuss methods to which ModelCheck can be implemented to not only improve model quality, but also satisfy both employees and management through different sets of quality checks. This approach allows a standard set of modeling practices to be upheld throughout a company, with minimal interaction required by the end user. The presenter will demonstrate how to create multiple ModelCheck standards, preventing users from evading the system, and how it can improve the quality of drawings and models.
Efficient Checking of Individual Rewards Properties in Markov Population Models
Bortolussi, Luca; Hillston, Jane
2015-01-01
In recent years fluid approaches to the analysis of Markov populations models have been demonstrated to have great pragmatic value. Initially developed to estimate the behaviour of the system in terms of the expected values of population counts, the fluid approach has subsequently been extended to more sophisticated interrogations of models through its embedding within model checking procedures. In this paper we extend recent work on checking CSL properties of individual agents within a Marko...
Dynamic State Space Partitioning for External Memory Model Checking
Evangelista, Sami; Kristensen, Lars Michael
2009-01-01
We describe a dynamic partitioning scheme usable by model checking techniques that divide the state space into partitions, such as most external memory and distributed model checking algorithms. The goal of the scheme is to reduce the number of transitions that link states belonging to different...... partitions, and thereby limit the amount of disk access and network communication. We report on several experiments made with our verification platform ASAP that implements the dynamic partitioning scheme proposed in this paper....
Model checking biological systems described using ambient calculus
Mardare, Radu Iulian; Priami, Corrado; Qualia, Paola; Vagin, Oleksander
2005-01-01
Model checking biological systems described using ambient calculus. In Proc. of the second International Workshop on Computational Methods in Systems Biology (CMSB04), Lecture Notes in Bioinformatics 3082:85-103, Springer, 2005.......Model checking biological systems described using ambient calculus. In Proc. of the second International Workshop on Computational Methods in Systems Biology (CMSB04), Lecture Notes in Bioinformatics 3082:85-103, Springer, 2005....
Model Checking-Based Testing of Web Applications
ZENG Hongwei; MIAO Huaikou
2007-01-01
A formal model representing the navigation behavior of a Web application as the Kripke structure is proposed and an approach that applies model checking to test case generation is presented. The Object Relation Diagram as the object model is employed to describe the object structure of a Web application design and can be translated into the behavior model. A key problem of model checking-based test generation for a Web application is how to construct a set of trap properties that intend to cause the violations of model checking against the behavior model and output of counterexamples used to construct the test sequences.We give an algorithm that derives trap properties from the object model with respect to node and edge coverage criteria.
Learning Markov Decision Processes for Model Checking
Hua Mao
2012-12-01
Full Text Available Constructing an accurate system model for formal model verification can be both resource demanding and time-consuming. To alleviate this shortcoming, algorithms have been proposed for automatically learning system models based on observed system behaviors. In this paper we extend the algorithm on learning probabilistic automata to reactive systems, where the observed system behavior is in the form of alternating sequences of inputs and outputs. We propose an algorithm for automatically learning a deterministic labeled Markov decision process model from the observed behavior of a reactive system. The proposed learning algorithm is adapted from algorithms for learning deterministic probabilistic finite automata, and extended to include both probabilistic and nondeterministic transitions. The algorithm is empirically analyzed and evaluated by learning system models of slot machines. The evaluation is performed by analyzing the probabilistic linear temporal logic properties of the system as well as by analyzing the schedulers, in particular the optimal schedulers, induced by the learned models.
Learning Markov Decision Processes for Model Checking
Mao, Hua; Chen, Yingke; Jaeger, Manfred;
2012-01-01
Constructing an accurate system model for formal model verification can be both resource demanding and time-consuming. To alleviate this shortcoming, algorithms have been proposed for automatically learning system models based on observed system behaviors. In this paper we extend the algorithm on...... learning probabilistic automata to reactive systems, where the observed system behavior is in the form of alternating sequences of inputs and outputs. We propose an algorithm for automatically learning a deterministic labeled Markov decision process model from the observed behavior of a reactive system....... The proposed learning algorithm is adapted from algorithms for learning deterministic probabilistic finite automata, and extended to include both probabilistic and nondeterministic transitions. The algorithm is empirically analyzed and evaluated by learning system models of slot machines. The...
Model checking Branching-Time Properties of Multi-Pushdown Systems is Hard
Atig, Mohamed Faouzi; Kumar, K Narayan; Saivasan, Prakash
2012-01-01
We address the model checking problem for shared memory concurrent programs modeled as multi-pushdown systems. We consider here boolean programs with a finite number of threads and recursive procedures. It is well-known that the model checking problem is undecidable for this class of programs. In this paper, we investigate the decidability and the complexity of this problem under the assumption of bounded context-switching defined by Qadeer and Rehof, and of phase-boundedness proposed by La Torre et al. On the model checking of such systems against temporal logics and in particular branching time logics such as the modal $\\mu$-calculus or CTL has received little attention. It is known that parity games, which are closely related to the modal $\\mu$-calculus, are decidable for the class of bounded-phase systems (and hence for bounded-context switching as well), but with non-elementary complexity (Seth). A natural question is whether this high complexity is inevitable and what are the ways to get around it. This...
Linear Parametric Model Checking of Timed Automata
Hune, Tohmas Seidelin; Romijn, Judi; Stoelinga, Mariëlle; Vaandrager, Frits W.
We present an extension of the model checker Uppaal capable of synthesize linear parameter constraints for the correctness of parametric timed automata. The symbolic representation of the (parametric) state-space is shown to be correct. A second contribution of this paper is the identication of a...
Abstraction and Model Checking in the PEPA Plug-in for Eclipse
Smith, Michael James Andrew
2010-01-01
The stochastic process algebra PEPA is a widely used language for performance modelling, and a large part of its success is due to the rich tool support that is available. As a compositional Markovian formalism, however, it suffers from the state space explosion problem, where even small models can...... lead to very large Markov chains. One way of analysing such models is to use abstraction - constructing a smaller model that bounds the properties of the original. We present an extension to the PEPA plug-in for Eclipse that enables abstracting and model checking of PEPA models. This implements two new...
Diagnostic checking for conditional heteroscedasticity models
无
2010-01-01
We suggest the score type tests for goodness-of-fit of conditional heteroscedasticity models in both univariate and multivariate time series.The tests can detect the alternatives converging to the null at a parametric rate.Weight functions are involved in the construction of the tests,which provides us with the flexibility to choose scores,especially under directional alternatives,for enhancing power performance.Furthermore,when the alternatives are not directional,we construct asymptotically distribution-free maximin tests for a large class of alternatives.A possibility to construct score-based omnibus tests is discussed when the alternative is saturated.The power performance is also investigated.A simulation study is carried out and a real data is analyzed.
Conductivity bounds in probe brane models
Ikeda, Tatsuhiko N; Nakai, Yuichiro
2016-01-01
We discuss upper and lower bounds on the electrical conductivity of finite temperature strongly coupled quantum field theories, holographically dual to probe brane models, within linear response. In a probe limit where disorder is introduced entirely through an inhomogeneous background charge density, we find simple lower and upper bounds on the electrical conductivity in arbitrary dimensions. In field theories in two spatial dimensions, we show that both bounds persist even when disorder is included in the bulk metric. We discuss the challenges with finding sharp lower bounds on conductivity in three or more spatial dimensions when the metric is inhomogeneous.
Towards Model Checking a Spi-Calculus Dialect
Gnesi, S.; Latella, D.; Lenzini, G.
2002-01-01
We present a model checking framework for a spi-calculus dialect which uses a linear time temporal logic for expressing security properties. We have provided our spi-calculus dialect, called SPID, with a semantics based on labeled transition systems (LTS), where the intruder is modeled in the Dolev-
Using Model Checking for Analyzing Distributed Power Control Problems
Brihaye, Thomas; Jungers, Marc; Lasaulce, Samson; Markey, Nicolas; Oreiby, Ghassan
2010-01-01
Model checking (MC) is a formal verification technique which has been known and still knows a resounding success in the computer science community. Realizing that the distributed power control ( PC) problem can be modeled by a timed game between a given transmitter and its environment, the authors...
Model checking conditional CSL for continuous-time Markov chains
Gao, Yang; Xu, Ming; Zhan, Naijun;
2013-01-01
probabilistic operator. CCSL allows us to express a richer class of properties for CTMCs. Based on a parameterized product obtained from the CTMC and an automaton extracted from a given CCSL formula, we propose an approximate model checking algorithm and analyse its complexity....
An Extended Ontology Model and Ontology Checking Based on Description Logics
王洪伟; 蒋馥; 吴家春
2004-01-01
Ontology is defined as an explicit specification of a conceptualization. In this paper, an extended ontology model was constructed using description logics, which is a 5-tuples including term set, individual set, term definition set, instantiation assertion set and term restriction set. Based on the extended model, the issue on ontology checking was studied with the conclusion that the four kinds of term checking, including term satisfiability checking, term subsumption checking, term equivalence checking and term disjointness checking, can be reduced to the satisfiability checking, and satisfiability checking can be transformed into instantiation consistence checking.
Mixed Portmanteau Test for Diagnostic Checking of Time Series Models
Sohail Chand
2014-01-01
Full Text Available Model criticism is an important stage of model building and thus goodness of fit tests provides a set of tools for diagnostic checking of the fitted model. Several tests are suggested in literature for diagnostic checking. These tests use autocorrelation or partial autocorrelation in the residuals to criticize the adequacy of fitted model. The main idea underlying these portmanteau tests is to identify if there is any dependence structure which is yet unexplained by the fitted model. In this paper, we suggest mixed portmanteau tests based on autocorrelation and partial autocorrelation functions of the residuals. We derived the asymptotic distribution of the mixture test and studied its size and power using Monte Carlo simulations.
Model-Checking Real-Time Properties of an Aircraft Landing Gear System Using Fiacre
Berthomieu, Bernard; Dal Zilio, Silvano; Fronc, Lukasz
2014-01-01
International audience We describe our experience with modeling the landing gear system of an aircraft using the formal specification language Fiacre. Our model takes into account the behavior and timing properties of both the physical parts and the control software of this system. We use this formal model to check safety and real-time properties on the system but also to find a safe bound on the maximal time needed for all gears to be down and locked (assuming the absence of failures). Ou...
Logic Model Checking of Unintended Acceleration Claims in Toyota Vehicles
Gamble, Ed
2012-01-01
Part of the US Department of Transportation investigation of Toyota sudden unintended acceleration (SUA) involved analysis of the throttle control software, JPL Laboratory for Reliable Software applied several techniques including static analysis and logic model checking, to the software; A handful of logic models were build, Some weaknesses were identified; however, no cause for SUA was found; The full NASA report includes numerous other analyses
Symbolic Model Checking and Analysis for E-Commerce Protocol
WEN Jing-Hua; ZHANG Mei; LI Xiang
2005-01-01
A new approach is proposed for analyzing non-repudiation and fairness of e-commerce protocols. The authentication e-mail protocol CMP1 is modeled as finite state machine and analyzed in two vital aspects - non-repudiation and fairness using SMV. As a result, the CMP1 protocol is not fair and we have improved it. This result shows that it is effective to analyze and check the new features of e-commerce protocols using SMV model checker
Schedulability of Herschel revisited using statistical model checking
David, Alexandre; Larsen, Kim Guldstrand; Legay, Axel;
2015-01-01
Schedulability analysis is a main concern for several embedded applications due to their safety-critical nature. The classical method of response time analysis provides an efficient technique used in industrial practice. However, the method is based on conservative assumptions related to execution...... and blocking times of tasks. Consequently, the method may falsely declare deadline violations that will never occur during execution. This paper is a continuation of previous work of the authors in applying extended timed automata model checking (using the tool UPPAAL) to obtain more exact...... schedulability analysis, here in the presence of non-deterministic computation times of tasks given by intervals [BCET,WCET]. Computation intervals with preemptive schedulers make the schedulability analysis of the resulting task model undecidable. Our contribution is to propose a combination of model checking...
Analysis of DIRAC's behavior using model checking with process algebra
Remenska, Daniela; Willemse, Tim; Bal, Henri; Verstoep, Kees; Fokkink, Wan; Charpentier, Philippe; Diaz, Ricardo Graciani; Lanciotti, Elisa; Roiser, Stefan; Ciba, Krzysztof
2012-01-01
DIRAC is the grid solution developed to support LHCb production activities as well as user data analysis. It consists of distributed services and agents delivering the workload to the grid resources. Services maintain database back-ends to store dynamic state information of entities such as jobs, queues, staging requests, etc. Agents use polling to check and possibly react to changes in the system state. Each agent's logic is relatively simple, the main complexity lies in their cooperation. Agents run concurrently, and collaborate using the databases as shared memory. The databases can be accessed directly by the agents if running locally or through a DIRAC service interface if necessary. This shared-memory model causes entities to occasionally get into inconsistent states. Tracing and fixing such problems becomes formidable due to the inherent parallelism present. We propose more rigorous methods to cope with this. Model checking is one such technique for analysis of an abstract model of a system. Unlike con...
Stochastic Semantics and Statistical Model Checking for Networks of Priced Timed Automata
David, Alexandre; Legay, Axel; Mikučionis, Marius; Poulsen, Danny Bøgsted; van Vliet, Jonas; Wang, Zheng
2011-01-01
This paper offers a natural stochastic semantics of Networks of Priced Timed Automata (NPTA) based on races between components. The semantics provides the basis for satisfaction of probabilistic Weighted CTL properties (PWCTL), conservatively extending the classical satisfaction of timed automata with respect to TCTL. In particular the extension allows for hard real-time properties of timed automata expressible in TCTL to be refined by performance properties, e.g. in terms of probabilistic guarantees of time- and cost-bounded properties. A second contribution of the paper is the application of Statistical Model Checking (SMC) to efficiently estimate the correctness of non-nested PWCTL model checking problems with a desired level of confidence, based on a number of independent runs of the NPTA. In addition to applying classical SMC algorithms, we also offer an extension that allows to efficiently compare performance properties of NPTAs in a parametric setting. The third contribution is an efficient tool implem...
Detecting feature interactions in Web services with model checking techniques
无
2007-01-01
As a platform-independent software system, a Web service is designed to offer interoperability among diverse and heterogeneous applications.With the introduction of service composition in the Web service creation, various message interactions among the atomic services result in a problem resembling the feature interaction problem in the telecommunication area.This article defines the problem as feature interaction in Web services and proposes a model checking-based detection method.In the method, the Web service description is translated to the Promela language - the input language of the model checker simple promela interpreter (SPIN), and the specific properties, expressed as linear temporal logic (LTL) formulas, are formulated according to our classification of feature interaction.Then, SPIN is used to check these specific properties to detect the feature interaction in Web services.
Model Checking Processes Specified In Join-Calculus Algebra
Sławomir Piotr Maludziński
2014-01-01
Full Text Available This article presents a model checking tool used to verify concurrent systems specified in join-calculus algebra. The temporal properties of systems under verification are expressed in CTL logic. Join-calculus algebra with its operational semantics defined by the chemical abstract machine serves as the basic method for the specification of concurrent systems and their synchronization mechanisms, and allows the examination of more complex systems.
Model Checking Processes Specified In Join-Calculus Algebra
Sławomir Piotr Maludziński; Grzegorz Dobrowolski
2014-01-01
This article presents a model checking tool used to verify concurrent systems specified in join-calculus algebra. The temporal properties of systems under verification are expressed in CTL logic. Join-calculus algebra with its operational semantics defined by the chemical abstract machine serves as the basic method for the specification of concurrent systems and their synchronization mechanisms, and allows the examination of more complex systems.
A Graphical μ-Calculus and Local Model Checking
林惠民
2002-01-01
A graphical notation for the propositionalμ-calculus, called modal graphs, ispresented. It is shown that both the textual and equational presentations of theμ-calculus canbe translated into modal graphs. A model checking algorithm based on such graphs is proposed.The algorithm is truly local in the sense that it only generates the parts of the underlyingsearch space which are necessary for the computation of the final result. The correctness of thealgorithm is proven and its complexity analysed.
Model Checking for Licensing Support in the Finnish Nuclear Industry
Antti, Pakonen; Janne, Valkonen [VTT Technical Research, VTT (Finland); Sami, Matinaho; Markus, Hartikainen [Protum Power and Heat, Fortum (Finland)
2014-08-15
This paper examines how model checking can be used to support the qualification of digital I and C software in nuclear power plants, in a way that is consistent with regulatory demands specifically, the common position of seven European nuclear regulators and authorised technical support organisations. As a practical example, we discuss the third-party review service provided by VTT for the power company Fortum in the I and C renewal project of the Loviisa plant in southern Finland.
Parallel State Space Construction for Model-Checking
Garavel, Hubert; Mateescu, Radu; Smarandache, Irina
2001-01-01
The verification of concurrent finite-state systems by model-checking often requires to generate (a large part of) the state space of the system under analysis. Because of the state explosion problem, this may be a resource-consuming operation, both in terms of memory and CPU time. In this report, we aim at improving the performances of state space construction by using parallelization techniques. We present parallel algorithms for constructing state spaces (or Labeled Transition Systems) on ...
Model-checking techniques based on cumulative residuals.
Lin, D Y; Wei, L J; Ying, Z
2002-03-01
Residuals have long been used for graphical and numerical examinations of the adequacy of regression models. Conventional residual analysis based on the plots of raw residuals or their smoothed curves is highly subjective, whereas most numerical goodness-of-fit tests provide little information about the nature of model misspecification. In this paper, we develop objective and informative model-checking techniques by taking the cumulative sums of residuals over certain coordinates (e.g., covariates or fitted values) or by considering some related aggregates of residuals, such as moving sums and moving averages. For a variety of statistical models and data structures, including generalized linear models with independent or dependent observations, the distributions of these stochastic processes tinder the assumed model can be approximated by the distributions of certain zero-mean Gaussian processes whose realizations can be easily generated by computer simulation. Each observed process can then be compared, both graphically and numerically, with a number of realizations from the Gaussian process. Such comparisons enable one to assess objectively whether a trend seen in a residual plot reflects model misspecification or natural variation. The proposed techniques are particularly useful in checking the functional form of a covariate and the link function. Illustrations with several medical studies are provided. PMID:11890304
Model-Checking Linear-Time Properties of Quantum Systems
Ying, Mingsheng; Yu, Nengkun; Feng, Yuan
2011-01-01
We define a formal framework for reasoning about linear-time properties of quantum systems in which quantum automata are employed in the modeling of systems and certain closed subspaces of state (Hilbert) spaces are used as the atomic propositions about the behavior of systems. We provide an algorithm for verifying invariants of quantum automata. Then automata-based model-checking technique is generalized for the verification of safety properties recognizable by reversible automata and omega-properties recognizable by reversible Buechi automata.
Model Checking Data Consistency for Cache Coherence Protocols
Hong Pan; Hui-Min Lin; Yi Lv
2006-01-01
A method for automatic verification of cache coherence protocols is presented, in which cache coherence protocols are modeled as concurrent value-passing processes, and control and data consistency requirement are described as formulas in first-orderμ-calculus. A model checker is employed to check if the protocol under investigation satisfies the required properties. Using this method a data consistency error has been revealed in a well-known cache coherence protocol.The error has been corrected, and the revised protocol has been shown free from data consistency error for any data domain size, by appealing to data independence technique.
Applying Model Checking to Industrial-Sized PLC Programs
AUTHOR|(CDS)2079190; Darvas, Daniel; Blanco Vinuela, Enrique; Tournier, Jean-Charles; Bliudze, Simon; Blech, Jan Olaf; Gonzalez Suarez, Victor M
2015-01-01
Programmable logic controllers (PLCs) are embedded computers widely used in industrial control systems. Ensuring that a PLC software complies with its specification is a challenging task. Formal verification has become a recommended practice to ensure the correctness of safety-critical software but is still underused in industry due to the complexity of building and managing formal models of real applications. In this paper, we propose a general methodology to perform automated model checking of complex properties expressed in temporal logics (\\eg CTL, LTL) on PLC programs. This methodology is based on an intermediate model (IM), meant to transform PLC programs written in various standard languages (ST, SFC, etc.) to different modeling languages of verification tools. We present the syntax and semantics of the IM and the transformation rules of the ST and SFC languages to the nuXmv model checker passing through the intermediate model. Finally, two real cases studies of \\CERN PLC programs, written mainly in th...
SoS contract verification using statistical model checking
Alessandro Mignogna
2013-11-01
Full Text Available Exhaustive formal verification for systems of systems (SoS is impractical and cannot be applied on a large scale. In this paper we propose to use statistical model checking for efficient verification of SoS. We address three relevant aspects for systems of systems: 1 the model of the SoS, which includes stochastic aspects; 2 the formalization of the SoS requirements in the form of contracts; 3 the tool-chain to support statistical model checking for SoS. We adapt the SMC technique for application to heterogeneous SoS. We extend the UPDM/SysML specification language to express the SoS requirements that the implemented strategies over the SoS must satisfy. The requirements are specified with a new contract language specifically designed for SoS, targeting a high-level English- pattern language, but relying on an accurate semantics given by the standard temporal logics. The contracts are verified against the UPDM/SysML specification using the Statistical Model Checker (SMC PLASMA combined with the simulation engine DESYRE, which integrates heterogeneous behavioral models through the functional mock-up interface (FMI standard. The tool-chain allows computing an estimation of the satisfiability of the contracts by the SoS. The results help the system architect to trade-off different solutions to guide the evolution of the SoS.
Stochastic Model Checking of the Stochastic Quality Calculus
Nielson, Flemming; Nielson, Hanne Riis; Zeng, Kebin
2015-01-01
The Quality Calculus uses quality binders for input to express strategies for continuing the computation even when the desired input has not been received. The Stochastic Quality Calculus adds generally distributed delays for output actions and real-time constraints on the quality binders for inp...... based on stochastic model checking and we compute closed form solutions for a number of interesting scenarios. The analyses are applied to the design of an intelligent smart electrical meter of the kind to be installed in European households by 2020....
Symbolic Game Semantics for Model Checking Program Families
Dimovski, Aleksandar
this paper, we propose an efficient game semantics based approach for verifying open program families, i.e. program families with free (undefined) identifiers. We use symbolic representation of algorithmic game semantics, where concrete values are replaced with symbolic ones. In this way, we can...... compactly represent program families with infinite integers as so-called (finite-state) featured symbolic automata. Specifically designed model checking algorithms are then employed to verify safety of all programs from a family at once and pinpoint those programs that are unsafe (respectively, safe). We...
Model Checking Degrees of Belief in a System of Agents
Raimondi, Franco; Primero, Giuseppe; Rungta, Neha
2014-01-01
Reasoning about degrees of belief has been investigated in the past by a number of authors and has a number of practical applications in real life. In this paper we present a unified framework to model and verify degrees of belief in a system of agents. In particular, we describe an extension of the temporal-epistemic logic CTLK and we introduce a semantics based on interpreted systems for this extension. In this way, degrees of beliefs do not need to be provided externally, but can be derived automatically from the possible executions of the system, thereby providing a computationally grounded formalism. We leverage the semantics to (a) construct a model checking algorithm, (b) investigate its complexity, (c) provide a Java implementation of the model checking algorithm, and (d) evaluate our approach using the standard benchmark of the dining cryptographers. Finally, we provide a detailed case study: using our framework and our implementation, we assess and verify the situational awareness of the pilot of Air France 447 flying in off-nominal conditions.
Generalized Symbolic Execution for Model Checking and Testing
Khurshid, Sarfraz; Pasareanu, Corina; Visser, Willem; Kofmeyer, David (Technical Monitor)
2003-01-01
Modern software systems, which often are concurrent and manipulate complex data structures must be extremely reliable. We present a novel framework based on symbolic execution, for automated checking of such systems. We provide a two-fold generalization of traditional symbolic execution based approaches: one, we define a program instrumentation, which enables standard model checkers to perform symbolic execution; two, we give a novel symbolic execution algorithm that handles dynamically allocated structures (e.g., lists and trees), method preconditions (e.g., acyclicity of lists), data (e.g., integers and strings) and concurrency. The program instrumentation enables a model checker to automatically explore program heap configurations (using a systematic treatment of aliasing) and manipulate logical formulae on program data values (using a decision procedure). We illustrate two applications of our framework: checking correctness of multi-threaded programs that take inputs from unbounded domains with complex structure and generation of non-isomorphic test inputs that satisfy a testing criterion. Our implementation for Java uses the Java PathFinder model checker.
Model checking as an aid to procedure design
The OECD Halden Reactor Project has been actively working on computer assisted operating procedures for many years. The objective of the research has been to provide computerised assistance for procedure design, verification and validation, implementation and maintenance. For the verification purpose, the application of formal methods has been considered in several reports. The recent formal verification activity conducted at the Halden Project is based on using model checking to the verification of procedures. This report presents verification approaches based on different model checking techniques and tools for the formalization and verification of operating procedures. Possible problems and relative merits of the different approaches are discussed. A case study of one of the approaches is presented to show the practical application of formal verification. Application of formal verification in the traditional procedure design process can reduce the human resources involved in reviews and simulations, and hence reduce the cost of verification and validation. A discussion of the integration of the formal verification with the traditional procedure design process is given at the end of this report. (Author)
Reasoning About Strategies: On the Model-Checking Problem
Mogavero, Fabio; Perelli, Giuseppe; Vardi, Moshe Y
2011-01-01
In open systems verification, to formally check for reliability, one needs an appropriate formalism to model the interaction between agents and express the correctness of the system no matter how the environment behaves. An important contribution in this context is given by modal logics for strategic ability, in the setting of multi-agent games, such as ATL, ATL*, and the like. Recently, Chatterjee, Henzinger, and Piterman introduced Strategy Logic (CHP-SL), with the aim of getting a powerful framework for reasoning explicitly about strategies. CHP-SL is obtained by using first-order quantifications over strategies and it has been investigated in the setting of two-agents turned-based games, where a non-elementary model-checking algorithm has been provided. While CHP-SL is a very expressive logic, we claim that it does not fully capture the strategic aspects of multi-agent systems. In this paper, we introduce and study a more general strategy logic, denoted SL, for reasoning about strategies in multi-agent co...
Using Model Checking for Analyzing Distributed Power Control Problems
Thomas Brihaye
2010-01-01
Full Text Available Model checking (MC is a formal verification technique which has been known and still knows a resounding success in the computer science community. Realizing that the distributed power control (PC problem can be modeled by a timed game between a given transmitter and its environment, the authors wanted to know whether this approach can be applied to distributed PC. It turns out that it can be applied successfully and allows one to analyze realistic scenarios including the case of discrete transmit powers and games with incomplete information. The proposed methodology is as follows. We state some objectives a transmitter-receiver pair would like to reach. The network is modeled by a game where transmitters are considered as timed automata interacting with each other. The objectives are then translated into timed alternating-time temporal logic formulae and MC is exploited to know whether the desired properties are verified and determine a winning strategy.
Model-checking dense-time Duration Calculus
Fränzle, Martin
2004-01-01
Since the seminal work of Zhou Chaochen, M. R. Hansen, and P. Sestoft on decidability of dense-time Duration Calculus [Zhou, Hansen, Sestoft, 1993] it is well-known that decidable fragments of Duration Calculus can only be obtained through withdrawal of much of the interesting vocabulary of this...... logic. While this was formerly taken as an indication that key-press verification of implementations with respect to elaborate Duration Calculus specifications were also impossible, we show that the model property is well decidable for realistic designs which feature natural constraints on their...... suitably sparser model classes we obtain model-checking procedures for rich subsets of Duration Calculus. Together with undecidability results also obtained, this sheds light upon the exact borderline between decidability and undecidability of Duration Calculi and related logics....
Methods to model-check parallel systems software.
Matlin, O. S.; McCune, W.; Lusk, E.
2003-12-15
We report on an effort to develop methodologies for formal verification of parts of the Multi-Purpose Daemon (MPD) parallel process management system. MPD is a distributed collection of communicating processes. While the individual components of the collection execute simple algorithms, their interaction leads to unexpected errors that are difficult to uncover by conventional means. Two verification approaches are discussed here: the standard model checking approach using the software model checker SPIN and the nonstandard use of a general-purpose first-order resolution-style theorem prover OTTER to conduct the traditional state space exploration. We compare modeling methodology and analyze performance and scalability of the two methods with respect to verification of MPD.
Analysis of DIRAC's behavior using model checking with process algebra
DIRAC is the grid solution developed to support LHCb production activities as well as user data analysis. It consists of distributed services and agents delivering the workload to the grid resources. Services maintain database back-ends to store dynamic state information of entities such as jobs, queues, staging requests, etc. Agents use polling to check and possibly react to changes in the system state. Each agent's logic is relatively simple; the main complexity lies in their cooperation. Agents run concurrently, and collaborate using the databases as shared memory. The databases can be accessed directly by the agents if running locally or through a DIRAC service interface if necessary. This shared-memory model causes entities to occasionally get into inconsistent states. Tracing and fixing such problems becomes formidable due to the inherent parallelism present. We propose more rigorous methods to cope with this. Model checking is one such technique for analysis of an abstract model of a system. Unlike conventional testing, it allows full control over the parallel processes execution, and supports exhaustive state-space exploration. We used the mCRL2 language and toolset to model the behavior of two related DIRAC subsystems: the workload and storage management system. Based on process algebra, mCRL2 allows defining custom data types as well as functions over these. This makes it suitable for modeling the data manipulations made by DIRAC's agents. By visualizing the state space and replaying scenarios with the toolkit's simulator, we have detected race-conditions and deadlocks in these systems, which, in several cases, were confirmed to occur in the reality. Several properties of interest were formulated and verified with the tool. Our future direction is automating the translation from DIRAC to a formal model.
Analysis of DIRAC's behavior using model checking with process algebra
Remenska, Daniela; Templon, Jeff; Willemse, Tim; Bal, Henri; Verstoep, Kees; Fokkink, Wan; Charpentier, Philippe; Graciani Diaz, Ricardo; Lanciotti, Elisa; Roiser, Stefan; Ciba, Krzysztof
2012-12-01
DIRAC is the grid solution developed to support LHCb production activities as well as user data analysis. It consists of distributed services and agents delivering the workload to the grid resources. Services maintain database back-ends to store dynamic state information of entities such as jobs, queues, staging requests, etc. Agents use polling to check and possibly react to changes in the system state. Each agent's logic is relatively simple; the main complexity lies in their cooperation. Agents run concurrently, and collaborate using the databases as shared memory. The databases can be accessed directly by the agents if running locally or through a DIRAC service interface if necessary. This shared-memory model causes entities to occasionally get into inconsistent states. Tracing and fixing such problems becomes formidable due to the inherent parallelism present. We propose more rigorous methods to cope with this. Model checking is one such technique for analysis of an abstract model of a system. Unlike conventional testing, it allows full control over the parallel processes execution, and supports exhaustive state-space exploration. We used the mCRL2 language and toolset to model the behavior of two related DIRAC subsystems: the workload and storage management system. Based on process algebra, mCRL2 allows defining custom data types as well as functions over these. This makes it suitable for modeling the data manipulations made by DIRAC's agents. By visualizing the state space and replaying scenarios with the toolkit's simulator, we have detected race-conditions and deadlocks in these systems, which, in several cases, were confirmed to occur in the reality. Several properties of interest were formulated and verified with the tool. Our future direction is automating the translation from DIRAC to a formal model.
Malekpour, Mahyar R.
2007-01-01
This report presents the mechanical verification of a simplified model of a rapid Byzantine-fault-tolerant self-stabilizing protocol for distributed clock synchronization systems. This protocol does not rely on any assumptions about the initial state of the system. This protocol tolerates bursts of transient failures, and deterministically converges within a time bound that is a linear function of the self-stabilization period. A simplified model of the protocol is verified using the Symbolic Model Verifier (SMV) [SMV]. The system under study consists of 4 nodes, where at most one of the nodes is assumed to be Byzantine faulty. The model checking effort is focused on verifying correctness of the simplified model of the protocol in the presence of a permanent Byzantine fault as well as confirmation of claims of determinism and linear convergence with respect to the self-stabilization period. Although model checking results of the simplified model of the protocol confirm the theoretical predictions, these results do not necessarily confirm that the protocol solves the general case of this problem. Modeling challenges of the protocol and the system are addressed. A number of abstractions are utilized in order to reduce the state space. Also, additional innovative state space reduction techniques are introduced that can be used in future verification efforts applied to this and other protocols.
Of Models and Machines: Implementing Bounded Rationality.
Dick, Stephanie
2015-09-01
This essay explores the early history of Herbert Simon's principle of bounded rationality in the context of his Artificial Intelligence research in the mid 1950s. It focuses in particular on how Simon and his colleagues at the RAND Corporation translated a model of human reasoning into a computer program, the Logic Theory Machine. They were motivated by a belief that computers and minds were the same kind of thing--namely, information-processing systems. The Logic Theory Machine program was a model of how people solved problems in elementary mathematical logic. However, in making this model actually run on their 1950s computer, the JOHNNIAC, Simon and his colleagues had to navigate many obstacles and material constraints quite foreign to the human experience of logic. They crafted new tools and engaged in new practices that accommodated the affordances of their machine, rather than reflecting the character of human cognition and its bounds. The essay argues that tracking this implementation effort shows that "internal" cognitive practices and "external" tools and materials are not so easily separated as they are in Simon's principle of bounded rationality--the latter often shaping the dynamics of the former. PMID:26685521
A conceptual model of check dam hydraulics for gully control
C. Castillo
2013-09-01
Full Text Available There is little information in scientific literature regarding the modifications induced by check dam systems in flow regimes in restored gully reaches, despite it being a crucial issue for the design of conservation measures. Here, we develop a conceptual model to classify flow regimes in straight rectangular channels for initial and dam-filling conditions as well as a method of estimating efficiency in order to provide guidelines for optimal design. The model integrates several previous mathematical approaches for assessing the main processes involved (hydraulic jump HJ, impact flow, gradually varied flows. Its performance was compared with the simulations obtained from IBER, a bi-dimensional hydrodynamic model. The impact of check dam spacing (defined by the geometric factor of influence c on efficiency was explored. Eleven main classifications of flow regimes were identified depending on the element and level of influence. The model produced similar results when compared with IBER, but led to higher estimations of HJ and impact lengths. Total influence guaranteed maximum efficiency and HJ control defining the location of the optimal c. Geometric total influence (c = 1 was a valid criterion for the different stages of the structures in a wide range of situations provided that hydraulic roughness conditions remained high within the gully, e.g. through revegetation. Our total influence criterion involved shorter spacing than that habitually recommended in technical manuals for restoration, but was in line with those values found in spontaneous and stable step-pools systems, which might serve as a reference for man-made interventions.
Take it NP-easy: Bounded model construction for duration calculus
Fränzle, Martin
Following the recent successes of bounded model-checking, we reconsider the problem of constructing models of discrete-time Duration Calculus formulae. While this problem is known to be non-elementary when arbitrary length models are considered [Hansen94], it turns out to be only NP-complete when...... constrained to bounded length. As a corollary we obtain that model construction is in NP for the formulae actually encountered in case studies using Duration Calculus, as these have a certain small-model property. First experiments with a prototype implementation of the procedures demonstrate a competitive...
Valuation models and Simon's bounded rationality
Alexandra Strommer de Farias Godoi
2009-09-01
Full Text Available This paper aims at reconciling the evidence that sophisticated valuation models are increasingly used by companies in their investment appraisal with the literature of bounded rationality, according to which objective optimization is impracticable in the real world because it would demand an immense level of sophistication of the analytical and computational processes of human beings. We show how normative valuation models should rather be viewed as forms of reality representation, frameworks according to which the real world is perceived, fragmented for a better understanding, and recomposed, providing an orderly method for undertaking a task as complex as the investment decision.
Combining Decision Diagrams and SAT Procedures for Efficient Symbolic Model Checking
Williams, Poul Frederick; Biere, Armin; Clarke, Edmund M.;
2000-01-01
, combined with BDDs and SAT-solvers to perform satisfiability checking. As a result we are able to model check systems for which standard BDD-based methods fail. For example, we model check a liveness property of a 256 bit shift-and-add multiplier and we are able to find a previously undetected bug...
A Succinct Approach to Static Analysis and Model Checking
Filipiuk, Piotr
In a number of areas software correctness is crucial, therefore it is often desirable to formally verify the presence of various properties or the absence of errors. This thesis presents a framework for concisely expressing static analysis and model checking problems. The framework facilitates...... guarantees that there always is single best solution for a problem under consideration. We also develop a solving algorithm, based on a dierential worklist, that computes the least solution guaranteed by the Moore Family result. Furthermore, we present a logic for specifying analysis problems called Layered...... Fixed Point Logic. Its most prominent feature is the direct support for both inductive computations of behaviors as well as co-inductive specications of properties. Two main theoretical contributions are a Moore Family result and a parametrized worst-case time complexity result. We develop a BDD...
Analysis of the Security of BB84 by Model Checking
Elboukhari, Mohamed; Azizi, Abdelmalek; 10.5121/ijnsa.2010.2207
2010-01-01
Quantum Cryptography or Quantum key distribution (QKD) is a technique that allows the secure distribution of a bit string, used as key in cryptographic protocols. When it was noted that quantum computers could break public key cryptosystems based on number theory extensive studies have been undertaken on QKD. Based on quantum mechanics, QKD offers unconditionally secure communication. Now, the progress of research in this field allows the anticipation of QKD to be available outside of laboratories within the next few years. Efforts are made to improve the performance and reliability of the implemented technologies. But several challenges remain despite this big progress. The task of how to test the apparatuses of QKD For example did not yet receive enough attention. These devises become complex and demand a big verification effort. In this paper we are interested in an approach based on the technique of probabilistic model checking for studying quantum information. Precisely, we use the PRISM tool to analyze ...
Analysis of the Security of BB84 by Model Checking
Mohamed Elboukhari
2010-04-01
Full Text Available Quantum Cryptography or Quantum key distribution (QKD is a technique that allows the secure distribution of a bit string, used as key in cryptographic protocols. When it was noted that quantum computers could break public key cryptosystems based on number theory extensive studies have been undertaken on QKD. Based on quantum mechanics, QKD offers unconditionally secure communication. Now, the progress of research in this field allows the anticipation of QKD to be available outside of laboratories within the next few years. Efforts are made to improve the performance and reliability of the implemented technologies. But several challenges remain despite this big progress. The task of how to test the apparatuses of QKD For example did not yet receive enough attention. These devises become complex and demand a big verification effort. In this paper we are interested in an approach based on the technique of probabilistic model checking for studying quantum information. Precisely, we use the PRISM tool to analyze the security of BB84 protocol and we are focused on the specific security property of eavesdropping detection. We show that this property is affected by the parameters of quantum channel and the power of eavesdropper
Optimisation of BPMN Business Models via Model Checking
Herbert, Luke Thomas; Sharp, Robin
2013-01-01
synthesized BPMN components, based on probabilistic computation tree logic and real-valued reward structures of the BPMN model, allowing for the specification of complex quantitative goals. We here present a simple algorithm, inspired by concepts from evolutionary algorithms, which iteratively generates...
Model Checking of a Diabetes-Cancer Model
Gong, Haijun; Zuliani, Paolo; Clarke, Edmund M.
2011-06-01
Accumulating evidence suggests that cancer incidence might be associated with diabetes mellitus, especially Type II diabetes which is characterized by hyperinsulinaemia, hyperglycaemia, obesity, and overexpression of multiple WNT pathway components. These diabetes risk factors can activate a number of signaling pathways that are important in the development of different cancers. To systematically understand the signaling components that link diabetes and cancer risk, we have constructed a single-cell, Boolean network model by integrating the signaling pathways that are influenced by these risk factors to study insulin resistance, cancer cell proliferation and apoptosis. Then, we introduce and apply the Symbolic Model Verifier (SMV), a formal verification tool, to qualitatively study some temporal logic properties of our diabetes-cancer model. The verification results show that the diabetes risk factors might not increase cancer risk in normal cells, but they will promote cell proliferation if the cell is in a precancerous or cancerous stage characterized by losses of the tumor-suppressor proteins ARF and INK4a.
Using Stochastic Model Checking to Provision Complex Business Services
Herbert, Luke Thomas; Sharp, Robin
2012-01-01
We present a framework for modelling and analysis of real-world business workflows. Business processes regularly form the basis for the design of software services, and frequently display complex stochastic behaviour. The accurate evaluation of their qualitative aspects can allow for determining ...... of business processes including transient probabilities, timing, occurrence and ordering of events, and best- and worst-case scenarios. The developments presented are illustrated using an example from the health-care industry.......We present a framework for modelling and analysis of real-world business workflows. Business processes regularly form the basis for the design of software services, and frequently display complex stochastic behaviour. The accurate evaluation of their qualitative aspects can allow for determining...... bounds on resources consumed during execution of business processes. Accurate resource provisioning is often central to ensuring the safe execution of a process. We first introduce a formalised core subset of the Business Process Modelling and Notation (BPMN), which we extend with probabilistic and non...
The Modeling Library of Eavesdropping Methods in Quantum Cryptography Protocols by Model Checking
Yang, Fan; Yang, Guowu; Hao, Yujie
2016-07-01
The most crucial issue of quantum cryptography protocols is its security. There exists many ways to attack the quantum communication process. In this paper, we present a model checking method for modeling the eavesdropping in quantum information protocols. So when the security properties of a certain protocol are needed to be verified, we can directly use the models which are already built. Here we adopt the probabilistic model checking tool—PRISM to model these attack methods. The verification results show that the detection rate of eavesdropping is approximately close to 1 when enough photons are transmitted.
The Modeling Library of Eavesdropping Methods in Quantum Cryptography Protocols by Model Checking
Yang, Fan; Yang, Guowu; Hao, Yujie
2016-03-01
The most crucial issue of quantum cryptography protocols is its security. There exists many ways to attack the quantum communication process. In this paper, we present a model checking method for modeling the eavesdropping in quantum information protocols. So when the security properties of a certain protocol are needed to be verified, we can directly use the models which are already built. Here we adopt the probabilistic model checking tool—PRISM to model these attack methods. The verification results show that the detection rate of eavesdropping is approximately close to 1 when enough photons are transmitted.
The Complexity of Model Checking Higher-Order Fixpoint Logic
Axelsson, Roland; Lange, Martin; Somla, Rafal
2007-01-01
Higher Order Fixpoint Logic (HFL) is a hybrid of the simply typed λ-calculus and the modal μ-calculus. This makes it a highly expressive temporal logic that is capable of expressing various interesting correctness properties of programs that are not expressible in the modal μ-calculus. This paper...... of solving rather large parity games of small index. As a consequence of this we obtain an ExpTime upper bound on the expression complexity of each HFLk,m. The lower bound is established by a reduction from the word problem for alternating (k-1)-fold exponential space bounded Turing Machines. As a...
Family-Based Model Checking Without a Family-Based Model Checker
Dimovski, Aleksandar; Al-Sibahi, Ahmad Salim; Brabrand, Claus; Wasowski, Andrzej
Many software systems are variational: they can be configured to meet diverse sets of requirements. Variability is found in both communication protocols and discrete controllers of embedded systems. In these areas, model checking is an important verification technique. For variational models...
PVeStA: A Parallel Statistical Model Checking and Quantitative Analysis Tool
AlTurki, Musab
2011-01-01
Statistical model checking is an attractive formal analysis method for probabilistic systems such as, for example, cyber-physical systems which are often probabilistic in nature. This paper is about drastically increasing the scalability of statistical model checking, and making such scalability of analysis available to tools like Maude, where probabilistic systems can be specified at a high level as probabilistic rewrite theories. It presents PVeStA, an extension and parallelization of the VeStA statistical model checking tool [10]. PVeStA supports statistical model checking of probabilistic real-time systems specified as either: (i) discrete or continuous Markov Chains; or (ii) probabilistic rewrite theories in Maude. Furthermore, the properties that it can model check can be expressed in either: (i) PCTL/CSL, or (ii) the QuaTEx quantitative temporal logic. As our experiments show, the performance gains obtained from parallelization can be very high. © 2011 Springer-Verlag.
Model checking and strategy synthesis for stochastic games: from theory to practice
Kwiatkowska, MZ
2016-01-01
Probabilistic model checking is an automatic procedure for establishing if a desired property holds in a probabilistic model, aimed at verifying quantitative probabilistic specifications such as the probability of a critical failure occurring or expected time to termination. Much progress has been made in recent years in algorithms, tools and applications of probabilistic model checking, as exemplified by the probabilistic model checker PRISM (www.prismmodelchecker.org). However, the unstoppa...
Checking Fine and Gray Subdistribution Hazards Model with Cumulative Sums of Residuals
Li, Jianing; Scheike, Thomas H.; Zhang, Mei-Jie
2014-01-01
Recently, Fine and Gray (1999) proposed a semi-parametric proportional regression model for the subdistribution hazard function which has been used extensively for analyzing competing risks data. However, failure of model adequacy could lead to severe bias in parameter estimation, and only a limited contribution has been made to check the model assumptions. In this paper, we present a class of analytical methods and graphical approaches for checking the assumptions of Fine and Gray’s model. T...
A logic for model-checking of mean-field models
Kolesnichenko, Anna; Remke, Anne; Boer, de, J.W.; Haverkort, Boudewijn R.
2012-01-01
Recently, many systems consisting of a large number of interacting objects were analysed using the mean-field method, which has only been used for performance evaluation. In this short paper, we apply it to model checking. We define logic, which allows to describe the overall properties of the large system.
Lower bounds in the quantum cell probe model
Sen, Pranab; Venkatesh, S.
2001-01-01
We introduce a new model for studying quantum data structure problems -- the "quantum cell probe model". We prove a lower bound for the static predecessor problem in the address-only version of this model where we allow quantum parallelism only over the `address lines' of the queries. The address-only quantum cell probe model subsumes the classical cell probe model, and many quantum query algorithms like Grover's algorithm fall into this framework. Our lower bound improves the previous known ...
Development of a butterfly check valve model under natural circulation conditions
Highlights: • Bases on Lim’s swing check valve model, a butterfly check valve model was developed. • The method to quantify the friction torque TF in Li’s model was corrected. • The developed model was implemented into the RELAP5 code and verified. - Abstract: A butterfly check valve is widely used to prevent a reverse flow in the pipe lines of a marine nuclear power plant. Under some conditions, the natural circulation conditions in particular, the fluid velocity through the butterfly check valve might become too low to hold the valve disk fully open, thereby the flow resistance of the butterfly check valve varies with the location of the valve disk and as a result the fluid flow is significantly affected by the dynamic motion of the valve disk. Simulation of a pipe line that includes some butterfly check valves, especially under natural circulation conditions, is thus complicated. This paper focuses on the development of a butterfly check valve model to enhance the capability of the thermal–hydraulic system code and the developed model is implemented into the RELAP5 code. Both steady-state calculations and transient calculations were carried out for the primary loop system of a marine nuclear power plant and the calculation results are compared with the experimental data for verification purpose. The simulation results show an agreement with the experimental data
LHCb: Analysing DIRAC's Behavior using Model Checking with Process Algebra
Remenska, Daniela
2012-01-01
DIRAC is the Grid solution designed to support LHCb production activities as well as user data analysis. Based on a service-oriented architecture, DIRAC consists of many cooperating distributed services and agents delivering the workload to the Grid resources. Services accept requests from agents and running jobs, while agents run as light-weight components, fulfilling specific goals. Services maintain database back-ends to store dynamic state information of entities such as jobs, queues, staging requests, etc. Agents use polling to check for changes in the service states, and react to these accordingly. A characteristic of DIRAC's architecture is the relatively low complexity in the logic of each agent; the main source of complexity lies in their cooperation. These agents run concurrently, and communicate using the services' databases as a shared memory for synchronizing the state transitions. Although much effort is invested in making DIRAC reliable, entities occasionally get into inconsistent states, leadi...
Checking the new IRI model The bottomside B parameters
Mosert, M; Ezquer, R; Lazo, B; Miro, G
2002-01-01
Electron density profiles obtained at Pruhonice (50.0, 15.0), El Arenosillo (37.1, 353.2) and Havana (23, 278) were used to check the bottom-side B parameters BO (thickness parameter) and B1 (shape parameter) predicted by the new IRI - 2000 version. The electron density profiles were derived from ionograms using the ARP technique. The data base includes daytime and nighttime ionograms recorded under different seasonal and solar activity conditions. Comparisons with IRI predictions were also done. The analysis shows that: a) The parameter B1 given by IRI 2000 reproduces better the observed ARP values than the IRI-90 version and b) The observed BO values are in general well reproduced by both IRI versions: IRI-90 and IRI-2000.
A branch-and-bound methodology within algebraic modelling systems
Bisschop, J.J.; Heerink, J.B.J.; Kloosterman, G.
1998-01-01
Through the use of application-specific branch-and-bound directives it is possible to find solutions to combinatorial models that would otherwise be difficult or impossible to find by just using generic branch-and-bound techniques within the framework of mathematical programming. {\\sc Minto} is an example of a system which offers the possibility to incorporate user-provided directives (written in {\\sc C}) to guide the branch-and-bound search. Its main focus, however, remains on mathematical p...
Model Checking of Software Components: Combining Java PathFinder and Behavior Protocol Model Checker
Pařízek, P.; Plášil, František; Kofroň, Jan
Los Alamitos: IEEE Computer Society, 2006, s. 133-141. ISBN 0-7695-2624-1. [SEW 2006. Annual IEEE/NASA Software Engineering Workshop /30./. Loyola College Graduate Center, Columbia (US), 24.04.2006-28.04.2006] R&D Projects: GA ČR GA201/06/0770 Institutional research plan: CEZ:AV0Z10300504 Keywords : software components * behavior protocols * model checking * cooperation of model checkers Subject RIV: JC - Computer Hardware ; Software
An Approach to Checking 3D Model with Related Engineering Drawings
无
2002-01-01
For some reasons, engineers build their product 3D mo del according to a set of related engineering drawings. The problem is how we ca n know the 3D model is correct. The manual checking is very boring and time cons uming, and still could not avoid mistakes. Thus, we could not confirm the model, maybe try checking again. It will effect the production preparing cycle greatly , and should be solved in a intelligent way. The difficulties are quite obvious, unlike word checking in a word processing package, ...
Efficient model checking for duration calculus based on branching-time approximations
Fränzle, Martin; Hansen, Michael Reichhardt
2008-01-01
Duration Calculus (abbreviated to DC) is an interval-based, metric-time temporal logic designed for reasoning about embedded real-time systems at a high level of abstraction. But the complexity of model checking any decidable fragment featuring both negation and chop, DC's only modality, is non......-elementary and thus impractical. We here investigate a similar approximation as frequently employed in model checking situation-based temporal logics, where linear-time problems are safely approximated by branching-time counterparts amenable to more efficient model-checking algorithms. Mimicking the role that a...... situation has in (A)CTL as origin of a set of linear traces, we define a branching-time counterpart to interval-based temporal logics building on situation pairs spanning sets of intervals. While this branching-time interval semantics yields the desired reduction in complexity of the model-checking problem...
Efficient Symmetry Reduction and the Use of State Symmetries for Symbolic Model Checking
Christian Appold
2010-06-01
Full Text Available One technique to reduce the state-space explosion problem in temporal logic model checking is symmetry reduction. The combination of symmetry reduction and symbolic model checking by using BDDs suffered a long time from the prohibitively large BDD for the orbit relation. Dynamic symmetry reduction calculates representatives of equivalence classes of states dynamically and thus avoids the construction of the orbit relation. In this paper, we present a new efficient model checking algorithm based on dynamic symmetry reduction. Our experiments show that the algorithm is very fast and allows the verification of larger systems. We additionally implemented the use of state symmetries for symbolic symmetry reduction. To our knowledge we are the first who investigated state symmetries in combination with BDD based symbolic model checking.
Validation of mission critical software design and implementation using model checking
Pingree, P. J.; Mikk, E.; Holzmann, G.; Smith, M.; Dams, D.
2002-01-01
Model Checking conducts an exhaustive exploration of all possible behaviors of a software system design and as such can be used to detect defects in designs that are typically difficult to discover with conventional testing approaches.
Deterministic Compilation of Temporal Safety Properties in Explicit State Model Checking
National Aeronautics and Space Administration — The translation of temporal logic specifications constitutes an essen- tial step in model checking and a major influence on the efficiency of formal verification...
Towards Symbolic Model Checking for Multi-Agent Systems via OBDDs
Raimondi, Franco; Lomunscio, Alessio
2004-01-01
We present an algorithm for model checking temporal-epistemic properties of multi-agent systems, expressed in the formalism of interpreted systems. We first introduce a technique for the translation of interpreted systems into boolean formulae, and then present a model-checking algorithm based on this translation. The algorithm is based on OBDD's, as they offer a compact and efficient representation for boolean formulae.
Phase Two Feasibility Study for Software Safety Requirements Analysis Using Model Checking
Turgeon, Gregory; Price, Petra
2010-01-01
A feasibility study was performed on a representative aerospace system to determine the following: (1) the benefits and limitations to using SCADE , a commercially available tool for model checking, in comparison to using a proprietary tool that was studied previously [1] and (2) metrics for performing the model checking and for assessing the findings. This study was performed independently of the development task by a group unfamiliar with the system, providing a fresh, external perspective free from development bias.
Lahtinen, J. [VTT Technical Research Centre of Finland, Espoo (Finland); Launiainen, T.; Heljanko, K.; Ropponen, J. [Aalto Univ., Espoo (Finland). Dept. of Information and Computer Science
2012-07-01
Digital instrumentation and control (I and C) systems are challenging to verify. They enable complicated control functions, and the state spaces of the models easily become too large for comprehensive verification through traditional methods. Model checking is a formal method that can be used for system verification. A number of efficient model checking systems are available that provide analysis tools to determine automatically whether a given state machine model satisfies the desired safety properties. This report reviews the work performed in the Safety Evaluation and Reliability Analysis of Nuclear Automation (SARANA) project in 2011 regarding model checking. We have developed new, more exact modelling methods that are able to capture the behaviour of a system more realistically. In particular, we have developed more detailed fault models depicting the hardware configuration of a system, and methodology to model function-block-based systems asynchronously. In order to improve the usability of our model checking methods, we have developed an algorithm for model checking large modular systems. The algorithm can be used to verify properties of a model that could otherwise not be verified in a straightforward manner. (orig.)
Verifying Real-time Commit Protocols Using Dense-time Model Checking Technology
Al-Bataineh, Omar I.; Reynolds, Mark; French, Tim; Woodings, Terry
2012-01-01
The timed-based automata model, introduced by Alur and Dill, provides a useful formalism for describing real-time systems. Over the last two decades, several dense-time model checking tools have been developed based on that model. The paper considers the verification of real-time distributed commit protocols using dense-time model checking technology. More precisely, we model and verify the well-known timed two phase commit protocol in three different state-of-the-art real-time model checkers...
Verifying Real-time Commit Protocols Using Dense-time Model Checking Technology
Al-Bataineh, Omar I; French, Tim; Woodings, Terry
2012-01-01
The timed-based automata model, introduced by Alur and Dill, provides a useful formalism for describing real-time systems. Over the last two decades, several dense-time model checking tools have been developed based on that model. The paper considers the verification of real-time distributed commit protocols using dense-time model checking technology. More precisely, we model and verify the well-known timed two phase commit protocol in three different state-of-the-art real-time model checkers: UPPAAL, Rabbit, and RED, and compare the results.
PKreport: report generation for checking population pharmacokinetic model assumptions
Li Jun
2011-05-01
Full Text Available Abstract Background Graphics play an important and unique role in population pharmacokinetic (PopPK model building by exploring hidden structure among data before modeling, evaluating model fit, and validating results after modeling. Results The work described in this paper is about a new R package called PKreport, which is able to generate a collection of plots and statistics for testing model assumptions, visualizing data and diagnosing models. The metric system is utilized as the currency for communicating between data sets and the package to generate special-purpose plots. It provides ways to match output from diverse software such as NONMEM, Monolix, R nlme package, etc. The package is implemented with S4 class hierarchy, and offers an efficient way to access the output from NONMEM 7. The final reports take advantage of the web browser as user interface to manage and visualize plots. Conclusions PKreport provides 1 a flexible and efficient R class to store and retrieve NONMEM 7 output, 2 automate plots for users to visualize data and models, 3 automatically generated R scripts that are used to create the plots; 4 an archive-oriented management tool for users to store, retrieve and modify figures, 5 high-quality graphs based on the R packages, lattice and ggplot2. The general architecture, running environment and statistical methods can be readily extended with R class hierarchy. PKreport is free to download at http://cran.r-project.org/web/packages/PKreport/index.html.
Model-Checking Real-Time Control Programs
Iversen, T. K.; Kristoffersen, K. J.; Larsen, Kim Guldstrand; Laursen, M.; Madsen, R. G.; Mortensen, S. K.; Pettersson, P.; Thomasen, C. B.
In this paper, we present a method for automatic verification of real-time control programs running on LEGO(R) RCX(TM) bricks using the verification tool UPPALL. The control programs, consisting of a number of tasks running concurrently, are automatically translated into the mixed automata model of...... UPPAAL. The fixed scheduling algorithm used by the LEGO(R) RCX(TM) processor is modeled in UPPALL, and supply of similar (sufficient) timed automata models for the environment allows analysis of the overall real-time system using the tools of UPPALL. To illustrate our technique for sorting LEGO(R) bricks...
Cosmological bounds on oscillating dark energy models
We study the cosmological constraints on the two purely phenomenological models of oscillating dark energy. In these oscillating models, the equation of state of dark energy varies periodically. The periodic equation of state may provide the natural way to unify the early acceleration (inflation) and the late time acceleration of the Universe. These models give the effective way to tackle the cosmic coincidence problem. We examine the observational constraints on the oscillatory models from the latest observational data including the gold sample of 182 SNe type Ia, the shift parameter, R, given by the WMAP and the BAO measurements from the SDSS
Practical Application of Model Checking in Software Verification
Havelund, Klaus; Skakkebaek, Jens Ulrik
1999-01-01
This paper presents our experiences in applying the JAVA PATHFINDER (J(sub PF)), a recently developed JAVA to SPIN translator, in the finding of synchronization bugs in a Chinese Chess game server application written in JAVA. We give an overview of J(sub PF) and the subset of JAVA that it supports and describe the abstraction and verification of the game server. Finally, we analyze the results of the effort. We argue that abstraction by under-approximation is necessary for abstracting sufficiently smaller models for verification purposes; that user guidance is crucial for effective abstraction; and that current model checkers do not conveniently support the computational models of software in general and JAVA in particular.
Application of Model-Checking Technology to Controller Synthesis
David, Alexandre; Grunnet, Jacob Deleuran; Jessen, Jan Jacob;
2011-01-01
its continuous environment, which is modelled and taken care of in our frameworks. Our first technique does it by using Matlab to discretise the problem and then Uppaal-tiga to solve the obtained timed game. This is implemented as a toolbox. The second technique relies on the user defining a timed...... game model in Uppaal- tiga. Then the strategy is automatically imported in Simulink as an S-function for simulation and validation purposes. We demonstrate the effectiveness of these frameworks in different case-studies....
Model Checking Electronic Commerce Security Protocols Based on CTL
XIAO De-qin; ZHANG Huan-guo
2005-01-01
We present a model based on Computational Temporal Logic (CTL) methods for verifying security requirements of electronic commerce protocols. The model describes formally the authentication, confidentiality integrity,non-repudiation, denial of service and access control of the electronic commerce protocols. We illustrate as case study a variant of the Lu-Smolka protocol proposed by Lu-Smolka.Moreover, we have discovered two attacks that allow a dishonest user to purchase a good debiting the amount to another user. And also, we compared our work with relative research works and found that the formal way of this paper is more general to specify security protocols for E-Commerce.
VERIFICATION OF CONFLICTION AND UNREACHABILITY IN RULE-BASED EXPERT SYSTEMS WITH MODEL CHECKING
Einollah pira
2014-03-01
Full Text Available It is important to find optimal solutions for structural errors in rule-based expert systems .Solutions to discovering such errors by using model checking techniques have already been proposed, but these solutions have problems such as state space explosion. In this paper, to overcome these problems, we model the rule-based systems as finite state transition systems and express confliction and unreachabilityas Computation Tree Logic (CTL logic formula and then use the technique of model checking to detect confliction and unreachability in rule-based systems with the model checker UPPAAL.
Vulnerable Derivatives and Good Deal Bounds: A Structural Model
Murgoci, Agatha
2013-01-01
new restriction in the arbitrage free model by setting upper bounds on the Sharpe ratios (SRs) of the assets. The potential prices that are eliminated represent unreasonably good deals. The constraint on the SR translates into a constraint on the stochastic discount factor. Thus, tight pricing bounds...... can be obtained. We provide a link between the objective probability measure and the range of potential risk-neutral measures, which has an intuitive economic meaning. We also provide tight pricing bounds for European calls and show how to extend the call formula to pricing other financial products in...
Hypersonic: Model Analysis and Checking in the Cloud
Acretoaie, Vlad; Störrle, Harald
2014-01-01
”. Objective: In this paper we investigate the conceptual and technical feasibility of a new software architecture for modeling tools, where certain advanced features are factored out of the client and moved towards the Cloud. With this approach we plan to address the above mentioned drawbacks of existing...
Membrane Matrix models and non-perturbative checks of gauge/gravity duality
O'Connor, Denjoe
2016-01-01
We compare the bosonic and maximally supersymmetric membrane models. We find that in Hoppe regulated form the bosonic membrane is well approximated by massive Gaussian quantum matrix models. In contrast the similarly regulated supersymmetric membrane, which is equivalent to the BFSS model, has a gravity dual description. We sketch recent progress in checking gauge/gravity duality in this context.
Using Runtime Analysis to Guide Model Checking of Java Programs
Havelund, Klaus; Norvig, Peter (Technical Monitor)
2001-01-01
This paper describes how two runtime analysis algorithms, an existing data race detection algorithm and a new deadlock detection algorithm, have been implemented to analyze Java programs. Runtime analysis is based on the idea of executing the program once. and observing the generated run to extract various kinds of information. This information can then be used to predict whether other different runs may violate some properties of interest, in addition of course to demonstrate whether the generated run itself violates such properties. These runtime analyses can be performed stand-alone to generate a set of warnings. It is furthermore demonstrated how these warnings can be used to guide a model checker, thereby reducing the search space. The described techniques have been implemented in the b e grown Java model checker called PathFinder.
Optimizing algebraic petri net model checking by slicing
Khan, Yasir Imtiaz; Risoldi, Matteo
2013-01-01
High-level Petri nets make models more concise and read- able as compared to low-level Petri nets. However, usual verification techniques such as state space analysis remain an open challenge for both because of state space explosion. The contribution of this paper is to propose an approach for property based reduction of the state space of Algebraic Petri nets (a variant of high-level Petri nets). To achieve the objective, we propose a slicing algorithm for Algebraic Petri ...
Model Checking of E-Commerce Protocol using Casper FDR
Dantuluri Sravanthi
2013-01-01
In present days the popularity of electronic commerce applications are motivated the development of new e-commerce protocols. By using these new protocols the secrecy and agreement properties are achieved. This paper mainly focuses on how to model the e-commerce protocol in CSP using SPL and verified using CasperFDR whether the protocol satisfies the properties specified. Attacks are identified in this version. The specifications through which these attacks are found are presented.
Numerical modelling of granular flows: a reality check
Windows-Yule, C. R. K.; Tunuguntla, D. R.; Parker, D. J.
2016-07-01
Discrete particle simulations provide a powerful tool for the advancement of our understanding of granular media, and the development and refinement of the multitudinous techniques used to handle and process these ubiquitous materials. However, in order to ensure that this tool can be successfully utilised in a meaningful and reliable manner, it is of paramount importance that we fully understand the degree to which numerical models can be trusted to accurately and quantitatively recreate and predict the behaviours of the real-world systems they are designed to emulate. Due to the complexity and diverse variety of physical states and dynamical behaviours exhibited by granular media, a simulation algorithm capable of closely reproducing the behaviours of a given system may be entirely unsuitable for other systems with different physical properties, or even similar systems exposed to differing control parameters. In this paper, we focus on two widely used forms of granular flow, for which discrete particle simulations are shown to provide a full, quantitative replication of the behaviours of real industrial and experimental systems. We identify also situations for which quantitative agreement may fail are identified, but important general, qualitative trends are still recreated, as well as cases for which computational models are entirely unsuitable. By assembling this information into a single document, we hope not only to provide researchers with a useful point of reference when designing and executing future studies, but also to equip those involved in the design of simulation algorithms with a clear picture of the current strengths and shortcomings of contemporary models, and hence an improved knowledge of the most valuable areas on which to focus their work.
Numerical modelling of granular flows: a reality check
Windows-Yule, C. R. K.; Tunuguntla, D. R.; Parker, D. J.
2015-12-01
Discrete particle simulations provide a powerful tool for the advancement of our understanding of granular media, and the development and refinement of the multitudinous techniques used to handle and process these ubiquitous materials. However, in order to ensure that this tool can be successfully utilised in a meaningful and reliable manner, it is of paramount importance that we fully understand the degree to which numerical models can be trusted to accurately and quantitatively recreate and predict the behaviours of the real-world systems they are designed to emulate. Due to the complexity and diverse variety of physical states and dynamical behaviours exhibited by granular media, a simulation algorithm capable of closely reproducing the behaviours of a given system may be entirely unsuitable for other systems with different physical properties, or even similar systems exposed to differing control parameters. In this paper, we focus on two widely used forms of granular flow, for which discrete particle simulations are shown to provide a full, quantitative replication of the behaviours of real industrial and experimental systems. We identify also situations for which quantitative agreement may fail are identified, but important general, qualitative trends are still recreated, as well as cases for which computational models are entirely unsuitable. By assembling this information into a single document, we hope not only to provide researchers with a useful point of reference when designing and executing future studies, but also to equip those involved in the design of simulation algorithms with a clear picture of the current strengths and shortcomings of contemporary models, and hence an improved knowledge of the most valuable areas on which to focus their work.
A Check-up for the Statistical Parton Model
Buccella, Franco
2014-01-01
We compare the parton distributions deduced in the framework of a quantum statistical approach for both the longitudinal and transverse degrees of freedom with the unpolarized distributions measured at Hera and with the polarized ones proposed in a previous paper, which have been shown to be in very good agreement also with the results of experiments performed after that proposal. The agreement with Hera data in correspondence of very similar values for the 'temperature' and the 'potentials' found in the previous work gives a robust confirm of the statistical model. The feature of describing both unpolarized and polarized parton distributions in terms of few parameters fixed by data with large statistics and small systematic errors makes very attractive the parametrization proposed here.
A check-up for the statistical Parton model
Buccella, Franco; Sohaily, Sozha
2015-11-01
We compare the Parton distributions deduced in the framework of a quantum statistical approach for both the longitudinal and transverse degrees of freedom with the unpolarized distributions measured at HERA and with the polarized ones proposed in a previous paper, which have been shown to be in very good agreement also with the results of experiments performed after that proposal. The agreement with HERA data in correspondence to very similar values for the “temperature” and the “potentials” found in the previous work gives a robust confirm of the statistical model. The unpolarized distributions are compared also with the result of NNPDF. The free parameters are fixed mainly by data in the range (0.1, 0.5) for the x variable, where the valence Partons dominate, and in the small x region for the diffractive contribution. This feature makes the parametrization proposed here very attractive.
Prototype of Automated PLC Model Checking Using Continuous Integration Tools
Lettrich, Michael
2015-01-01
To deal with the complexity of operating and supervising large scale industrial installations at CERN, often Programmable Logic Controllers (PLCs) are used. A failure in these control systems can cause a disaster in terms of economic loses, environmental damages or human losses. Therefore the requirements to software quality are very high. To provide PLC developers with a way to verify proper functionality against requirements, a Java tool named PLCverif has been developed which encapsulates and thus simplifies the use of third party model checkers. One of our goals in this project is to integrate PLCverif in development process of PLC programs. When the developer changes the program, all the requirements should be verified again, as a change on the code can produce collateral effects and violate one or more requirements. For that reason, PLCverif has been extended to work with Jenkins CI in order to trigger automatically the verication cases when the developer changes the PLC program. This prototype has been...
Cascading Verification: An Integrated Method for Domain-Specific Model Checking
Zervoudakis, F.
2014-01-01
Model checking is an established formal method for verifying the desired behavioral properties of system models. But popular model checkers tend to support low-level modeling languages that require intricate models to represent even the simplest systems. Modeling complexity arises in part from the need to encode domain knowledge, including domain objects and concepts, and their relationships, at relatively low levels of abstraction. We will demonstrate that, once formalized, domain knowledge ...
Model Checking Real Time Java Using Java PathFinder
Lindstrom, Gary; Mehlitz, Peter C.; Visser, Willem
2005-01-01
The Real Time Specification for Java (RTSJ) is an augmentation of Java for real time applications of various degrees of hardness. The central features of RTSJ are real time threads; user defined schedulers; asynchronous events, handlers, and control transfers; a priority inheritance based default scheduler; non-heap memory areas such as immortal and scoped, and non-heap real time threads whose execution is not impeded by garbage collection. The Robust Software Systems group at NASA Ames Research Center has JAVA PATHFINDER (JPF) under development, a Java model checker. JPF at its core is a state exploring JVM which can examine alternative paths in a Java program (e.g., via backtracking) by trying all nondeterministic choices, including thread scheduling order. This paper describes our implementation of an RTSJ profile (subset) in JPF, including requirements, design decisions, and current implementation status. Two examples are analyzed: jobs on a multiprogramming operating system, and a complex resource contention example involving autonomous vehicles crossing an intersection. The utility of JPF in finding logic and timing errors is illustrated, and the remaining challenges in supporting all of RTSJ are assessed.
Gamble, Ed; Holzmann, Gerard
2011-01-01
Part of the US DOT investigation of Toyota SUA involved analysis of the throttle control software. JPL LaRS applied several techniques, including static analysis and logic model checking, to the software. A handful of logic models were built. Some weaknesses were identified; however, no cause for SUA was found. The full NASA report includes numerous other analyses
Requirements-level semantics and model checking of object-oriented statecharts
Eshuis, Rik; Jansen, David N.; Wieringa, Roel
2002-01-01
In this paper we define a requirements-level execution semantics for object-oriented statecharts and show how properties of a system specified by these statecharts can be model checked using tool support for model checkers. Our execution semantics is requirements-level because it uses the perfect te
Random Testing and Model Checking: Building a Common Framework for Nondeterministic Exploration
Groce, Alex; Joshi, Rajeev
2008-01-01
Two popular forms of dynamic analysis, random testing and explicit-state software model checking, are perhaps best viewed as search strategies for exploring the state spaces introduced by nondeterminism in program inputs. We present an approach that enables this nondeterminism to be expressed in the SPIN model checker's PROMELA language, and then lets users generate either model checkers or random testers from a single harness for a tested C program. Our approach makes it easy to compare model checking and random testing for models with precisely the same input ranges and probabilities and allows us to mix random testing with model checking's exhaustive exploration of non-determinism. The PROMELA language, as intended in its design, serves as a convenient notation for expressing nondeterminism and mixing random choices with nondeterministic choices. We present and discuss a comparison of random testing and model checking. The results derive from using our framework to test a C program with an effectively infinite state space, a module in JPL's next Mars rover mission. More generally, we show how the ability of the SPIN model checker to call C code can be used to extend SPIN's features, and hope to inspire others to use the same methods to implement dynamic analyses that can make use of efficient state storage, matching, and backtracking.
R. Lestari
2012-12-01
Full Text Available Tujuan penelitian tindakan kelas ini untuk mengetahui pengaruh proses pembelajaran dengan menggunakan model pembelajaran kooperatif tipe Pair Checks pemecahan masalah terhadap peningkatan social skill siswa. Pada proses penerapan model pembelajaran kooperatif tipe Pair Checks pemecahan masalah siswa dibagi dalam kelompok-kelompok dan satu kelompok terdiri dari dua orang. Setiap kelompok berdiskusi untuk menyelesaikan suatu masalah, kemudian hasil diskusi kelompok akan dicek oleh pasangan dari kelompok lain. Metode Penelitian yang digunakan adalah penelitian tindakan kelas yang dilaksanakan dua siklus. Metode pengumpulan data menggunakan tes dan angket skala sikap, sedangkan teknik analisis data menggunakan teknik analisis data kuantitatif. Social Skill siswa dari siklus I ke siklus II mengalami peningkatan. Hal ini didapatkan dari data angket skala sikap siklus I ke siklus II ketuntasan klasikalnya meningkat dan sebagian besar siswa sudah memiliki social skill yang baik. Hasil belajar kognitif siswa juga mengalami peningkatan. Model pembelajaran kooperatif tipe Pair Checks pemecahan masalah dapat meningkatkan social skill siswa.This two cycles-action research aimed to know learning process applying cooperative learning model-pair checks problem solving type and improvement of studentâ€™s social skills. The process of the model was as follows: deviding students into some groups consisting of two students, solving problem by each group and checking result of the discussion by other groups. Data collection method used was test and the use of attitude scale questionnaire, while technique of data analysis used was quantitative data analysis technique. The data analysis result showed that there was an increase of studentâ€™s social skill and studentsâ€™ achievement from cycle one to two. It is concluded that cooperative learning model-pair checks problem solving type can enhance studentâ€™s social skills
Electrostatic charge bounds for ball lightning models
Several current theories concerning the nature of ball lightning predict a substantial electrostatic charge in order to account for its observed motion and shape (Turner 1998 Phys. Rep. 293 1; Abrahamson and Dinniss 2000 Nature 403 519). Using charged soap bubbles as a physical model for ball lightning, we show that the magnitude of charge predicted by some of these theories is too high to allow for the types of motion commonly observed in natural ball lightning, which includes horizontal motion above the ground and movement near grounded conductors. Experiments show that at charge levels of only 10-15 nC, 3-cm-diameter soap bubbles tend to be attracted by induced charges to the nearest grounded conductor and rupture. We conclude with a scaling rule that can be used to extrapolate these results to larger objects and surroundings
DiVinE-CUDA - A Tool for GPU Accelerated LTL Model Checking
Jiří Barnat
2009-12-01
Full Text Available In this paper we present a tool that performs CUDA accelerated LTL Model Checking. The tool exploits parallel algorithm MAP adjusted to the NVIDIA CUDA architecture in order to efficiently detect the presence of accepting cycles in a directed graph. Accepting cycle detection is the core algorithmic procedure in automata-based LTL Model Checking. We demonstrate that the tool outperforms non-accelerated version of the algorithm and we discuss where the limits of the tool are and what we intend to do in the future to avoid them.
Model Checking Process Algebra of Communicating Resources for Real-time Systems
Boudjadar, Jalil; Kim, Jin Hyun; Larsen, Kim Guldstrand;
2014-01-01
This paper presents a new process algebra, called PACOR, for real-time systems which deals with resource constrained timed behavior as an improved version of the ACSR algebra. We define PACOR as a Process Algebra of Communicating Resources which allows to express preemptiveness, urgent ness and...... original semantics of PACOR and enables the verification of PACOR systems using symbolic model checking in UPPAAL and statistical model checking UPPAAL SMC. Finally we provide an example to illustrate system specification in PACOR, translation and verification....
Model checking process algebra of communicating resources for real-time systems
Boudjadar, Jalil; Kim, Jin Hyun; Larsen, Kim Guldstrand;
2014-01-01
This paper presents a new process algebra, called PACoR, for real-time systems which deals with resource- constrained timed behavior as an improved version of the ACSR algebra. We define PACoR as a Process Algebra of Communicating Resources which allows to explicitly express preemptiveness...... preserves the original semantics of PACoR and enables the verification of PACoR systems using symbolic model checking in Uppaal and statistical model checking UppaalSMC. Finally we provide an example to illustrate system specification in PACoR, translation and verification....
Quark model study of the triton bound stat
Juliá-Díaz, B.; Fernández, F.; Valcarce, A.; Haidenbauer, J.
2001-01-01
The three-nucleon bound state problem is studied employing nucleon-nucleon potentials derived from a basic quark-quark interaction. We analyze the effects of the nonlocalities generated by the quark model. The calculated triton binding energies indicate that quark-model nonlocalities can yield additional binding in the order of few hundred keV.
Application safety enhancement model using self-checking with software enzymes
Subramaniam, Chandrasekaran; Ravishankar, Arthi; Gopal, Deepthi; Subramanian, Dhaarini
2011-12-01
The objective of the paper is to propose a safety enhancement model for application software in accelerating the respective self checking strategies similar to bio enzymatic actions. The application software components which are safety critical may have to be assessed periodically or on demand to achieve not only the functional correctness but also the safety specifications or features while getting executed. The design and deployment of such software modules can be formally verified for possible safety flaws using self checking capabilities and software enzymatic actions. The self checks must sense the safety holes in the software and decide to activate the built-in software components called enzymes to do the safe guard operations in a timely manner to mitigate the safety faults using the proposed enzyme calculus. The various application hazards due to the boolean faults in the functional and behavioral model that lead to software safety issues are considered in this approach.
Boson bound states in the -Fermi–Pasta–Ulam model
Xin-Guang Hu; Ju Xiang; Zheng Jiao; Yang Liu; Guo-Qiu Xie; Ke Hu
2013-11-01
The bound states of four bosons in the quantum -Fermi–Pasta–Ulam model are investigated and some interesting results are presented using the number conserving approximation combined with the number state method. We find that the relative magnitude of anharmonic coefficient has a significant effect on forming localized energy in the model, and the wave number plays an important role in forming different bound states. The signature of the quantum breather is also set up by the square of the amplitudes of the corresponding eigenvectors in real space.
Nonparametric checks for count data models: an application to demand for health care in Spain
Álvarez, Begoña; Delgado, Miguel A.
1997-01-01
This paper presents model specification checking procedures for count data regression models which are consistent in the direction of nonparametric alternatives. The discussion is motivated in the context of a model of demand for health care in Spain. The parameters of the regression model are estimated by maximum likelihood based on Poisson and Negative Binomial specifications as well as by ordinary least squares and semiparametric generalized least squares. However, our interest is not only...
Incremental checking of Master Data Management model based on contextual graphs
Lamolle, Myriam; Menet, Ludovic; Le Duc, Chan
2015-10-01
The validation of models is a crucial step in distributed heterogeneous systems. In this paper, an incremental validation method is proposed in the scope of a Model Driven Engineering (MDE) approach, which is used to develop a Master Data Management (MDM) field represented by XML Schema models. The MDE approach presented in this paper is based on the definition of an abstraction layer using UML class diagrams. The validation method aims to minimise the model errors and to optimisethe process of model checking. Therefore, the notion of validation contexts is introduced allowing the verification of data model views. Description logics specify constraints that the models have to check. An experimentation of the approach is presented through an application developed in ArgoUML IDE.
Specification and Generation of Environment for Model Checking of Software Components
Pařízek, P.; Plášil, František
2007-01-01
Roč. 176, - (2007), s. 143-154. ISSN 1571-0661 R&D Projects: GA AV ČR 1ET400300504 Institutional research plan: CEZ:AV0Z10300504 Keywords : software components * behavior protocols * model checking * automated generation of environment Subject RIV: JC - Computer Hardware ; Software
On Robustness Analysis of Stochastic Biochemical Systems by Probabilistic Model Checking
Brim, Lubos; Ceska, Milan; Drazan, Sven; Safranek, David
2013-01-01
This report proposes a novel framework for a rigorous robustness analysis of stochastic biochemical systems. The technique is based on probabilistic model checking. We adapt the general definition of robustness introduced by Kitano to the class of stochastic systems modelled as continuous time Markov Chains in order to extensively analyse and compare robustness of biological models with uncertain parameters. The framework utilises novel computational methods that enable to effectively evaluat...
Machine Learning Methods in Statistical Model Checking and System Design – Tutorial
Bortolussi, Luca; Milios, Dimitrios; Sanguinetti, Guido
2015-01-01
Recent research has seen an increasingly fertile convergence of ideas from machine learning and formal modelling. Here we review some recently introduced methodologies for model checking and system design/parameter synthesis for logical properties against stochastic dynamical models. The crucial insight is a regularity result which states that the satisfaction probability of a logical formula is a smooth function of the parameters of a CTMC. This enables us to select an appropriate class of f...
An interval-valued reliability model with bounded failure rates
Kozine, Igor; Krymsky, Victor
2012-01-01
The approach to deriving interval-valued reliability measures described in this paper is distinctive from other imprecise reliability models in that it overcomes the issue of having to impose an upper bound on time to failure. It rests on the presupposition that a constant interval-valued failure...
Cryptography in the Bounded Quantum-Storage Model
Damgård, Ivan Bjerre; Serge, Fehr; Schaffner, Christian;
2008-01-01
We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory...
Cryptography In The Bounded Quantum-Storage Model
Damgård, Ivan Bjerre; Salvail, Louis; Schaffner, Christian;
2005-01-01
We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory...
Ravie c. Muniyandi
2010-01-01
Full Text Available Problem statement: Membrane computing formalism has provided better modeling capabilities for biological systems in comparison to conventional mathematical models. Model checking could be used to reason about the biological system in detail and with precision by verifying formally whether membrane computing model meets the properties of the system. Approach: This study was carried to investigate the preservation of properties of two biological systems that had been modeled and simulated in membrane computing by a method of model checking using PRISM. The two biological systems were prey-predator population and signal processing in the legend-receptor networks of protein TGF-ß. Results: The model checking of membrane computing model of the biological systems with five different properties showed that the properties of the biological systems could be preserved in the membrane computing model. Conclusion: Membrane computing model not only provides a better approach in representing and simulating a biological system but also able to sustain the basic properties of the system.
Gilbert, David
2016-01-01
Insights gained from multilevel computational models of biological systems can be translated into real-life applications only if the model correctness has been verified first. One of the most frequently employed in silico techniques for computational model verification is model checking. Traditional model checking approaches only consider the evolution of numeric values, such as concentrations, over time and are appropriate for computational models of small scale systems (e.g. intracellular networks). However for gaining a systems level understanding of how biological organisms function it is essential to consider more complex large scale biological systems (e.g. organs). Verifying computational models of such systems requires capturing both how numeric values and properties of (emergent) spatial structures (e.g. area of multicellular population) change over time and across multiple levels of organization, which are not considered by existing model checking approaches. To address this limitation we have developed a novel approximate probabilistic multiscale spatio-temporal meta model checking methodology for verifying multilevel computational models relative to specifications describing the desired/expected system behaviour. The methodology is generic and supports computational models encoded using various high-level modelling formalisms because it is defined relative to time series data and not the models used to generate it. In addition, the methodology can be automatically adapted to case study specific types of spatial structures and properties using the spatio-temporal meta model checking concept. To automate the computational model verification process we have implemented the model checking approach in the software tool Mule (http://mule.modelchecking.org). Its applicability is illustrated against four systems biology computational models previously published in the literature encoding the rat cardiovascular system dynamics, the uterine contractions of labour
Trajectory based models. Evaluation of minmax pricing bounds
Degano, Ivan; Ferrando, Sebastian; Gonzalez, Alfredo
2015-01-01
The paper studies market models based on trajectory spaces, properties of such models are obtained without recourse to probabilistic assumptions. For a given European option, an interval of rational prices exists under a more general condition than the usual no-arbitrage requirement. The paper develops computational results in order to evaluate the option bounds; the global minmax optimization, defining the price interval, is reduced to a local minmax optimization via dynamic programming. A g...
Towards Support for Software Model Checking: Improving the Efficiency of Formal Specifications
Salamah Salamah
2011-01-01
presented in this paper provides improved LTL specifications for patterns and scopes over those originally provided by Prospec. This improvement comes in the efficiency of the LTL formulas as measured in terms of the number of states in the Büchi automaton generated for the formula. Minimizing the size of the Büchi automata for an LTL specification provides a significant improvement for model checking software systems using such tools as the highly acclaimed Spin model checker.
General bound of overfitting for MLP regression models
Rynkiewicz, Joseph
2012-01-01
Multilayer perceptrons (MLP) with one hidden layer have been used for a long time to deal with non-linear regression. However, in some task, MLP's are too powerful models and a small mean square error (MSE) may be more due to overfitting than to actual modelling. If the noise of the regression model is Gaussian, the overfitting of the model is totally determined by the behavior of the likelihood ratio test statistic (LRTS), however in numerous cases the assumption of normality of the noise is arbitrary if not false. In this paper, we present an universal bound for the overfitting of such model under weak assumptions, this bound is valid without Gaussian or identifiability assumptions. The main application of this bound is to give a hint about determining the true architecture of the MLP model when the number of data goes to infinite. As an illustration, we use this theoretical result to propose and compare effective criteria to find the true architecture of an MLP.
A Skyrme-like model with an exact BPS bound
Ferreira, L.A.; Zakrzewski, Wojtek J.
2013-01-01
We propose a new Skyrme-like model with fields taking values on the sphere S^3 or, equivalently, on the group SU(2). The action of the model contains a quadratic kinetic term plus a quartic term which is the same as that of the Skyrme-Faddeev model. The novelty of the model is that it possess a first order Bogomolny type equation whose solutions automatically satisfy the second order Euler-Lagrange equations. It also possesses a lower bound on the static energy which is saturated by the Bogom...
Generalized Skyrme model with the loosely bound potential
Gudnason, Sven Bjarke; Ma, Nana
2016-01-01
We study a generalization of the loosely bound Skyrme model which consists of the Skyrme model with a sixth-order derivative term and the second-order loosely bound potential. We use the rational map approximation for the 4-Skyrmion and calculate the binding energy and estimate the systematic error in using the latter approximation. In the parameter space that we can explore within the rational map approximation, we find classical binding energies as low as 1.8% and once taking into account the contribution from spin-isospin quantization we obtain binding energies as low as 5.3%. We also calculate the contribution from the sixth-order derivative term to the electric charge density and axial coupling.
Checking the Adequacy of Fit of Models from Split-Plot Designs
Almini, A. A.; Kulahci, Murat; Montgomery, D. C.
2009-01-01
-plot models. In this article, we propose the computation of two R-2, R-2-adjusted, prediction error sums of squares (PRESS), and R-2-prediction statistics to measure the adequacy of fit for the WP and the SP submodels in a split-plot design. This is complemented with the graphical analysis of the two types...... of errors to check for any violation of the underlying assumptions and the adequacy of fit of split-plot models. Using examples, we show how computing two measures of model adequacy of fit for each split-plot design model is appropriate and useful as they reveal whether the correct WP and SP effects have...
HyLTL: a temporal logic for model checking hybrid systems
Davide Bresolin
2013-08-01
Full Text Available The model-checking problem for hybrid systems is a well known challenge in the scientific community. Most of the existing approaches and tools are limited to safety properties only, or operates by transforming the hybrid system to be verified into a discrete one, thus loosing information on the continuous dynamics of the system. In this paper we present a logic for specifying complex properties of hybrid systems called HyLTL, and we show how it is possible to solve the model checking problem by translating the formula into an equivalent hybrid automaton. In this way the problem is reduced to a reachability problem on hybrid automata that can be solved by using existing tools.
Holography and entropy bounds in the plane wave matrix model
Bousso, R; Bousso, Raphael; Mints, Aleksey L.
2006-01-01
As a quantum theory of gravity, Matrix theory should provide a realization of the holographic principle, in the sense that a holographic theory should contain one binary degree of freedom per Planck area. We present evidence that Bekenstein's entropy bound, which is related to area differences, is manifest in the plane wave matrix model. If holography is implemented in this way, we predict crossover behavior at strong coupling when the energy exceeds N^2 in units of the mass scale.
Higgs mass bound in the minimal standard model
Heller, U M
1993-01-01
A brief review of the role of the Higgs mechanism and the ensuing Higgs particle in the Minimal Standard Model is given. Then the property of triviality of the scalar sector in the Minimal Standard Model and the upper bound on the Higgs mass that follows is discussed. It is emphasized that the bound is obtained by limiting cutoff effects on physical processes. Actions that allow a parameterization and tuning of the leading cutoff effects are studied both analytically, in the large $N$ limit of the generalization of the $O(4)$ symmetry of the scalar sector to $O(N)$, and numerically for the physical case $N = 4$. Combining those results we show that the Minimal Standard Model will describe physics to an accuracy of a few percent up to energies of the order 2 to 4 times the Higgs mass, $M_H$, only if $M_H \\le 710 \\pm 60 ~ GeV$. This bound is the result of a systematic search in the space of dimension six operators and is expected to hold in the {\\it continuum}. (Complete postscript file can be obtained by anony...
Combination of Model Checking and Theorem Proving to Verify Embedded Software
XIAO Jian-yu; ZHANG De-yun; DONG Hao; CHEN Hai-quan
2005-01-01
In this paper, a scheme of combining model checking and theorem proving techniques to verify high trustworthy embedded software is proposed. The software model described in state machine of unified model language is transformed into the input modeling language of a model checker in which the model is analyzed with associated property specifications expressed in temporal logic. The software model which has been verified by model checker is then transformed into abstract specifications of a theorem prover , in which the model will be refined, verified and translated into source C code. The transformation rules from state machine to input language of model checker and abstract specifications of theorem prover are given. The experiment shows that the proposed scheme can effectively improve the development and verification of high trustworthy embedded software.
Visual Predictive Check in Models with Time-Varying Input Function.
Largajolli, Anna; Bertoldo, Alessandra; Campioni, Marco; Cobelli, Claudio
2015-11-01
The nonlinear mixed effects models are commonly used modeling techniques in the pharmaceutical research as they enable the characterization of the individual profiles together with the population to which the individuals belong. To ensure a correct use of them is fundamental to provide powerful diagnostic tools that are able to evaluate the predictive performance of the models. The visual predictive check (VPC) is a commonly used tool that helps the user to check by visual inspection if the model is able to reproduce the variability and the main trend of the observed data. However, the simulation from the model is not always trivial, for example, when using models with time-varying input function (IF). In this class of models, there is a potential mismatch between each set of simulated parameters and the associated individual IF which can cause an incorrect profile simulation. We introduce a refinement of the VPC by taking in consideration a correlation term (the Mahalanobis or normalized Euclidean distance) that helps the association of the correct IF with the individual set of simulated parameters. We investigate and compare its performance with the standard VPC in models of the glucose and insulin system applied on real and simulated data and in a simulated pharmacokinetic/pharmacodynamic (PK/PD) example. The newly proposed VPC performance appears to be better with respect to the standard VPC especially for the models with big variability in the IF where the probability of simulating incorrect profiles is higher. PMID:26265094
Bounding the Practical Error of Path Loss Models
Caleb Phillips
2012-01-01
Full Text Available We seek to provide practical lower bounds on the prediction accuracy of path loss models. We describe and implement 30 propagation models of varying popularity that have been proposed over the last 70 years. Our analysis is performed using a large corpus of measurements collected on production networks operating in the 2.4 GHz ISM, 5.8 GHz UNII, and 900 MHz ISM bands in a diverse set of rural and urban environments. We find that the landscape of path loss models is precarious: typical best-case performance accuracy of these models is on the order of 12–15 dB root mean square error (RMSE and in practice it can be much worse. Models that can be tuned with measurements and explicit data fitting approaches enable a reduction in RMSE to 8-9 dB. These bounds on modeling error appear to be relatively constant, even in differing environments and at differing frequencies. Based on our findings, we recommend the use of a few well-accepted and well-performing standard models in scenarios where a priori predictions are needed and argue for the use of well-validated, measurement-driven methods whenever possible.
Characteristics of successful opinion leaders in a bounded confidence model
Chen, Shuwei; Glass, David H.; McCartney, Mark
2016-05-01
This paper analyses the impact of competing opinion leaders on attracting followers in a social group based on a bounded confidence model in terms of four characteristics: reputation, stubbornness, appeal and extremeness. In the model, reputation differs among leaders and normal agents based on the weights assigned to them, stubbornness of leaders is reflected by their confidence towards normal agents, appeal of the leaders is represented by the confidence of followers towards them, and extremeness is captured by the opinion values of leaders. Simulations show that increasing reputation, stubbornness or extremeness makes it more difficult for the group to achieve consensus, but increasing the appeal will make it easier. The results demonstrate that successful opinion leaders should generally be less stubborn, have greater appeal and be less extreme in order to attract more followers in a competing environment. Furthermore, the number of followers can be very sensitive to small changes in these characteristics. On the other hand, reputation has a more complicated impact: higher reputation helps the leader to attract more followers when the group bound of confidence is high, but can hinder the leader from attracting followers when the group bound of confidence is low.
A variational study of bound states in the Higgs model
Siringo, F
2000-01-01
The possible existence of Higgs-Higgs bound states in the Higgs sector of the Standard Model is explored using the |hh>+|hhh> variational ansatz of Di Leo and Darewych. The resulting integral equations can be decoupled exactly, yielding a one-dimensional integral equation, solved numerically. We thereby avoid the extra approximations employed by Di Leo and Darewych, and we find a qualitatively different mass renormalization. Within the conventional scenario, where a not-too-large cutoff is invoked to avoid "triviality", we find, as usual, an upperbound on the Higgs mass. Bound-state solutions are only found in the very strong coupling regime, but at the same time a relatively small physical mass is required as a consequence of renormalization.
Modifying the pion mass in the loosely bound Skyrme model
Gudnason, Sven Bjarke
2016-01-01
We study the loosely bound Skyrme model with the addition of two different pion mass terms; this is the most general potential of polynomial form up to second order in the trace of the Skyrme field. The two pion mass terms are called the standard pion mass term and the modified pion mass term. We find that the binding energies are not reduced by the introduction of the modified pion mass, but slightly larger values of the coefficient of the loosely bound potential are allowed when the modified pion mass term is used compared to the standard pion mass term. We find by increasing the overall pion mass that we can reduce the classical binding energy of the 4-Skyrmion to the 2.7% level and the total binding energy including the contribution from spin/isospin quantization is reduced to the 5.8% level.
Model-Checking the Higher-Dimensional Modal mu-Calculus
Lange, Martin; 10.4204/EPTCS.77.6
2012-01-01
The higher-dimensional modal mu-calculus is an extension of the mu-calculus in which formulas are interpreted in tuples of states of a labeled transition system. Every property that can be expressed in this logic can be checked in polynomial time, and conversely every polynomial-time decidable problem that has a bisimulation-invariant encoding into labeled transition systems can also be defined in the higher-dimensional modal mu-calculus. We exemplify the latter connection by giving several examples of decision problems which reduce to model checking of the higher-dimensional modal mu-calculus for some fixed formulas. This way generic model checking algorithms for the logic can then be used via partial evaluation in order to obtain algorithms for theses problems which may benefit from improvements that are well-established in the field of program verification, namely on-the-fly and symbolic techniques. The aim of this work is to extend such techniques to other fields as well, here exemplarily done for process...
Bounds for perpetual American option prices in a jump diffusion model
Ekström, Erik
2006-01-01
We provide bounds for perpetual American option prices in a jump diffusion model in terms of American option prices in the standard Black-Scholes model. We also investigate the dependence of the bounds on different parameters of the model.
Sediment depositions upstream of open check dams: new elements from small scale models
Piton, Guillaume; Le Guern, Jules; Carbonari, Costanza; Recking, Alain
2015-04-01
numbers that the flows tend to adopt? New small scale model experiments have been undertaken focusing on depositions processes and their related hydraulics. Accurate photogrammetric measurements allowed us to better describe the deposition processes3. Large Scale Particle Image Velocimetry (LS-PIV) was performed to determine surface velocity fields in highly active channels with low grain submersion4. We will present preliminary results of our experiments showing the new elements we observed in massive deposit dynamics. REFERENCES 1.Armanini, A., Dellagiacoma, F. & Ferrari, L. From the check dam to the development of functional check dams. Fluvial Hydraulics of Mountain Regions 37, 331-344 (1991). 2.Piton, G. & Recking, A. Design of sediment traps with open check dams: a review, part I: hydraulic and deposition processes. (Accepted by the) Journal of Hydraulic Engineering 1-23 (2015). 3.Le Guern, J. Ms Thesis: Modélisation physique des plages de depot : analyse de la dynamique de remplissage.(2014) . 4.Carbonari, C. Ms Thesis: Small scale experiments of deposition processes occuring in sediment traps, LS-PIV measurments and geomorphological descriptions. (in preparation).
An Efficient Explicit-time Description Method for Timed Model Checking
Wang, Hao; 10.4204/EPTCS.14.6
2009-01-01
Timed model checking, the method to formally verify real-time systems, is attracting increasing attention from both the model checking community and the real-time community. Explicit-time description methods verify real-time systems using general model constructs found in standard un-timed model checkers. Lamport proposed an explicit-time description method using a clock-ticking process (Tick) to simulate the passage of time together with a group of global variables to model time requirements. Two methods, the Sync-based Explicit-time Description Method using rendezvous synchronization steps and the Semaphore-based Explicit-time Description Method using only one global variable were proposed; they both achieve better modularity than Lamport's method in modeling the real-time systems. In contrast to timed automata based model checkers like UPPAAL, explicit-time description methods can access and store the current time instant for future calculations necessary for many real-time systems, especially those with p...
Constraint LTL Satisfiability Checking without Automata
Bersani, Marcello M; Morzenti, Angelo; Pradella, Matteo; Rossi, Matteo; Pietro, Pierluigi San
2012-01-01
This paper introduces a novel technique to decide the satisfiability of formulae written in the language of Linear Temporal Logic with Both future and past operators and atomic formulae belonging to constraint system D (CLTLB(D) for short). The technique is based on the concept of bounded satisfiability, and hinges on an encoding of CLTLB(D) formulae into QF-EUD, the theory of quantifier-free equality and uninterpreted functions combined with D. Similarly to standard LTL, where bounded model-checking and SAT-solvers can be used as an alternative to automata-theoretic approaches to model-checking, our approach allows users to solve the satisfiability problem for CLTLB(D) formulae through SMT-solving techniques, rather than by checking the emptiness of the language of a suitable automaton A{\\phi}. The technique is effective, and it has been implemented in our Zot formal verification tool.
Model Checking and Code Generation for UML Diagrams Using Graph Transformation
Wafa Chama
2012-12-01
Full Text Available UML is considered as the standard for object-oriented modelling language adopted by the ObjectManagement Group. However, UML has been criticized due to the lack of formal semantics and theambiguity of its models. In other hands, UML models can be mathematically verified and checked by usingits equivalent formal representation. So, in this paper, we propose an approach and a tool based on graphtransformation to perform an automatic mapping for verification purposes. This transformation aims tobridge the gap between informal and formal notations and allows a formal verification of concurrent UMLmodels using Maude language. We consider both static (Class Diagram and dynamic (StateChart andCommunication Diagrams features of concurrent object-oriented system. Then, we use Maude LTL ModelChecker to verify the formal model obtained (Automatic Code Generation Maude. The meta-modellingAToM3 tool is used. A case study is presented to illustrate our approach.
Stieltjes electrostatic model interpretation for bound state problems
K V S Shiv Chaitanya
2014-07-01
In this paper, it is shown that Stieltjes electrostatic model and quantum Hamilton Jacobi formalism are analogous to each other. This analogy allows the bound state problem to mimic as unit moving imaginary charges $i\\hbar$, which are placed in between the two fixed imaginary charges arising due to the classical turning points of the potential. The interaction potential between unit moving imaginary charges $i\\hbar$ is given by the logarithm of the wave function. For an exactly solvable potential, this system attains stable equilibrium position at the zeros of the orthogonal polynomials depending upon the interval of the classical turning points.
Christian Krause
2011-11-01
Full Text Available The assurance of quality of service properties is an important aspect of service-oriented software engineering. Notations for so-called service level agreements (SLAs, such as the Web Service Level Agreement (WSLA language, provide a formal syntax to specify such assurances in terms of (legally binding contracts between a service provider and a customer. On the other hand, formal methods for veriﬁcation of probabilistic real-time behavior have reached a level of expressiveness and efﬁciency which allows to apply them in real-world scenarios. In this paper, we suggest to employ the recently introduced model of Interval Probabilistic Timed Automata (IPTA for formal veriﬁcation of QoS properties of service-oriented systems. Speciﬁcally, we show that IPTA in contrast to Probabilistic Timed Automata (PTA are able to capture the guarantees speciﬁed in SLAs directly. A particular challenge in the analysis of IPTA is the fact that their naive semantics usually yields an inﬁnite set of states and inﬁnitely-branching transitions. However, using symbolic representations, IPTA can be analyzed rather efﬁciently. We have developed the ﬁrst implementation of an IPTA model checker by extending the PRISM tool and show that model checking IPTA is only slightly more expensive than model checking comparable PTA.
Marcus Völp
2012-11-01
Full Text Available Reliability in terms of functional properties from the safety-liveness spectrum is an indispensable requirement of low-level operating-system (OS code. However, with evermore complex and thus less predictable hardware, quantitative and probabilistic guarantees become more and more important. Probabilistic model checking is one technique to automatically obtain these guarantees. First experiences with the automated quantitative analysis of low-level operating-system code confirm the expectation that the naive probabilistic model checking approach rapidly reaches its limits when increasing the numbers of processes. This paper reports on our work-in-progress to tackle the state explosion problem for low-level OS-code caused by the exponential blow-up of the model size when the number of processes grows. We studied the symmetry reduction approach and carried out our experiments with a simple test-and-test-and-set lock case study as a representative example for a wide range of protocols with natural inter-process dependencies and long-run properties. We quickly see a state-space explosion for scenarios where inter-process dependencies are insignificant. However, once inter-process dependencies dominate the picture models with hundred and more processes can be constructed and analysed.
Model checking of safety-critical software in the nuclear engineering domain
Instrumentation and control (I and C) systems play a vital role in the operation of safety-critical processes. Digital programmable logic controllers (PLC) enable sophisticated control tasks which sets high requirements for system validation and verification methods. Testing and simulation have an important role in the overall verification of a system but are not suitable for comprehensive evaluation because only a limited number of system behaviors can be analyzed due to time limitations. Testing is also performed too late in the development lifecycle and thus the correction of design errors is expensive. This paper discusses the role of formal methods in software development in the area of nuclear engineering. It puts forward model checking, a computer-aided formal method for verifying the correctness of a system design model, as a promising approach to system verification. The main contribution of the paper is the development of systematic methodology for modeling safety critical systems in the nuclear domain. Two case studies are reviewed, in which we have found errors that were previously not detected. We also discuss the actions that should be taken in order to increase confidence in the model checking process.
Lochbihler, Andreas
2012-01-01
The Java programming language provides safety and security guarantees such as type safety and its security architecture. They distinguish it from other mainstream programming languages like C and C++. In this work, we develop a machine-checked model of concurrent Java and the Java memory model and investigate the impact of concurrency on these guarantees. From the formal model, we automatically obtain an executable verified compiler to bytecode and a validated virtual machine.
Unitarity bound in the most general two Higgs doublet model
Shinya Kanemura
2015-12-01
Full Text Available We investigate unitarity bounds in the most general two Higgs doublet model without a discrete Z2 symmetry nor CP conservation. S-wave amplitudes for two-body elastic scatterings of Nambu–Goldstone bosons and physical Higgs bosons are calculated at high energies for all possible initial and final states (14 neutral, 8 singly-charged and 3 doubly-charged states. We obtain analytic formulae for the block-diagonalized scattering matrix by the classification of the two body scattering states using the conserved quantum numbers at high energies. Imposing the condition of perturbative unitarity to the eigenvalues of the scattering matrix, constraints on the model parameters can be obtained. We apply our results to constrain the mass range of the next-to-lightest Higgs state in the model.
Monitor-Based Statistical Model Checking for Weighted Metric Temporal Logic
Bulychev, Petr; David, Alexandre; Larsen, Kim Guldstrand;
2012-01-01
We present a novel approach and implementation for ana- lysing weighted timed automata (WTA) with respect to the weighted metric temporal logic (WMTL≤ ). Based on a stochastic semantics of WTAs, we apply statistical model checking (SMC) to estimate and test probabilities of satisfaction with...... desired levels of confidence. Our ap- proach consists in generation of deterministic monitors for formulas in WMTL≤ , allowing for efficient SMC by run-time evaluation of a given formula. By necessity, the deterministic observers are in general approx- imate (over- or under-approximations), but are most...
Bringing Automated Model Checking to PLC Program Development - A CERN Case Study
Fernandez Adiego, B; Tournier, J-C; Blanco Vinuela, E; Gonzalez Suarez, V M
2014-01-01
Verification of critical software is a high priority but a challenging task for industrial control systems. Model checking appears to be an appropriate approach for this purpose. However, this technique is not widely used in industry yet, due to some obstacles. The main obstacles encountered when trying to apply formal verification techniques at industrial installations are the difficulty of creating models out of PLC programs and defining formally the specification requirements. In addition, models produced out of real-life programs have a huge state space, thus preventing the verification due to performance issues. Our work at CERN (European Organization for Nuclear Research) focuses on developing efficient automatic verification methods for industrial critical installations based on PLC (Programmable Logic Controller) control systems. In this paper, we present a tool generating automatically formal models out of PLC code. The tool implements a general methodology which can support several input languages, ...
G. Bussi
2013-08-01
Full Text Available Soil loss and sediment transport in Mediterranean areas are driven by complex non-linear processes which have been only partially understood. Distributed models can be very helpful tools for understanding the catchment-scale phenomena which lead to soil erosion and sediment transport. In this study, a modelling approach is proposed to reproduce and evaluate erosion and sediment yield processes in a Mediterranean catchment (Rambla del Poyo, Valencia, Spain. Due to the lack of sediment transport records for model calibration and validation, a detailed description of the alluvial stratigraphy infilling a check dam that drains a 12.9 km2 sub-catchment was used as indirect information of sediment yield data. These dam infill sediments showed evidences of at least 15 depositional events (floods over the time period 1990–2009. The TETIS model, a distributed conceptual hydrological and sediment model, was coupled to the Sediment Trap Efficiency for Small Ponds (STEP model for reproducing reservoir retention, and it was calibrated and validated using the sedimentation volume estimated for the depositional units associated with discrete runoff events. The results show relatively low net erosion rates compared to other Mediterranean catchments (0.136 Mg ha−1 yr−1, probably due to the extensive outcrops of limestone bedrock, thin soils and rather homogeneous vegetation cover. The simulated sediment production and transport rates offer model satisfactory results, further supported by in-site palaeohydrological evidences and spatial validation using additional check dams, showing the great potential of the presented data assimilation methodology for the quantitative analysis of sediment dynamics in ungauged Mediterranean basins.
Model Checking Artificial Intelligence Based Planners: Even the Best Laid Plans Must Be Verified
Smith, Margaret H.; Holzmann, Gerard J.; Cucullu, Gordon C., III; Smith, Benjamin D.
2005-01-01
Automated planning systems (APS) are gaining acceptance for use on NASA missions as evidenced by APS flown On missions such as Orbiter and Deep Space 1 both of which were commanded by onboard planning systems. The planning system takes high level goals and expands them onboard into a detailed of action fiat the spacecraft executes. The system must be verified to ensure that the automatically generated plans achieve the goals as expected and do not generate actions that would harm the spacecraft or mission. These systems are typically tested using empirical methods. Formal methods, such as model checking, offer exhaustive or measurable test coverage which leads to much greater confidence in correctness. This paper describes a formal method based on the SPIN model checker. This method guarantees that possible plans meet certain desirable properties. We express the input model in Promela, the language of SPIN and express the properties of desirable plans formally.
Entropy Bound for the Crystalline Vacuum Cosmic Space Model
Montemayor-Aldrete, J A; Morales-Mori, A; Mendoza-Allende, A; Cabrera-Bravo, E; Montemayor-Varela, A
2005-01-01
By applying the Heisenberg's uncertainty principle for a macroscopic quantum gas formed by gravitational waves an expression for the universal bound on the entropy proposed by Bekenstein for any system of maximum radius R and total energy E has been obtained. By using such expression, in the theoretical scheme of the crystalline vacuum cosmic model, the low entropy value at the Big Bang beginning, 1088k, is explained. According to our analysis the time arrow is well defined and the theoretical time flow occurs only in one direction as requested by the physical processes of gravitational stabilization of the vacuum space crystalline structure around equilibrium conditions. PACS numbers: 65.50.+m, 97.60.Lf, 03.65.-w, 61.50.-f, 98.80.Ft, 04.20.-q
A Skyrme-like model with an exact BPS bound
Ferreira, L. A.; Zakrzewski, Wojtek J.
2013-09-01
We propose a new Skyrme-like model with fields taking values on the sphere S 3 or, equivalently, on the group SU(2). The action of the model contains a quadratic kinetic term plus a quartic term which is the same as that of the Skyrme-Faddeev model. The novelty of the model is that it possess a first order Bogomolny type equation whose solutions automatically satisfy the second order Euler-Lagrange equations. It also possesses a lower bound on the static energy which is saturated by the Bogomolny solutions. Such Bogomolny equation is equivalent to the so-called force free equation used in plasma and solar Physics, and which possesses large classes of solutions. An old result due to Chandrasekhar prevents the existence of finite energy solutions for the force free equation on the entire three-dimensional space . We construct new exact finite energy solutions to the Bogomolny equations for the case where the space is the three-sphere S 3, using toroidal like coordinates.
A Skyrme-like model with an exact BPS bound
Ferreira, L A
2013-01-01
We propose a new Skyrme-like model with fields taking values on the sphere S^3 or, equivalently, on the group SU(2). The action of the model contains a quadratic kinetic term plus a quartic term which is the same as that of the Skyrme-Faddeev model. The novelty of the model is that it possess a first order Bogomolny type equation whose solutions automatically satisfy the second order Euler-Lagrange equations. It also possesses a lower bound on the static energy which is saturated by the Bogomolny solutions. Such Bogomolny equation is equivalent to the so-called force free equation used in plasma and solar Physics, and which possesses large classes of solutions. An old result due to Chandrasekhar prevents the existence of finite energy solutions for the force free equation on the entire tridimensional space R^3. We construct new exact finite energy solutions to the Bogomolny equations for the case where the space is the three-sphere S^3, using toroidal like coordinates.
Distance bound for nonconvex polyhedral models in close proximity
Jiménez Schlegl, Pablo; Torras, Carme
2006-01-01
In many applications, it suffices to know a lower bound on the distance between objects, instead of the exact distance itself, which may be more difficult to compute. Such an easy-to-compute lower bound on the distance between two nonconvex polyhedra is presented here, which does not require a decomposition of the original polyhedra into convex entities. Furthermore, a suitable preprocessing of the polyhedra permits lowering the effort needed to compute this lower bound, and improves its qual...
Application of a hazard-based visual predictive check to evaluate parametric hazard models.
Huh, Yeamin; Hutmacher, Matthew M
2016-02-01
Parametric models used in time to event analyses are evaluated typically by survival-based visual predictive checks (VPC). Kaplan-Meier survival curves for the observed data are compared with those estimated using model-simulated data. Because the derivative of the log of the survival curve is related to the hazard--the typical quantity modeled in parametric analysis--isolation, interpretation and correction of deficiencies in the hazard model determined by inspection of survival-based VPC's is indirect and thus more difficult. The purpose of this study is to assess the performance of nonparametric hazard estimators of hazard functions to evaluate their viability as VPC diagnostics. Histogram-based and kernel-smoothing estimators were evaluated in terms of bias of estimating the hazard for Weibull and bathtub-shape hazard scenarios. After the evaluation of bias, these nonparametric estimators were assessed as a method for VPC evaluation of the hazard model. The results showed that nonparametric hazard estimators performed reasonably at the sample sizes studied with greater bias near the boundaries (time equal to 0 and last observation) as expected. Flexible bandwidth and boundary correction methods reduced these biases. All the nonparametric estimators indicated a misfit of the Weibull model when the true hazard was a bathtub shape. Overall, hazard-based VPC plots enabled more direct interpretation of the VPC results compared to survival-based VPC plots. PMID:26563504
Taming Numbers and Durations in the Model Checking Integrated Planning System
Edelkamp, S
2011-01-01
The Model Checking Integrated Planning System (MIPS) is a temporal least commitment heuristic search planner based on a flexible object-oriented workbench architecture. Its design clearly separates explicit and symbolic directed exploration algorithms from the set of on-line and off-line computed estimates and associated data structures. MIPS has shown distinguished performance in the last two international planning competitions. In the last event the description language was extended from pure propositional planning to include numerical state variables, action durations, and plan quality objective functions. Plans were no longer sequences of actions but time-stamped schedules. As a participant of the fully automated track of the competition, MIPS has proven to be a general system; in each track and every benchmark domain it efficiently computed plans of remarkable quality. This article introduces and analyzes the most important algorithmic novelties that were necessary to tackle the new layers of expressiven...
For those who run an organization, it is critical to identify the causal relationship between the organization's characteristics and the safety-checking action of its staff, in order to effectively implement activities for promoting safety. In this research. a causal model of the safety-checking action was developed and factors affecting it were studied. A questionnaire survey, which includes safety awareness, attitude toward safety, safety culture and others, was conducted at three nuclear power plants and eight factors were extracted by means of factor analysis of the questionnaire items. The extracted eight interrelated factors were as follows: work norm, supervisory action, interest in training, recognition of importance, safety-checking action, the subject of safety, knowledge/skills, and the attitude of an organization. Among them, seven factors except the recognition of importance were defined as latent variables and a causal model of safety-checking action was constructed. By means of covariance structure analysis, it was found that the three factors: the attitude of an organization, supervisory action and the subject of safety, have a significant effect on the safety-checking action. Moreover, it was also studied that workplaces in which these three factors are highly regarded form social environment where safety-checking action is fully supported by the workplace as a whole, while workplaces in which these three factors are poorly regarded do not fully form social environment where safety-checking action is supported. Therefore, the workplaces form an organizational environment where safety-checking action tends to depend strongly upon the knowledge or skills of individuals. On top of these, it was noted that the attitude of an organization and supervisory action are important factors that serve as the first trigger affecting the formation of the organizational climate for safety. (author)
The work of Krommes and Smith on rigorous upper bounds for the turbulent transport of a passively advected scalar [/ital Ann. Phys./ 177:246 (1987)] is extended in two directions: (1) For their ''reference model,'' improved upper bounds are obtained by utilizing more sophisticated two-time constraints which include the effects of cross-correlations up to fourth order. Numerical solutions of the model stochastic differential equation are also obtained; they show that the new bounds compare quite favorably with the exact results, even at large Reynolds and Kubo numbers. (2) The theory is extended to take account of a finite spatial autocorrelation length L/sub c/. As a reasonably generic example, the problem of particle transport due to statistically specified stochastic magnetic fields in a collisionless turbulent plasma is revisited. A bound is obtained which reduces for small L/sub c/ to the quasilinear limit and for large L/sub c/ to the strong turbulence limit, and which provides a reasonable and rigorous interpolation for intermediate values of L/sub c/. 18 refs., 6 figs
WAVE EQUATION MODEL FOR SHIP WAVES IN BOUNDED SHALLOW WATER
无
2000-01-01
Ships were modelled as moving pressure disturbances on the free surface of a shallow water basin in the present paper.The moving-pressure generating waves were subjected to the reflection of land boundaries and the radiation of open boundaries.This paper proposed and examined a wave equation model (WEM) to solve the shallow water equations with moving surface pressures simulating ship waves in a bounded shallow water region.The Galerkin finite element method was used to solve a second order wave equation for the free surface elevations and the hydrodynamic pressure of the ship bottom simultaneously.Horizontal velocities were obtained from the momentum equations.Numerical solutions of Series 60 CB=0.6 ships moving with the depth Froude number of Fh=0.6, 1.0, 1.3 in a rectangular shallow water harbor were investigated.Three dimensional surface elevation profiles and the depth-averaged horizontal velocities were analysed.The numerical results characterised very well the ship waves in shallow water.Strong boundary reflection waves were found in the case of high depth Froude number (Fh=1.3).Waves generated by the interactions of two ships moving in the same directions and in the opposite directions were also numerically investigated in the present study.
Perturbative Unitarity Bounds in Composite 2-Higgs Doublet Models
De Curtis, Stefania; Yagyu, Kei; Yildirim, Emine
2016-01-01
We study bounds from perturbative unitarity in a Composite 2-Higgs Doublet Model (C2HDM) based on the spontaneous breakdown of a global symmetry $SO(6)\\to SO(4)\\times SO(2)$ at the compositeness scale $f$. The eight pseudo Nambu-Goldstone Bosons (pNGBs) emerging from such a dynamics are identified as two isospin doublet Higgs fields. We calculate the $S$-wave amplitude for all possible 2-to-2-body elastic (pseudo)scalar boson scatterings at energy scales $\\sqrt{s}$ reachable at the Large Hadron Collider (LHC) and beyond it, including the longitudinal components of weak gauge boson states as the corresponding pNGB states. In our calculation, the Higgs potential is assumed to have the same form as that in the Elementary 2-Higgs Doublet Model (E2HDM) with a discrete $Z_2$ symmetry, which is expected to be generated at the one-loop level via the Coleman-Weinberg (CW) mechanism. We find that the $S$-wave amplitude matrix can be block-diagonalized with maximally $2\\times 2$ submatrices in a way similar to the E2HDM...
Pricing bounds for discrete arithmetic Asian options under Lévy models
Lemmens, D.; Liang, L. Z. J.; Tempere, J.; De Schepper, A.
2010-11-01
Analytical bounds for Asian options are almost exclusively available in the Black-Scholes framework. In this paper we derive bounds for the price of a discretely monitored arithmetic Asian option when the underlying asset follows an arbitrary Lévy process. Explicit formulas are given for Kou’s model, Merton’s model, the normal inverse Gaussian model, the CGMY model and the variance gamma model. The results are compared with the comonotonic upper bound, existing numerical results, Monte carlo simulations and in the case of the variance gamma model with an existing lower bound. The method outlined here provides lower and upper bounds that are quick to evaluate, and more accurate than existing bounds.
Extended FRAM by Integrating with Model Checking to Effectively Explore Hazard Evolution
Guihuan Duan
2015-01-01
Full Text Available Functional Resonance Analysis Method (FRAM, which defines a systemic framework to model complex systems from the perspective of function and views accidents as emergent phenomenon of function’s variability, is playing an increasingly significant role in the development of systemic accident theory. However, as FRAM is typically taken as a theoretic method, there is a lack of specific approaches or supportive tools to bridge the theory and practice. To fill the gap and contribute to the development of FRAM, (1 function’s variability was described further, with the rules of interaction among variability of different functions being determined and (2 the technology of model checking (MC was used for the analysis of function’s variability to automatically search the potential paths that could lead to hazards. By means of MC, system’s behaviors (normal or abnormal are simulated and the counter example(s that violates the safety constraints and requirements can be provided, if there is any, to improve the system design. The extended FRAM approach was applied to a typical air accident analysis, with more details drawn than the conclusions in the accident report issued officially by Agenzia Nazionale per la Sicurezza del Volo (ANSV.
A check valve for use in a GDCS of a nuclear reactor and having a motor driven disk including a rotatable armature for rotating the check valve disk over its entire range of motion is described. In one embodiment, the check valve includes a valve body having a coolant flow channel extending therethrough. The coolant flow channel includes an inlet end and an outlet end. A valve body seat is located on an inner surface of the valve body. The check valve further includes a disk assembly, sometimes referred to as the motor driven disc, having a counterweight and a disk shaped valve. The disk valve includes a disk base having a seat for seating with the valve body seat. The disk assembly further includes a first hinge pin member which extends at least partially through the disk assembly and is engaged to the disk. The disk valve is rotatable relative to the first hinge pin member. The check valve also includes a motor having a stator frame with a stator bore therein. An armature is rotatably positioned within the stator bore and the armature is coupled to the disk valve to cause the disk valve to rotate about its full range of motion. 5 figs
New perspective in statistical modeling of wall-bounded turbulence
She, Zhen-Su; Chen, Xi; Wu, You; Hussain, Fazle
2010-12-01
Despite dedicated effort for many decades, statistical description of highly technologically important wall turbulence remains a great challenge. Current models are unfortunately incomplete, or empirical, or qualitative. After a review of the existing theories of wall turbulence, we present a new framework, called the structure ensemble dynamics (SED), which aims at integrating the turbulence dynamics into a quantitative description of the mean flow. The SED theory naturally evolves from a statistical physics understanding of non-equilibrium open systems, such as fluid turbulence, for which mean quantities are intimately coupled with the fluctuation dynamics. Starting from the ensemble-averaged Navier-Stokes (EANS) equations, the theory postulates the existence of a finite number of statistical states yielding a multi-layer picture for wall turbulence. Then, it uses order functions (ratios of terms in the mean momentum as well as energy equations) to characterize the states and transitions between states. Application of the SED analysis to an incompressible channel flow and a compressible turbulent boundary layer shows that the order functions successfully reveal the multi-layer structure for wall-bounded turbulence, which arises as a quantitative extension of the traditional view in terms of sub-layer, buffer layer, log layer and wake. Furthermore, an idea of using a set of hyperbolic functions for modeling transitions between layers is proposed for a quantitative model of order functions across the entire flow domain. We conclude that the SED provides a theoretical framework for expressing the yet-unknown effects of fluctuation structures on the mean quantities, and offers new methods to analyze experimental and simulation data. Combined with asymptotic analysis, it also offers a way to evaluate convergence of simulations. The SED approach successfully describes the dynamics at both momentum and energy levels, in contrast with all prevalent approaches describing
Two-vibron bound states in the β-Fermi-Pasta-Ulam model
Hu Xin-Guang; Tang Yi
2008-01-01
This paper studies the two-vibron bound states in the β-Fermi-Pasta-Ulam model by means of the number conserving approximation combined with the number state method.The results indicate that on-site,adjacent-site and mixed two-vibron bound states may exist in the model.Specially,wave number has a significant effect on such bound states,which may be considered as the quantum effects of the localized states in quantum systems.
Hussain, Faraz; Jha, Sumit K.; Jha, Susmit; Langmead, Christopher J.
2014-01-01
Stochastic models are increasingly used to study the behaviour of biochemical systems. While the structure of such models is often readily available from first principles, unknown quantitative features of the model are incorporated into the model as parameters. Algorithmic discovery of parameter values from experimentally observed facts remains a challenge for the computational systems biology community. We present a new parameter discovery algorithm that uses simulated annealing, sequential ...
Vester, Steen
We study the complexity of the model-checking problem for the branching-time logic CTL ∗ and the alternating-time temporal logics ATL/ATL ∗ in one-counter processes and one-counter games respectively. The complexity is determined for all three logics when integer weights are input in unary (non...
K-nuclear bound states in a dynamical model
Mareš, Jiří; Friedman, E.; Gal, A.
2006-01-01
Roč. 770, 1/2 (2006), s. 84-105. ISSN 0375-9474 Institutional research plan: CEZ:AV0Z10480505 Keywords : kaonic atoms * K-nuclear bound states * K-nucleus interaction Subject RIV: BE - Theoretical Physics Impact factor: 2.155, year: 2006
Improved shape hardening function for bounding surface model for cohesive soils
Andrés Nieto-Leal
2014-08-01
Full Text Available A shape hardening function is developed that improves the predictive capabilities of the generalized bounding surface model for cohesive soils, especially when applied to overconsolidated specimens. This improvement is realized without any changes to the simple elliptical shape of the bounding surface, and actually reduces the number of parameters associated with the model by one.
Skyrmion model in 2+1 dimensions with soliton bound states
Piette, B.; Zakrzewski, W.J. (Dept. of Mathematical Sciences, Univ. Durham (United Kingdom))
1993-03-22
We consider a class of skyrmion models in 2+1 dimensions which possess bound stable solitons. We show that these models have one-soliton solutions as well as static solutions corresponding to their bound states. We study the scattering and stability properties of these solutions, compute their energies and estimate their binding energies. (orig.).
Automated parameter estimation for biological models using Bayesian statistical model checking
Hussain, Faraz; Langmead, Christopher J.; Mi, Qi; Dutta-Moscato, Joyeeta; Vodovotz, Yoram; Jha, Sumit K.
2015-01-01
Background Probabilistic models have gained widespread acceptance in the systems biology community as a useful way to represent complex biological systems. Such models are developed using existing knowledge of the structure and dynamics of the system, experimental observations, and inferences drawn from statistical analysis of empirical data. A key bottleneck in building such models is that some system variables cannot be measured experimentally. These variables are incorporated into the mode...
Dependence in probabilistic modeling, Dempster-Shafer theory, and probability bounds analysis.
Oberkampf, William Louis; Tucker, W. Troy (Applied Biomathematics, Setauket, NY); Zhang, Jianzhong (Iowa State University, Ames, IA); Ginzburg, Lev (Applied Biomathematics, Setauket, NY); Berleant, Daniel J. (Iowa State University, Ames, IA); Ferson, Scott (Applied Biomathematics, Setauket, NY); Hajagos, Janos (Applied Biomathematics, Setauket, NY); Nelsen, Roger B. (Lewis & Clark College, Portland, OR)
2004-10-01
This report summarizes methods to incorporate information (or lack of information) about inter-variable dependence into risk assessments that use Dempster-Shafer theory or probability bounds analysis to address epistemic and aleatory uncertainty. The report reviews techniques for simulating correlated variates for a given correlation measure and dependence model, computation of bounds on distribution functions under a specified dependence model, formulation of parametric and empirical dependence models, and bounding approaches that can be used when information about the intervariable dependence is incomplete. The report also reviews several of the most pervasive and dangerous myths among risk analysts about dependence in probabilistic models.
Evading Lyth bound in models of quintessential inflation
Quintessential inflation refers to an attempt to unify inflation and late-time cosmic acceleration using a single scalar field. In this letter we consider two different classes of quintessential inflation, one of which is based upon a Lagrangian with non-canonical kinetic term k2(ϕ)∂μϕ∂μϕ and a steep exponential potential while the second class uses the concept of steep brane world inflation. We show that in both cases the Lyth bound can be evaded, despite the large tensor-to-scalar ratio of perturbations. The post-inflationary dynamics is consistent with nucleosynthesis constraint in these cases
Mixed and Mixture Regression Models for Continuous Bounded Responses Using the Beta Distribution
Verkuilen, Jay; Smithson, Michael
2012-01-01
Doubly bounded continuous data are common in the social and behavioral sciences. Examples include judged probabilities, confidence ratings, derived proportions such as percent time on task, and bounded scale scores. Dependent variables of this kind are often difficult to analyze using normal theory models because their distributions may be quite…
Model of bound interface dynamics for coupled magnetic domain walls
Politi, P.; Metaxas, P. J.; Jamet, J.-P.; Stamps, R. L.; Ferré, J.
2011-08-01
A domain wall in a ferromagnetic system will move under the action of an external magnetic field. Ultrathin Co layers sandwiched between Pt have been shown to be a suitable experimental realization of a weakly disordered 2D medium in which to study the dynamics of 1D interfaces (magnetic domain walls). The behavior of these systems is encapsulated in the velocity-field response v(H) of the domain walls. In a recent paper [P. J. Metaxas , Phys. Rev. Lett.PRLTAO0031-900710.1103/PhysRevLett.104.237206 104, 237206 (2010)] we studied the effect of ferromagnetic coupling between two such ultrathin layers, each exhibiting different v(H) characteristics. The main result was the existence of bound states over finite-width field ranges, wherein walls in the two layers moved together at the same speed. Here we discuss in detail the theory of domain wall dynamics in coupled systems. In particular, we show that a bound creep state is expected for vanishing H and we give the analytical, parameter free expression for its velocity which agrees well with experimental results.
Gluino bounds: Simplified Models vs a Particular SO(10) Model (A Snowmass white paper)
Anandakrishnan, Archana; Raby, Stuart; Wingerter, Akin
2013-01-01
We consider the results from the first run of LHC studied in the context of simplified models and re-interpret them for a particular SO(10) model with a non-simplified topology. Hadronic searches have been designed to obtain the best sensitivity for the simplified models. They require multiple b-jets in the final state. But we show that the bounds obtained from these searches are weaker in the case of the particular model studied here, since there are fewer b-jets.
Relevance of the ICRP biokinetic model for dietary organically bound tritium
Ingested dietary tritium can participate in metabolic processes, and become synthesized into organically bound tritium in the tissues and organs. The distribution and retention of the organically bound tritium throughout the body are much different than tritium in the body water. The International Commission on Radiological Protection (ICRP) Publication 56 (1989) has a biokinetic model to calculate dose from the ingestion of organically bound dietary tritium. The model predicts that the dose from the ingestion of organically bound dietary tritium is about 2.3 times higher than from the ingestion of the same activity of tritiated water. Under steady-state conditions, the calculated dose rate (using the first principle approach) from the ingestion of dietary organically bound tritium can be twice that from the ingestion of tritiated water. For an adult, the upper-bound dose estimate for the ingestion of dietary organically bound tritium is estimated to be close to 2.3 times higher than that of tritiated water. Therefore, given the uncertainty in the dose calculation with respect to the actual relevant dose, the ICRP biokinetic model for organically bound tritium is sufficient for dosimetry for adults. (author)
Electrostatic self-energy and Bekenstein entropy bound in the massive Schwinger model
Sadjadi, H M
2005-01-01
We obtain the electrostatic energy of two opposite charges near the horizon of stationary black-holes in the massive Schwinger model. Besides the confining aspects of the model, we discuss the Bekenstein entropy upper bound of a charged object using the generalized second law. We show that despite the massless case, in the massive Schwinger model the entropy of the black hole and consequently the Bekenstein bound are altered by the vacuum polarization.
A heterogeneous boundedly rational expectation model for housing market
Andrew Y. T. LEUNG; Jia-na XU; Wing Shum TSUI
2009-01-01
This research aims to test the housing price dynamics when considering heterogeneous boundedly rational expectations such as naive expectation, adaptive expectation and biased belief. The housing market is investigated as an evolutionary system with heterogeneous and competing expectations. The results show that the dynamics of the expected housing price varies substantially when heterogeneous expectations are considered together with some other endogenous factors. Simulation results explain some stylized phenomena such as equilibrium or oscillation, convergence or divergence, and over-shooting or under-shooting. Furthermore, the results suggest that variation of the proportion of groups of agents is basically dependent on the selected strategies. It also indicates that control policies should be chosen carefully in consistence with a unique real estate market during a unique period since certain parameter portfolio may increase or suppress oscillation.
A practical approach to model checking Duration Calculus using Presburger Arithmetic
Hansen, Michael Reichhardt; Dung, Phan Anh; Brekling, Aske Wiid
upper bound. The generated Presburger formulas have a rich Boolean structure, many quantifiers and quantifier alternations. Such formulas are simplified using so-called guarded formulas, where a guard provides a context used to simplify the rest of the formula. A normal form for guarded formulas...
Tools for model-independent bounds in direct dark matter searches
Del Nobile, Eugenio; Panci, Paolo
2013-01-01
We discuss a framework (based on non-relativistic operators) and a self-contained set of numerical tools to derive the bounds from some current direct detection experiments on any arbitrary model of Dark Matter.
Upper Higgs boson mass bounds from a chirally invariant lattice Higgs-Yukawa Model
Gerhold, P. [Humboldt-Universitaet, Berlin (Germany). Inst. fuer Physik; John von Neumann-Institut fuer Computing NIC/DESY, Zeuthen (Germany); Jansen, K. [John von Neumann-Institut fuer Computing NIC/DESY, Zeuthen (Germany)
2010-02-15
We establish the cutoff-dependent upper Higgs boson mass bound by means of direct lattice computations in the framework of a chirally invariant lattice Higgs-Yukawa model emulating the same chiral Yukawa coupling structure as in the Higgs-fermion sector of the Standard Model. As expected from the triviality picture of the Higgs sector, we observe the upper mass bound to decrease with rising cutoff parameter {lambda}. Moreover, the strength of the fermionic contribution to the upper mass bound is explored by comparing to the corresponding analysis in the pure {phi}{sup 4}-theory. (orig.)