How can we be certain that software is reliable? Is there any method that can verify the correctness of software for all cases of interest? Computer scientists and software engineers have informally assumed that there is no fully general solution to the verification problem. In this paper, we survey approaches to the problem of software verification and offer a new proof for why there can be no general solution.

How can we be certain that software is reliable? Is there any method that can verify the correctness of software for all cases of interest? Computer scientists and software engineers have informally assumed that there is no fully general solution to the verification problem. In this paper, we survey approaches to the problem of software verification and offer a new proof for why there can be no general solution.

in Oct-14-1998 ordinance INDESP-IO4 established the federal software certification and verification requirements for gaming machines in Brazil. The authors present the rationale behind these criteria, whose basic principles can find applications in several other software authentication applications.

Questions concerning the epistemological status of computer science are, in this paper, answered from the point of view of the formal verification framework. State space reduction techniques adopted to simplify computational models in model checking are analysed in terms of Aristotelian abstractions and Galilean idealizations characterizing the inquiry of empirical systems. Methodological considerations drawn here are employed to argue in favour of the scientific understanding of computer science as a discipline. Specifically, reduced models gained by Dataion are acknowledged as (...) Aristotelian abstractions that include only data which are sufficient to examine the interested executions. The present study highlights how the need to maximize incompatible properties is at the basis of both Abstraction Refinement, the process of generating a cascade of computational models to achieve a balance between simplicity and informativeness, and the Multiple Model Idealization approach in biology. Finally, fairness constraints, imposed to computational models to allow fair behaviours only, are defined as ceteris paribus conditions under which temporal formulas, formalizing software requirements, acquire the status of law-like statements about the software systems executions. (shrink)

Various errors can affect scientific code and detecting them is a central concern within computational science. Could formal verification methods, which are now available tools, be widely adopted to guarantee the general reliability of scientific code? After discussing their benefits and drawbacks, we claim that, absent significant changes as regards features like their user-friendliness and versatility, these methods are unlikely to be adopted throughout computational science, beyond certain specific contexts for which they are well-suited. This issue exemplifies the epistemological (...) heterogeneity of computational science: profoundly different practices can be appropriate to meet the reliability challenge that rises for scientific code. (shrink)

Various errors can affect scientific code and detecting them is a central concern within computational science. Could formal verification methods, which are now available tools, be widely adopted to guarantee the general reliability of scientific code? After discussing their benefits and drawbacks, we claim that, absent significant changes as regards features like their user-friendliness and versatility, these methods are unlikely to be adopted throughout computational science, beyond certain specific contexts for which they are well-suited. This issue exemplifies the epistemological (...) heterogeneity of computational science: profoundly different practices can be appropriate to meet the reliability challenge that rises for scientific code. (shrink)

A proof of ‘correctness’ for a mathematical algorithm cannot be relevant to executions of a program based on that algorithm because both the algorithm and the proof are based on assumptions that do not hold for computations carried out by real-world computers. Thus, proving the ‘correctness’ of an algorithm cannot establish the trustworthiness of programs based on that algorithm. Despite the (deceptive) sameness of the notations used to represent them, the transformation of an algorithm into an executable program is a (...) wrenching metamorphosis that changes a mathematical abstraction into a prescription for concrete actions to be taken by real computers. Therefore, it is verification of program executions (processes) that is needed, not of program texts that are merely the scripts for those processes. In this view, verification is the empirical investigation of: (a) the behavior that programs invoke in a computer system and (b) the larger context in which that behavior occurs. Here, deduction can play no more, and no less, a role than it does in the empirical sciences. (shrink)

A debate over the theoretical capabilities of formal methods in computer science has raged for more than two years now. The function of this paper is to summarize the key elements of this debate and to respond to important criticisms others have advanced by placing these issues within a broader context of philosophical considerations about the nature of hardware and of software and about the kinds of knowledge that we have the capacity to acquire concerning their performance.

The issue of proper functioning of operative computing and the utility of program verification, both in general and of specific methods, has been discussed a lot. In many of those discussions, attempts have been made to take mathematics as a model of knowledge and certitude achieving, and accordingly infer about the suitable ways to handle computing. I shortly review three approaches to the subject, and then take a stance by considering social factors which affect the epistemic status of both (...) mathematics and computing. I use the analogy between mathematics and computing in reverse—that is to say, I consider operative computing as a form of making mathematics, and so attempt to learn from computing to mathematics in general. I conclude that mathematics engineering is a field to be both developed for practical improvement of doing mathematics and taken into consideration while philosophizing about mathematics as well. (shrink)

