Finite-state methods are the most efficient mechanisms for analysing textual and symbolic data, providing elegant solutions for an immense number of practical problems in computational linguistics and computerscience...
详细信息
ISBN:
(纸本)9781108756945
Finite-state methods are the most efficient mechanisms for analysing textual and symbolic data, providing elegant solutions for an immense number of practical problems in computational linguistics and computerscience. This book for graduate students and researchers gives a complete coverage of the field, starting from a conceptual introduction and building to advanced topics and applications. The central finite-state technologies are introduced with mathematical rigour, ranging from simple finite-state automata to transducers and bimachines as 'input-output' devices. Special attention is given to the rich possibilities of simplifying, transforming and combining finite-state devices. All algorithms presented are accompanied by full correctness proofs and executable source code in a new programming language, C(M), which focuses on transparency of steps and simplicity of code. Thus, by enabling readers to obtain a deep formal understanding of the subject and to put finite-state methods to real use, this book closes the gap between theory and practice.
This comprehensive text provides a modern and technically precise exposition of the fundamental theory and applications of temporal logics in computerscience. Part I presents the basics of discrete transition systems...
详细信息
ISBN:
(纸本)9781107028364
This comprehensive text provides a modern and technically precise exposition of the fundamental theory and applications of temporal logics in computerscience. Part I presents the basics of discrete transition systems, including constructions and behavioural equivalences. Part II examines the most important temporal logics for transition systems and Part III looks at their expressiveness and complexity. Finally, Part IV describes the main computational methods and decision procedures for model checking and model building - based on tableaux, automata and games - and discusses their relationships. The book contains a wealth of examples and exercises, as well as an extensive annotated bibliography. Thus, the book is not only a solid professional reference for researchers in the field but also a comprehensive graduate textbook that can be used for self-study as well as for teaching courses.
Nominal sets provide a promising new mathematical analysis of names in formal languages based upon symmetry, with many applications to the syntax and semantics of programming language constructs that involve binding, ...
详细信息
ISBN:
(数字)9781107240186
ISBN:
(纸本)9781107017788
Nominal sets provide a promising new mathematical analysis of names in formal languages based upon symmetry, with many applications to the syntax and semantics of programming language constructs that involve binding, or localising names. Part I provides an introduction to the basic theory of nominal sets. In Part II, the author surveys some of the applications that have developed in programming language semantics (both operational and denotational), functional programming and logic programming. As the first book to give a detailed account of the theory of nominal sets, it will be welcomed by researchers and graduate students in theoreticalcomputerscience.
Coinduction is a method for specifying and reasoning about infinite data types and automata with infinite behaviour. In recent years, it has come to play an ever more important role in the theory of computing. It is s...
详细信息
ISBN:
(数字)9781316963289
ISBN:
(纸本)9781107004979
Coinduction is a method for specifying and reasoning about infinite data types and automata with infinite behaviour. In recent years, it has come to play an ever more important role in the theory of computing. It is studied in many disciplines, including process theory and concurrency, modal logic and automata theory. Typically, coinductive proofs demonstrate the equivalence of two objects by constructing a suitable bisimulation relation between them. This collection of surveys is aimed at both researchers and Master's students in computerscience and mathematics and deals with various aspects of bisimulation and coinduction, with an emphasis on process theory. Seven chapters cover the following topics: history, algebra and coalgebra, algorithmics, logic, higher-order languages, enhancements of the bisimulation proof method, and probabilities. Exercises are also included to help the reader master new material.
This book discusses the connection between two areas of semantics, namely the semantics of databases and the semantics of natural language, and links them via a common view of the semantics of time. It is argued that ...
ISBN:
(纸本)9780511874345
This book discusses the connection between two areas of semantics, namely the semantics of databases and the semantics of natural language, and links them via a common view of the semantics of time. It is argued that a coherent theory of the semantics of time is an essential ingredient for the success of efforts to incorporate more 'real world' semantics into database models. This idea is a relatively recent concern of database research but it is receiving growing interest. The book begins with a discussion of database querying which motivates the use of the paradigm of Montague Semantics and discusses the details of the intensional logic ILs. This is followed by a description of the author's own model, the Historical Relational Data Model (HRDM) which extends the RDM to include a temporal dimension. Finally the database querying language QEHIII is defined and examples illustrate its use. A formal model for the interpretation of questions is presented in this work which will form the basis for much further research.
This 1993 book shows how formal logic can be used to specify the behaviour of hardware designs and reason about their correctness. A primary theme of the book is the use of abstraction in hardware specification and ve...
详细信息
ISBN:
(纸本)9780521115322
This 1993 book shows how formal logic can be used to specify the behaviour of hardware designs and reason about their correctness. A primary theme of the book is the use of abstraction in hardware specification and verification. The author describes how certain fundamental abstraction mechanisms for hardware verification can be formalised in logic and used to express assertions about design correctness and the relative accuracy of models of hardware behaviour. His approach is pragmatic and driven by examples. He also includes an introduction to higher-order logic, which is a widely used formalism in this subject, and describes how that formalism is actually used for hardware verification. The book is based in part on the author's own research as well as on graduate teaching. Thus it can be used to accompany courses on hardware verification and as a resource for research workers.
Process algebra is a widely accepted and much used technique in the specification and verification of parallel and distributed software systems. This book sets the standard for the field. It assembles the relevant res...
详细信息
ISBN:
(数字)9780511717420
ISBN:
(纸本)9780521820493
Process algebra is a widely accepted and much used technique in the specification and verification of parallel and distributed software systems. This book sets the standard for the field. It assembles the relevant results of most process algebras currently in use, and presents them in a unified framework and notation. The authors describe the theory underlying the development, realization and maintenance of software that occurs in parallel or distributed systems. A system can be specified in the syntax provided, and the axioms can be used to verify that a composed system has the required external behaviour. As examples, two protocols are completely specified and verified in the text: the Alternating-Bit Protocol for Data Communication, and Fischer's Protocol of Mutual Exclusion. The book serves as a reference text for researchers and graduate students in computerscience, offering a complete overview of the field and referring to further literature where appropriate.
暂无评论