In this paper we present an approach for modelling functional procedures (as they occur in imperative programming languages) in a weakest precondition framework. Functional procedures are called inside expressions, bu...
详细信息
We tackle the problem of verifying correctness properties on an HDL implementation of a system-on-chip bus-based integration architecture. the bus architecture is characterized by a 2-level arbitration scheme and the ...
详细信息
We tackle the problem of verifying correctness properties on an HDL implementation of a system-on-chip bus-based integration architecture. the bus architecture is characterized by a 2-level arbitration scheme and the absence of a centralized controller. Checking correctness properties on an implementation can be hard because it is common for an implementation to contain constructs which are difficult to capture using a synchronous FSM model. the hard part in our case is that for performance reasons the second-level arbitration is based on a token-ring protocol implemented as a novel combinational loop. While the combinational loop is non-inverting, there is no acyclic implementation which can mimic its functionality. Our contribution has been to show how the combinational loop, and hence the arbitration scheme, can be modeled by means of mechanical transformations of the implementation model. We model check a 4-client base case implementation followed by an inductive argument for the correctness of an n-client implementation. Our approach including the combinational loop modeling and the inductive proof technique has general application to other similar protocols. Our verification methodology involved checking a Verilog implementation for desired properties using symbolic model checking in the VIS system from UC Berkeley. Checking properties on the base case required negligible amount of CPU resources. While there have been a number of formal verification case studies, we do not believe that any previous work has proposed a general purpose technique for modeling combinational loops.
the proceedings contain 41 papers. the special focus in this conference is on Verification, Temporal logic, Lambda Calculus, Linear logic and Descriptive Complexity. the topics include: Topological queries in spatial ...
ISBN:
(纸本)3540665366
the proceedings contain 41 papers. the special focus in this conference is on Verification, Temporal logic, Lambda Calculus, Linear logic and Descriptive Complexity. the topics include: Topological queries in spatial databases;constraint-based analysis of broadcast protocols;applicative control and computational complexity;applying rewriting techniques to the verification of erlang processes;an expressively complete temporal logic without past tense operators for mazurkiewicz traces;using fields and explicit substitutions to implement objects and functions in a de bruijn setting;a linear logical view of linear type isomorphisms;choice logic programs and Nash equilibria in strategic games;resolution method for modal logic with well-founded frames;fixpoint alternation and the game quantifier;open least element principle and bounded query computation;anti-symmetry of higher-order subtyping;monadic presentations of lambda terms using generalized inductive types;a logical viewpoint on process-algebraic quotients;data-refinement for call-by value programming languages and interactive theorem proving using type theory.
We explain why the original proofs of P-Time completeness for Light Affine logic and Light Linear logic can not work, and we fully develop a working one.
ISBN:
(纸本)3540665366
We explain why the original proofs of P-Time completeness for Light Affine logic and Light Linear logic can not work, and we fully develop a working one.
We present a definition of untyped lambda -terms using a heterogeneous datatype, i.e. an inductively defined operator. this operator can be extended to a Kleish triple, which is a concise way to verify the substitutio...
详细信息
ISBN:
(纸本)3540665366
We present a definition of untyped lambda -terms using a heterogeneous datatype, i.e. an inductively defined operator. this operator can be extended to a Kleish triple, which is a concise way to verify the substitution laws for lambda -calculus. We also observe that repetitions in the definition of the monad as well as in the proofs can be avoided by using well-founded recursion and induction instead of structural induction. We extend the construction to the simply typed lambda -calculus using dependent types, and show that this is an instance of a generalization of Kleish triples. the proofs for the untyped case have been checked using the LEGO system.
We give a category theoretic framework for data-refinement in call-by-value programming languages. One approach to data refinement for the simply typed lambda -calculus is given by generalising the notion of logical r...
详细信息
ISBN:
(纸本)3540665366
We give a category theoretic framework for data-refinement in call-by-value programming languages. One approach to data refinement for the simply typed lambda -calculus is given by generalising the notion of logical relation to one of lax logical relation, so that binary lax logical relations compose. So here, we generalise the notion of lax logical relation, defined in category theoretic terms, from the simply typed lambda -calculus to the computational lambda -calculus as a model of data refinement.
this paper represents the beginning of a study aimed at devising semantic models for true concurrency that provide clear distinctions between concurrency, paxallelism and choice. We present a simple programming langua...
详细信息
ISBN:
(纸本)3540665366
this paper represents the beginning of a study aimed at devising semantic models for true concurrency that provide clear distinctions between concurrency, paxallelism and choice. We present a simple programming language which includes (weakly) sequential composition, asynchronous and synchronous parallel composition, a restriction operator, and that supports recursion. We develop an operational and a denotational semantics for this language, and we obtain a theorem relating the behavior of a process as described by the transition system to the meaning of the process in the denotational model. this implies that the denotational model is adequate with respect to the operational model. Our denotational model is based on the resource traces of Gastin and Teodesiu, and since a single resource trace represents all possible executions of a concurrent process, we axe able to model each term of our concurrent language by a single trace. therefore we obtain a deterministic semantics for our language and we axe able to model parallelism without introducing nondeterminism.
the program committee of the 13th European conference on Artificial Intelligence has accepted 15 papers in the field of machine learning from seven countries: France (3), Germany (1), Japan (1), Italy (3), the Netherl...
详细信息
the program committee of the 13th European conference on Artificial Intelligence has accepted 15 papers in the field of machine learning from seven countries: France (3), Germany (1), Japan (1), Italy (3), the Netherlands (1), Slovenia (3) and the United Kingdom (3). the papers cover almost all important sub-areas of machine learning such as, concept learning (2), decision-tree learning (2), inductivelogicprogramming (5), instance-based learning (1), artificial neural networks (2), bayesian learning (1), and learning in multiagent systems (2). Most of the papers represent extensions of the existing machine learning techniques towards more practical applications. this is a positive sign in comparison withthe previous ECAI conference and it reflects the basic stream of machine learning research.
Withthe advance of research, design and operation of flexible manufacturing systems (FMS), new requirements have been presented for FMS simulators. these new requirements are high modelling efficiency, high model val...
详细信息
Withthe advance of research, design and operation of flexible manufacturing systems (FMS), new requirements have been presented for FMS simulators. these new requirements are high modelling efficiency, high model validity and credibility, more user-friendly features, real control and scheduling logic similar to a real FMS, and effective and correct analysis of results, etc. In this paper, a new FMS simulator (FMSSIM) based an object-oriented-programming (OOP) and some new techniques is introduced. the new techniques include: (i) fully interactive graphical modelling technique, with which the simulation modelling only needs 2-4 h to complete and thp model data are highly consistent and accurate;(ii) real FMS-like simulation control and scheduling, with which various control and scheduling algorithms such as Al-based heuristic scheduling can be easily implemented;(iii) the Intelligent Evaluator, with which the efficiency and accuracy of the evaluation process can be improved. Practical use has shown that the FMSSIM has a good performance in modelling, operation and evaluation. meeting the new requirements for a modern FMS simulator. (C) 1998 Elsevier Science S.A. All rights reserved.
the ever-rising expectations of customers regarding quality and diversity of products require new products to be launched with a minimum of upheaval and consequently rapid, defect-free and economical processes. these ...
详细信息
the ever-rising expectations of customers regarding quality and diversity of products require new products to be launched with a minimum of upheaval and consequently rapid, defect-free and economical processes. these goals can be attained and guaranteed in the planning departments of businesses through the sharing of secure and up-to-date planning data. leading to a high degree of flexibility and a minimum of interruptions in the production processes. In terms of technology planning, this results in a demand for economic methods of planning and NC programming, leading in turn to continuous, systematic acquisition of specialised in-house technological knowledge. However, most of the applications on the market are unsatisfactory in terms of acquisition of specialised knowledge of technology, only allowing specialised planning knowledge to be gathered or entered through costly procedures and for it to be organised statically. For rational processing and evaluation of planning knowledge, it is therefore sensible to systematically record technological discoveries made in the course of the planning and running-in process and to make them available for future planning processes. this processing of empirical knowledge along with rational and safe technology planning is supported by the use of DP systems, thus enabling planning knowledge to be kept constantly up-to-date, growing along withthe data specific to the enterprise, Fur this purpose, a suitable information model must be devised that represents the integration point within the NC process chain. Using a feature-based product model introduced in the design departments as a starting point, the model is extended to take in a production-orientated view. the model should be designed in such a way that, above all, the technological interconnections are represented and that the technology planning, NC programming and running-in process are integrated through the model. In order to evaluate and process empirical knowledge? m
暂无评论