The philosophy of mathematics has long been concerned with deter- mining the means that are appropriate for justifying claims of mathemat- ical knowledge, and the metaphysical considerations that render them so. But, as of late, many philosophers have called attention to the fact that a much broader range of normative judgments arise in ordinary math- ematical practice; for example, questions can be interesting, theorems important, proofs explanatory, concepts powerful, and so on. The as- sociated values are often loosely classied as (...) aspects of \mathematical understanding." Meanwhile, in a branch of computer science known as \formal ver- ication," the practice of interactive theorem proving has given rise to software tools and systems designed to support the development of com- plex formal axiomatic proofs. Such eorts require one to develop models of mathematical language and inference that are more robust than the the simple foundational models of the last century. This essay explores some of the insights that emerge from this work, and some of the ways that these insights can inform, and be informed by, philosophical theories of mathematical understanding. (shrink)

This paper is concerned with the construction of theories of software systems yielding adequate predictions of their target systems’ computations. It is first argued that mathematical theories of programs are not able to provide predictions that are consistent with observed executions. Empirical theories of software systems are here introduced semantically, in terms of a hierarchy of computational models that are supplied by formal methods and testing techniques in computer science. Both deductive top-down and inductive bottom-up approaches in the (...) discovery of semantic software theories are refused to argue in favour of the abductive process of hypothesising and refining models at each level in the hierarchy, until they become satisfactorily predictive. Empirical theories of computational systems are required to be modular, as modular are most software verification and testing activities. We argue that logic relations must be thereby defined among models representing different modules in a semantic theory of a modular software system. We exclude that scientific structuralism is able to define module relations needed in software modular theories. The algebraic Theory of Institutions is finally introduced to specify the logic structure of modular semantic theories of computational systems. (shrink)

This paper provides a review of Raymond Turner’s book Computational Artefacts. Towards a Philosophy of Computer Science. Focus is made on the definition of program correctness as the twofold problem of evaluating whether both the symbolic program and the physical implementation satisfy a set of specifications. The review stresses how these are not two separate problems. First, it is highlighted how formal proofs of correctness need to rely on the analysis of physical computational processes. Secondly, it is underlined how (...) class='Hi'>software testing requires considering the formal relations holding between the specifications and the symbolic program. Such a mutual dependency between formal and empirical program verification methods is finally shown to influence the debate on the epistemological status of computer science. (shrink)

An important perquisite for verification of the correctness of software is the ability to write mathematically precise documents that can be read by practitioners and advanced users. Without such documents, we won't know what properties we should verify. Tabular expressions, in which predicate expressions may appear, have been found useful for this purpose. We frequently use partial functions in our tabular documentation. Conventional interpretations of expressions that describe predicates are not appropriate for our application because they do not (...) deal with partial functions. Experience with this documentation has led us to choose a logic in which predicates are total but functions remain partial. We have found that this particular interpretation results in simpler expressions and is easily understood by practitioners. (shrink)

Production systems are one of the most widely used models of knowledge representation and application. They have demonstrated their success as a software technology for solving ill-structured problems.Though they have been implemented successfully in many domains, building these systems is a challenging task because of the ill-defined nature of the applications and the novel nature of the technology. Since the architecture of production systems is dissimilar to typical procedural software, lots of conventional software evaluation techniques cannot be (...) available easily to them. So, there has been a demand for a practical verification systems which help the knowledge-base designer to develop production systems, and to assure the validity of them. This paper presents two verification systems that can be used to verify the dynamic properties of OPS5, which is the most general production system arguably. One is a system which predicts the sequence of rules that must fire to archieve given specific goal state concerned with a final state or an intermediate state representing a meaningful advancement in reaching a final state. The prediction is performed at compile-time, only with static informations and a set of declarations for the objective goal state. This system can generate the information to determine whether the manner in which the developed production system will pursue given goal state at run-time is valid according to the specifications and expectations of the knowledge-base designer. The other is a system which automatically detects some exceptions which may occur at run-time by using meta-knowledges. Meta-knowledges are constructed by the knowledge-base designer in conjunction with the domain expert implicitly. They represent his design or semantic specification of the knowledge-base, such as valid range of attribute values, range of attribute values requested by the knowledge-base and unexpected inconsistent states. This system is implemented additionally to OPS5 framework. The detection is performed at run-time and is taken in every inference-cycle. By introducing both of two systems described in the above into the development process of production systems, the costs of the knowledge-base designer are reduced, and it becomes possible that to some extentreliability is guaranteed in the system which was finally completed. (shrink)

Quantum computing is of high interest because it promises to perform at least some kinds of computations much faster than classical computers. Arute et al. 2019 (informally, “the Google Quantum Team”) report the results of experiments that purport to demonstrate “quantum supremacy” – the claim that the performance of some quantum computers is better than that of classical computers on some problems. Do these results close the debate over quantum supremacy? We argue that they do not. In the following, we (...) provide an overview of the Google Quantum Team’s experiments, then identify some open questions in the quest to demonstrate quantum supremacy. (shrink)

