A comprehensive introduction to interval logic and duration calculus for modelling, analysing and verifying real-time systems. The Duration Calculus (DC) represents a logical approach to formal design of real-time systems. In DC real numbers are used to model time and Boolean-valued (i.e. {0,1}-valued) functions over time to model states of real-time systems. The duration of a state in a time interval is the accumulated presence time of the state in the interval. DC extends interval logic to a calculus to specify and reason about properties of state durations. The text covers theory (completeness, decidability, undecidability, model-checking), results, as well as case studies (Deadline Driven Scheduler).
This book presents thoroughly revised tutorial papers based on lectures given by leading researchers at the International Training School on Domain Modeling and the Duration Calculus, held in Shanghai, China, as an associated event of ICTAC 2007. Topics addressed in detail are: development of real-time systems, domain engineering using abstract modeling, the area of duration calculus, and formal methods like language description using the operational semantics approach.
This volume comprises the papers selected for presentation at the international conference on Formal Methods in Programming and Their Applications, held in Academgorodok, Novosibirsk, Russia, June-July 1993. The conference was organized by the Institute of Informatics Systems of the Siberian Division of the Russian Academy of Sciences and was the first forum organized by the Institute which was entirely dedicated to formal methods. The main scientific tracks of the conference were centered around formal methods of program development and program construction. The papers in the book are grouped into the following parts: - formal semantics methods - algebraic specification methods - semantic program analysis and abstract interpretation - semantics of parallelism - logic of programs - software specification and verification - transformational development and program synthesis.
In this book the author explains domain engineering and the underlying science, and he then shows how we can derive requirements prescriptions for computing systems from domain descriptions. A further motivation is to present domain descriptions, requirements prescriptions, and software design specifications as mathematical quantities. The author's maxim is that before software can be designed we must understand its requirements, and before requirements can be prescribed we must analyse and describe the domain for which the software is intended. He does this by focusing on what it takes to analyse and describe domains. By a domain we understand a rationally describable discrete dynamics segment of human activity, of natural and man-made artefacts, examples include road, rail and air transport, container terminal ports, manufacturing, trade, healthcare, and urban planning. The book addresses issues of seemingly large systems, not small algorithms, and it emphasizes descriptions as formal, mathematical quantities. This is the first thorough monograph treatment of the new software engineering phase of software development, one that precedes requirements engineering. It emphasizes a methodological approach by treating, in depth, analysis and description principles, techniques and tools. It does this by basing its domain modeling on fundamental philosophical principles, a view that is new for a computer science monograph. The book will be of value to computer scientists engaged with formal specifications of software. The author reveals this as a field of interesting problems, most chapters include pointers to further study and exercises drawn from practical engineering and science challenges. The text is supported by a primer to the formal specification language RSL and extensive indexes.
This book constitutes the refereed proceedings of the International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2002, held in Copenhagen, Denmark, in July/August 2002. The 20 revised full papers and two system descriptions presented together with two invited contributions were carefully reviewed and selected for inclusion in the book. All current issues surrounding the mechanization of logical reasoning with tableaux and similar methods are addressed. Among the logic calculi investigated are linear logic, temporal logic, modal logics, hybrid logic, multi-modal logics, fuzzy logics, Goedel logic, Lukasiewicz logic, intermediate logics, quantified boolean logic, and, of course, classical first-order logic.
This book constitutes the refereed proceedings of the 5th International Colloquium on Theoretical Aspects of Computing, ICTAC 2008 held in Istanbul, Turkey in September 2008. The 27 revised full papers were carefully reviewed and selected from over 70 submissions. The aim of the colloquium is to bring together practitioners and researchers from academia, industry and government to present research results, and exchange experience, ideas, and solutions for their problems in theoretical aspects of computing such as automata theory and formal languages, principles and semantics of programming languages, software architectures and their description languages, software specification, refinement, and verification, model checking and theorem proving, real-time, embedded and hybrid systems, theory of parallel, distributed, and internet-based (grid) computing, simulation and modeling, and service-oriented development.
This volume contains the proceedings of CHARME 2001, the Eleventh Advanced Research Working Conference on Correct Hardware Design and Veri?cation Methods. CHARME 2001 is the 11th in a series of working conferences devoted to the development and use of leading-edge formal techniques and tools for the design and veri?cation of hardware and hardware-like systems. Previous events in the ‘CHARME’ series were held in Bad Herrenalb (1999), Montreal (1997), Frankfurt (1995), Arles (1993), and Torino (1991). This series of meetings has been organized in cooperation with IFIP WG 10.5 and WG 10.2. Prior meetings, stretching backto the earliest days of formal hardware veri?cation, were held under various names in Miami (1990), Leuven (1989), Glasgow (1988), Grenoble (1986), Edinburgh (1985), and Darmstadt (1984). The convention is now well-established whereby the European CHARME conference alternates with its biennial counterpart, the International Conference on Formal Methods in Computer-Aided Design (FMCAD), which is held on even-numbered years in the USA. The conference tookplace during 4–7 September 2001 at the Institute for System Level Integration in Livingston, Scotland. It was co-hosted by the - stitute and the Department of Computing Science of Glasgow University and co-sponsored by the IFIP TC10/WG10.5 Working Group on Design and En- neering of Electronic Systems. CHARME 2001 also included a scienti?c session and social program held jointly with the 14th International Conference on Th- rem Proving in Higher Order Logics (TPHOLs), which was co-located in nearby Edinburgh.
This book originates from the International Symposium on Compositionality, COMPOS'97, held in Bad Malente, Germany in September 1997. The 25 chapters presented in revised full version reflect the current state of the art in the area of compositional reasoning about concurrency. The book is a valuable reference for researchers and professionals interested in formal systems design and analysis; it also is well suited for self study and use in advanced courses.
This book is the proceedings of the Structures in Concurrency Theory workshop (STRICT) that was held from 11 th to l3th May 1995 in Berlin, Germany. It includes three invited contributions - by J. de Bakker, E. Best et aI, and E. R. Olderog and M. Schenke - and all papers which were submitted and accepted for presentation. Concurrency Theory deals with formal aspects of concurrent systems. It uses partly competing and partly complementary formalisms and structures. The aim of this workshop was to present and compare different formalisms and results in Concurrency Theory. STRICT was organized by the Humboldt-University Berlin and the ESPRIT Basic Research Working Group CALIBAN. Original papers had been sought from all scientists in the field of Concurrency Theory. The Programme Committee selected twenty contributions with various different topics, including Petri Nets, Process Algebras, Distributed Algorithms, Formal Semantics, and others. I am grateful to the Programme Committee and to the other referees for the careful evaluation of the submitted papers.