To assess the prevalence of plagiarism in manuscripts submitted for publication in the Croatian Medical Journal (CMJ). All manuscripts submitted in 2009–2010 were analyzed using plagiarism detection software: eTBLAST , CrossCheck, and WCopyfind . Plagiarism was suspected in manuscripts with more than 10% of the text derived from other sources. These manuscripts were checked against the Déjà vu database and manually verified by investigators. Of 754 submitted manuscripts, 105 (14%) were identified by the software as suspicious of plagiarism. (...) Manual verification confirmed that 85 (11%) manuscripts were plagiarized: 63 (8%) were true plagiarism and 22 (3%) were self-plagiarism. Plagiarized manuscripts were mostly submitted from China (21%), Croatia (14%), and Turkey (19%). There was no significant difference in the text similarity rate between plagiarized and self-plagiarized manuscripts (25% [95% CI 22–27%] vs. 28% [95% CI 20–33%]; U = 645.50; P = 0.634). Differences in text similarity rate were found between various sections of self-plagiarized manuscripts (H = 12.65, P = 0.013). The plagiarism rate in the Materials and Methods (61% (95% CI 41–68%) was higher than in the Results (23% [95% CI 17–36%], U = 33.50; P = 0.009) or Discussion (25.5 [95% CI 15–35%]; U = 57.50; P < 0.001) sections. Three authors were identified in the Déjà vu database. Plagiarism detection software combined with manual verification may be used to detect plagiarized manuscripts and prevent their publication. The prevalence of plagiarized manuscripts submitted to the CMJ , a journal dedicated to promoting research integrity, was 11% in the 2-year period 2009–2010. (shrink)

This book constitutes the refereed proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, held in Ann Arbor, MI, USA in June 2011.The 25 revised full papers presented together with ...

Formal verification involves the use of logical and computational methods to establish claims that are expressed in precise mathematical terms. These can include ordinary mathematical theorems, as well as claims that pieces of hardware or software, network protocols, and mechanical and hybrid systems meet their specifications. In practice, there is not a sharp distinction between verifying a piece of mathematics and verifying the correctness of a system: formal verification requires describing hardware and software systems in mathematical (...) terms, at which point establishing claims as to their correctness becomes a form of theorem proving. Conversely, the proof of a mathematical theorem may require a lengthy computation, in which case verifying the truth of the theorem requires verifying that the computation does what it is supposed to do. The gold standard for supporting a mathematical claim is to provide a proof, and twentieth-century developments in logic show most if not all conventional proof methods can be reduced to a small set of axioms and rules in any of a number of foundational systems. With this reduction, there are two ways that a computer can help establish a claim: it can help find a proof in the first place, and it can help verify that a purported proof is correct. Automated theorem proving focuses on the “finding” aspect. Resolution theorem provers, tableau theorem provers, fast satisfiability solvers, and so on provide means of establishing the validity of formulas in propositional and first-order logic. Other systems provide search procedures and decision procedures for specific languages and domains, such as linear or nonlinear expressions over the integers or the real numbers. Architectures like SMT combine domain-general search methods with domain-specific procedures. Computer algebra systems and specialized mathematical software packages provide means of carrying out mathematical computations, establishing mathematical bounds, or finding mathematical objects. A calculation can be viewed as a proof as well, and these systems, too, help establish mathematical claims. Automated reasoning systems strive for power and efficiency, often at the expense of guaranteed soundness. Such systems can have bugs, and it can be difficult to ensure that the results they deliver are correct. In contrast, interactive theorem proving focuses on the “verification” aspect of theorem proving, requiring that every claim is supported by a proof in a suitable axiomatic foundation. This sets a very high standard: every rule of inference and every step of a calculation has to be justified by appealing to prior definitions and theorems, all the way down to basic axioms and rules. In fact, most such systems provide fully elaborated “proof objects” that can be communicated to other systems and checked independently. Constructing such proofs typically requires much more input and interaction from users, but it allows us to obtain deeper and more complex proofs. The Lean Theorem Prover aims to bridge the gap between interactive and automated theorem proving, by situating automated tools and methods in a framework that supports user interaction and the construction of fully specified axiomatic proofs. The goal is to support both mathematical reasoning and reasoning about complex systems, and to verify claims in both domains. (shrink)

Connected devices, such as smartphones and tablets, are exposed to a large variety of attacks. Their protection is often challenged by their resource constraints in terms of CPU, memory and energy. Security chains, composed of security functions such as firewalls, intrusion detection systems and data leakage prevention mechanisms, offer new perspectives to protect these devices using software-defined networking and network function virtualization. However, the complexity and dynamics of these chains require new automation techniques to orchestrate them. This chapter describes (...) an automated orchestration methodology for security chains in order to secure connected devices and their applications. This methodology exploits process learning to establish behavioral models and infer security constraints represented as logical predicates. It then generates and merges a set of chains of security functions on the basis of these predicates. These chains are finally compiled into low-level configuration rules and deployed into the network, optimizing for the underlying topology. The benefits and limits of such a methodology combining machine learning and verification techniques are evaluated by a set of experimental results. (shrink)

ArgumentAgent-based social simulations have historically been evaluated using two criteria: verification and validation. This article questions the adequacy of this dual evaluation scheme. It claims that the scheme does not conform to everyday practices of evaluation, and has, over time, fostered a theory-practice gap in the assessment of social simulations. This gap originates because the dual evaluation scheme, inherited from computer science and software engineering, on one hand, overemphasizes the technical and formal aspects of the implementation process and, (...) on the other hand, misrepresents the connection between the conceptual and the computational model. The mismatch between evaluation theory and practice, it is suggested, might be overcome if practitioners of agent-based social simulation adopt a single criterion evaluation scheme in which: i) the technical/formal issues of the implementation process are tackled as a matter of debugging or instrument calibration, and ii) the epistemological issues surrounding the connection between conceptual and computational models are addressed as a matter of validation. (shrink)

The automatic verification of large parts of mathematics has been an aim of many mathematicians from Leibniz to Hilbert. While Gödel's first incompleteness theorem showed that no computer program could automatically prove certain true theorems in mathematics, the advent of electronic computers and sophisticated software means in practice there are many quite effective systems for automated reasoning that can be used for checking mathematical proofs. This book describes the use of a computer program to check the proofs of (...) several celebrated theorems in metamathematics including those of Gödel and Church-Rosser. The computer verification using the Boyer-Moore theorem prover yields precise and rigorous proofs of these difficult theorems. It also demonstrates the range and power of automated proof checking technology. The mechanization of metamathematics itself has important implications for automated reasoning, because metatheorems can be applied as labor-saving devices to simplify proof construction. (shrink)

Although formal system verification has been around for many years, little attention was given to the case where the specification of the system has to be changed. This may occur due to a failure in capturing the clients’ requirements or due to some change in the domain (think for example of banking systems that have to adapt to different taxes being imposed). We are interested in having methods not only to verify properties, but also to suggest how the system (...) model should be changed so that a property would be satisfied. For this purpose, we will use techniques from the area of Belief Revision, that deals with the problem of changing a knowledge base in view of new information. In the last thirty years, several authors have contributed with change operations and ways of characterizing them. However, most of the work concentrates on knowledge bases represented using classical propositional logic. In the last decade, there have been efforts to apply belief revision theory to description and modal logics. In this work, we analyze what is needed for a theory of belief revision which can be applied to the temporal logic, such as the Computation Tree Logic (CTL). In particular, we illustrate different alternatives for formalizing the concept of revision of CTL. Our interest in this particular logic comes both from practical issues, since it is used for software specification, as from theoretical issues, as it is a non-compact logic and most existing results rely on compactness. We focus here on the revision of CTL models and present a characterization result for the revision of partial models. (shrink)

This book constitutes the proceedings of the 17th International Conference, TAP 2023, as part of STAF 2023, a federation of conferences on Software Technologies, Applications and Foundations, which includes two more conferences besides TAP: ICGT (International Conference on Graph Transformations), and ECMFA (European Conference on Modelling Foundations and Applications) in Leicester, UK, in July 2023. The 8 full papers together with 2 short papers included in this volume were carefully reviewed and selected from 14 submissions. They were organized in (...) topical sections on Low-level Code Verification, Formal Models, Model-based test generation, and Abstraction and Refinement. (shrink)

A new approach for defining causality and such related notions as degree of responsibility, degrees of blame, and causal explanation. Causality plays a central role in the way people structure the world; we constantly seek causal explanations for our observations. But what does it even mean that an event C "actually caused" event E? The problem of defining actual causation goes beyond mere philosophical speculation. For example, in many legal arguments, it is precisely what needs to be established in order (...) to determine responsibility. The philosophy literature has been struggling with the problem of defining causality since Hume. In this book, Joseph Halpern explores actual causality, and such related notions as degree of responsibility, degree of blame, and causal explanation. The goal is to arrive at a definition of causality that matches our natural language usage and is helpful, for example, to a jury deciding a legal case, a programmer looking for the line of code that cause some software to fail, or an economist trying to determine whether austerity caused a subsequent depression. Halpern applies and expands an approach to causality that he and Judea Pearl developed, based on structural equations. He carefully formulates a definition of causality, and building on this, defines degree of responsibility, degree of blame, and causal explanation. He concludes by discussing how these ideas can be applied to such practical problems as accountability and program verification. Technical details are generally confined to the final section of each chapter and can be skipped by non-mathematical readers. (shrink)

Cellular Automata, which is a method for analyzing phenomena of complex systems, allows us to construct many kinds of simulators such as road traffic simulators. When we design a CA model, we need a CA simulator for verification of its result. However, at the present, we need to develop a software simulator since CA dedicated computers have not been generalized yet. We need to use a trial and error method with the simulator for design of local rules, which (...) is the main process of making CA models. We have developed an interpreter that makes this process easily. Giving the system a local rule described in a CA dedicated language, the user can instantly confirm the result. When the user change the rules, the system reflects his changes immediately. Our system does not regulate to design the local rules belonging to the CA category because the system is a general purpose CA simulator that adopts the method by description in the special language for definitions of local rules. We can modify a rule dramatically since the system interprets a rule description language in runtime. Furthermore, we can change variable parameters using GUI interfaces. Whereby they iterate to change a rule, a conflictive conditional statement sometimes occurs in a description of local rules. This conflict is far from seeking generally. Our system detects such a conflict automatically and notifies it to users as an error. (shrink)

This introduction to mathematical logic starts with propositional calculus and first-order logic. Topics covered include syntax, semantics, soundness, completeness, independence, normal forms, vertical paths through negation normal formulas, compactness, Smullyan's Unifying Principle, natural deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's Theorem, unification, duality, interpolation, and definability. The last three chapters of the book provide an introduction to type theory (higher-order logic). It is shown how various mathematical concepts can be formalized in this very expressive formal language. This expressive notation facilitates proofs (...) of the classical incompleteness and undecidability theorems which are very elegant and easy to understand. The discussion of semantics makes clear the important distinction between standard and nonstandard models which is so important in understanding puzzling phenomena such as the incompleteness theorems and Skolem's Paradox about countable models of set theory. Some of the numerous exercises require giving formal proofs. A computer program called ETPS which is available from the web facilitates doing and checking such exercises. Audience: This volume will be of interest to mathematicians, computer scientists, and philosophers in universities, as well as to computer scientists in industry who wish to use higher-order logic for hardware and software specification and verification. (shrink)

Higher-Order Logic (HOL) is a proof development system intended for applications to both hardware and software. It is principally used in two ways: for directly proving theorems, and as theorem-proving support for application-specific verification systems. HOL is currently being applied to a wide variety of problems, including the specification and verification of critical systems. Introduction to HOL provides a coherent and self-contained description of HOL containing both a tutorial introduction and most of the material that is needed (...) for day-to-day work with the system. After a quick overview that gives a "hands-on feel" for the way HOL is used, there follows a detailed description of the ML language. The logic that HOL supports and how this logic is embedded in ML, are then described in detail. This is followed by an explanation of the theorem-proving infrastructure provided by HOL. Finally two appendices contain a subset of the reference manual, and an overview of the HOL library, including an example of an actual library documentation. (shrink)

This handbook with exercises reveals the mathematical beauty of formalisms hitherto mostly used for software and hardware design and verification.

One might poetically muse that computers have the essence both of logic and machines. Through the case of the history of Separation Logic, we explore how this assertion is more than idle poetry. Separation Logic works because it merges the software engineer’s conceptual model of a program’s manipulation of computer memory with the logical model that interprets what sentences in the logic are true, and because it has a proof theory which aids in the crucial problem of scaling the (...) reasoning task. Scalability is a central problem, and some would even say the central problem, in appli- cations of logic in computer science. Separation Logic is an interesting case because of its widespread success in verification tools. For these two senses of model—the engineering/conceptual and the logical—to merge in a genuine sense, each must maintain their norms of use from their home disciplines. When this occurs, both the logic and engineering benefit greatly. Seeking this intersection of two different senses of model provides a strategy for how computer scientists and logicians may be successful. Furthermore, the history of Separation Logic for analysing programs provides a novel case for philosophers of science of how software engineers and computer scientists develop models and the components of such models. We provide three contributions: an exploration of the extent of models merging that is necessary for success in computer science; an introduction to the technical details of Separation Logic, which can be used for reasoning about other exhaustible resources; and an introduction to the problems, process, and results of computer scientists for those outside the field. (shrink)

This is the first paper on constructive concurrent dynamic logic . For the first time, either for concurrent or sequential dynamic logic, we give a satisfactory treatment of what statements are forced to be true by partial information about the underlying computer. Dynamic logic was developed by Pratt [V. Pratt, Semantical considerations on Floyd–Hoare logic, in: 17th Annual IEEE Symp. on Found. Comp. Sci., New York, 1976, pp. 109–121, V. Pratt, Applications of modal logic to programming, Studia Logica 39 257–274] (...) for nondeterministic sequential programs, and by Peleg [D. Peleg, Concurrent dynamic logic, Journal of the Association for Computing Machinery 34 , D. Peleg, Communication in concurrent dynamic logic, Journal of Computer and System Sciences 35 ] for concurrent programs, for the purpose of proving properties of programs such as correctness. Here we define what it means for a dynamic logic formula to be forced to be true knowing only partial information about the results of assignments and tests. This informal CCDL semantics is formalized by intuitionistic Kripke frames modeling this partial information, and each such frame is interpreted as an idealized concurrent machine . In CCDL, proofs and deductions are ω-height, ω-branching, well-founded labeled subtrees of ωω. These are a generalization of the signed tableaux of Nerode [A. Nerode, Some lectures in modal logic, Technical Report, M.S.I. Cornell University, 1989, CIME Logic and Computer Science Montecatini Volume, Springer-Verlag Lecture Notes, 1990, A. Nerode, Some lectures in intuitionistic logic, Technical Report, M.S.I. Cornell University, 1988, Marktoberdorf Logic and Computation NATO Summer School Volume, NATO Science Series, 1990 ] stemming from the prefix tableaux of Fitting [M.C. Fitting, Proof Methods for Modal and Intuitionistic Logic, Reidel, 1983]. We demonstrate the correctness of our tableau proofs, define consistency properties, prove that consistency properties yield models, construct systematic tableaux, prove that systematic tableaux yield a consistency property, and conclude that CCDL is complete. This infinitary semantics and proof procedure will be the primary guide for defining, in a sequel, the correct finitary CCDL based on induction principles. FCCDL is suitable for implementation in constructive logic software systems such as Constable’s NUPRL or Huet-Coquand’s CONSTRUCTIONS. Our goal is to develop a constructive logic programming tool for specification and modular verification of programs in any imperative concurrent language, and for the extraction of concurrent programs from constructive proofs. Subsequent papers will introduce analogous logics for declarative and functional concurrent languages. (shrink)

Throughout the twentieth century, the automation of formal logics in computers has created unprecedented potential for practical applications of logic—most prominently the mechanical verification of mathematics and software. But the high cost of these applications makes them infeasible but for a few flagship projects, and even those are negligible compared to the ever-rising needs for verification. One of the biggest challenges in the future of logic will be to enable applications at much larger scales and simultaneously at (...) much lower costs. This will require a far more efficient allocation of resources. Wherever possible, theoretical and practical results must be formulated generically so that they can be instantiated to arbitrary logics; this will allow reusing results in the face of today’s multitude of application-oriented and therefore diverging logical systems. Moreover, the software engineering problems concerning automation support must be decoupled from the theoretical problems of designing logics and calculi; this will allow researchers outside or at the fringe of logic to contribute scalable logic-independent tools. Anticipating these needs, the author has developed the Mmt framework. It offers a modern approach towards defining, analyzing, implementing, and applying logics that focuses on modular design and logic-independent results. This paper summarizes the ideas behind and the results about Mmt. It focuses on showing how Mmt. provides a theoretical and practical framework for the future of logic. (shrink)

Designing and building complex artifacts like simulation models often rely on the strategy of modularity. My main claim is that the validation of simulation models faces a challenge of holismHolism because modularityModularity tends to erode over the process of building a simulation model. Two different reasons that fuel the tendency to erosion are analyzed. Both are based on the methodologyMethodology of simulation, but on different levels. The first has to do with the way parameter adjustment works in simulation; the second (...) comes from how different groups of software programmers work together. The chapter will conclude by drawing lessons about how holism challenges the validation of simulation and by discussing a corollary to conformational holism: the boundary between validation and verification tends to become blurred, thus undermining a strategy that insists on keeping them separate. (shrink)

The value of logic techniques in circuit design has been well-known for many years, but a thorough grounding in mathematical logic is needed for all stages of software development, especially program specification, verification and program transformation. In all these stages, logic underpins the theory, bearing out the dictum that Logic is the calculus of computer science. This book presents the subject of mathematical logic in order to provide a grounding for students in computer science.

Temporal logic is of importance in theoretical computer science for its application in formal verification, to state requirements of hardware or software systems. Linear temporal logic is an appropriate logical environment to formalize Yablo’s paradox which is seemingly non-self-referential and basically has a sequential structure. We give a brief review of Yablo’s paradox and its various versions. Formalization of these paradoxes yields some theorems in Linear Temporal Logic (LTL) for which we give syntactic proofs using an appropriate axiomatization (...) of LTL. (shrink)

Over the last decade, multi-agent systems have come to form one of the key tech- nologies for software development. The Formal Approaches to Multi-Agent Systems (FAMAS) workshop series brings together researchers from the fields of logic, theoreti- cal computer science and multi-agent systems in order to discuss formal techniques for specifying and verifying multi-agent systems. FAMAS addresses the issues of logics for multi-agent systems, formal methods for verification, for example model check- ing, and formal approaches to cooperation, multi-agent (...) planning, communication, coordination, negotiation, games, and reasoning under uncertainty in a distributed environment. In 2007, the third FAMAS workshop, FAMAS'007, was one of the agent workshops gathered together under the umbrella of Multi-Agent Logics, Languages, and Organ- isations - Federated Workshops, MALLOW'007, taking place from 3 to 7 September 2007 in Durham. This current special issue of the Logic Journal of the IGPL gathers together the revised and updated versions of the five best FAMAS'007 contributions. (shrink)

Introduction -- Algorithms, programs, procedures, and abstract automata -- Functioning of algorithms and automata, computation, and operations with algorithms and automata -- Basic postulates and axioms for algorithms -- Power of algorithms and classes of algorithms: comparison and evaluation -- Computing, accepting, and deciding modes of algorithms and programs -- Problems that people solve and related properties of algorithms -- Boundaries for algorithms and computation -- Software and hardware verification and testing -- Conclusion.

This chapter contains sections titled: References and Further Reading.

This paper starts with the study of realistic three-dimensional models, from the two aspects of ink art style simulation model and three-dimensional display technology, explores the three-dimensional display model of three-dimensional model ink style, and conducts experiments through the software development platform and auxiliary software. The feasibility of the model is verified. Aiming at the problem of real-time rendering of large-scale 3D scenes in the model, efficient visibility rejection method and a multiresolution fast rendering method were designed to (...) realize the rapid construction and rendering of ink art 3D virtual reality scenes in a big data environment. A two-dimensional cellular automaton is used to simulate a brushstroke model with ink and wash style, and outlines are drawn along the path of the brushstroke to obtain an effect close to the artistic style of ink and wash painting. Set the surface of the model with ink style brushstroke texture patterns, refer to the depth map, normal map, and curvature map information of the model, and simulate the drawing effect of the method by procedural texture mapping. Example verification shows that the rapid visualization analysis model of ink art big data designed in this paper is in line with the prediction requirements of ink art big data three-dimensional display indicators. The fast visibility removal method is used to deal with large-scale three-dimensional ink art in a big data environment. High efficiency is achieved in virtual reality scenes, and the multiresolution fast rendering method better maintains the appearance of the prediction model without major deformation. (shrink)

This article presents two theorems: a generalization of Löb’s Theorem that applies to formal proof systems operating with bounded computational resources, such as formal verification software or theorem provers, and a theorem on the robust cooperation of agents that employ proofs about one another’s source code as unexploitable criteria for cooperation. The latter illustrates a capacity for outperforming classical Nash equilibria and correlated equilibria, attaining mutually cooperative program equilibrium in the Prisoner’s Dilemma while remaining unexploitable, i.e., sometimes achieving (...) the outcome, and never receiving the outcome as player 1. (shrink)

This festschrift volume is dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday. For over half a century, Trakhtenbrot has been making seminal contributions to virtually all of the central areas of theoretical computer science. He is universally admired as a founding father and long-standing pillar of the discipline of computer science. On Friday, 28 April 2006, the School of Computer Science at Tel Aviv University held a “Computation Day Celebrating Boaz (Boris) Trakhtenbrot's Eighty-Fifth Birthday”. As a (...) follow-up to that event, his students and colleagues were asked to contribute to a volume in his honor and in recognition of his grand contributions to the field. The book opens with two historical overviews and a bibliography. These are followed by 33 thoroughly reviewed technical contributions. The broad range of topics covered include mathematical logic, logics for computer science, mathematics for computer science, automata and formal languages, asynchronous computation, semantics of programming languages, verification, and software engineering. This tapestry of subjects stands as testimony to the vast scope of Trakhtenbrot's achievements and the profound influence he has had on the field. (shrink)

The article is an attempt to answer one of the most important question in the philosophy of computer science: is a computer science a new branch of mathematics or an engineering discipline? Mathematical methods in computer science (especially in the process of program designing and producing, software and hardware verification) are discussed. In the article are considered problems connected with acceptance of mathematical paradigm in computer science. The main issue is the problem of philosophical consequences of regarding computer (...) science as a branch of mathematics. (shrink)

Proof and Disproof in Formal Logic is a lively and entertaining introduction to formal logic providing an excellent insight into how a simple logic works. Formal logic allows you to check a logical claim without considering what the claim means. This highly abstracted idea is an essential and practical part of computer science. The idea of a formal system-a collection of rules and axioms, which define a universe of logical proofs-is what gives us programming languages and modern-day programming. This book (...) concentrates on using logic as a tool: making and using formal proofs and disproofs of particular logical claims. The logic it uses-natural deduction-is very small and very simple; working with it helps you see how large mathematical universes can be built on small foundations. The book is divided into four parts: Part I "Basics" gives an introduction to formal logic with a short history of logic and explanations of some technical words. Part II "Formal Syntactic Proof" show you how to do calculations in a formal system where you are guided by shapes and never need to think about meaning. Your experiments are aided by Jape, which can operate as both inquisitor and oracle. Part III "Formal Semantic Disproof" shows you how to construct mathematical counterexamples to shoe that proof is impossible. Jape can check the counterexamples you build. Part IV " Program Specification and Proof" describes how to apply your logical understanding to a real computer science problem, the accurate description and verification of programs. Jape helps, as far as arithmetic allows. Aimed at undergraduates and graduates in computer science, logic, mathematics and philosophy, the text includes reference to and exercises based on the computer software package Jape, an interactive teaching and research tool designed and hosted by the author that is freely available on the web. (shrink)

Unmanned aerial vehicles, particularly quadcopters, have several medical, agriculture, surveillance, and security applications. However, the use of this innovative technology for civilian applications is still very limited in low-income countries due to the high cost, whereas low-cost controllers available in the market are often tuned using the hit and trial approach and are limited for specific applications. This paper addresses this issue and presents a novel proof of concept low-cost quadcopter UAV design approach using a systematic Model-Based Design method for (...) mathematical modeling, simulation, real-time testing, and prototyping. The quadcopter dynamic model is developed, and controllers are designed using Proportional Integral, and Derivative, Pole Placement, and Linear Quadratic Regulator control strategies. The stability of the controllers is also checked using Lyapunov stability analysis. For verification and validation of the design, Software-in-the-Loop, Processor-in-the-Loop, Hardware-in-the-loop testing, and Rapid Control Prototyping have been performed. The V&V methods of the MBD approach showed practically valid results with a stable flight of the quadcopter prototype. The proposed low-cost POC quadcopter design approach can be easily modified to have enhanced features, and quadcopters with different design parameters can be assembled using this approach for a diverse range of applications. (shrink)

In recent years, with the development of society and the rapid development of the animation industry, people are paying more and more attention to and requirements for animation production. As an indispensable part of animation production, picture composition plays a major role in animation production. It can give full play to the application of color matching and light and shadow design and enhance the depth and space of the animation screen. Tone space conversion refers to the conversion or representation of (...) color data in one color space into corresponding data in another color space. Its purpose is to distinguish and process color components such as hue and saturation in an image. This article first introduces the domestic and foreign research status of digital image preprocessing and analyzes the basic principles of several color space conversions in detail. Then, several color space conversion algorithms are studied, and the performance of the algorithms is compared and analyzed. The paper focuses on the hardware implementation and optimization of the algorithm for converting RGB color space into HSI color space to meet the real-time requirements. This article focuses on the mutual conversion between the RGB tone space and the HSI tone space and describes in detail how each color component in the HSI tone space is converted from the three RGB color components from a geometric perspective, and then the conversion is derived, and several general conversion methods of RGB to HSI tone space are introduced; two conversion methods of geometric derivation method and standard modulus algorithm are implemented in the software, and the comparison verification is carried out, and the comparison is made from the perspective of hardware implementation. The pros and cons of the two methods are discussed. Finally, the paper summarizes the shortcomings in the design and proposes further research directions in the future. (shrink)

Documents the history and rationale as well as the technology for the creation of an open online corpus of Ancient Greek texts, the Free First Thousand Years of Greek. Reveals the energy on a worldwide basis for building open data along with the boundless creativity around developing software tools for teaching, research, and publishing that exploit open data in ways that were impossible before.

Software is a ubiquitous artifact, yet not much has been done to understand its ontological nature. There are a few accounts offered so far about the nature of software. I argue that none of those accounts give a plausible picture of the nature of software. I draw attention to the striking similarities between software and musical works. These similarities motivate to look more closely on the discussions regarding the nature of the musical works. With the lessons (...) drawn from the ontology of musical works I offer a novel account of the nature of software. In this account, software is an abstract artifact. I elaborate the conditions under which software comes into existence; how it persists; how and on which entities its existence depends. (shrink)