Finding models of a predicate logic formula is a well-known hard problem, whose complexity is exponential in the number of variables. However, even though this number is kept constant, substantial differences in compl...
详细信息
ISBN:
(纸本)1558606130
Finding models of a predicate logic formula is a well-known hard problem, whose complexity is exponential in the number of variables. However, even though this number is kept constant, substantial differences in complexity arise when searching for solutions in different problem instances. Such a behavior appears to be quite general, according to recent results reported in the literature;in fact, several classes of hard problems exhibit a narrow phase transition with respect to some order parameter, in correspondence of which the complexity dramatically rises up, still remaining tractable elsewhere. In this paper we provide an extensive experimental study on the emergence of a phase transition in the problem of matching a Horn clause to a universe, searching for a model of the clause or for a proof that no such model exists. As it turns out, phase transition in the matching problem depends in an essential way on two order parameters, one capturing syntactic aspects of the clause structure (intensional aspect), while the other related to the structure of the universe (extensional aspect).
the proceedings contain 40 papers. the special focus in this conference is on Automated Deduction. the topics include: A dynamic programming approach to categorial deduction;tractable transformations from modal provab...
ISBN:
(纸本)3540662227
the proceedings contain 40 papers. the special focus in this conference is on Automated Deduction. the topics include: A dynamic programming approach to categorial deduction;tractable transformations from modal provability logics into first-order logic;a Pspace algorithm for graded modal logic;solvability of context equations with two context variables is decidable;solving equational problems efficiently;a verifiable symbolic definite integral table look-up;a framework for the flexible integration of a class of decision procedures into theorem provers;on the universal theory of varieties of distributive lattices with operators;a resolution method for modal and description logics;MAthWEB, an agent-based communication layer for distributed automated theorem proving;fault-tolerant distributed theorem proving;formal metatheory using implicit syntax, and an application to data abstraction for asynchronous systems;on explicit reflection in theorem proving and formal verification;rewrite-based deduction and symbolic constraints;towards an automatic analysis of security protocols in first-order logic;abstraction-based relevancy testing for model elimination;a breadth-first strategy for mating search;embedding programming languages in theorem provers;extensional higher-order paramodulation and rue-resolution and automatic generation of proof search strategies for second-order logic.
the logicprogramming language λProlog is based on the intuitionistic theory of higher-order hereditary Harrop formulas, a logicthat significantly extends the theory of Horn clauses. A systematic exploitation ...
详细信息
It has become a tradition at CADE to run a competition for first-order automated theorem provers based on the TPTP problem library. this competition (CASC) [SuSu96] aims at fully automatic ATP systems and provides var...
ISBN:
(纸本)3540662227
It has become a tradition at CADE to run a competition for first-order automated theorem provers based on the TPTP problem library. this competition (CASC) [SuSu96] aims at fully automatic ATP systems and provides various categories dedicated to diffirent problem classes of rst-order logic. the number of problems solved and the runtime is used to assess the winners in the individual categories of the competition.
We discuss the relationship between probabilistic logic and π-CMS. Given a set of logical sentences and their probabilities of being true, the outcome of a probabilistic logic system consists of lower and upper bound...
详细信息
We discuss the relationship between probabilistic logic and π-CMS. Given a set of logical sentences and their probabilities of being true, the outcome of a probabilistic logic system consists of lower and upper bounds on the probability of an additional sentence to be true. these bounds are computed using a linear programming formulation. In π-CMS systems, the outcome is defined by the probabilities of the support and the plausibility (withthe assumptions being independent) after a first phase which consists of computing the prime implicants depending only on the variables of the assumptions. We propose to reformulate a π-CMS system without independence conditions on the assumptions, using the linear programming framework of probabilistic logic, and show how to exploit its particular structure to solve it efficiently. When an independence condition is imposed on the assumptions the two systems give different results. Comparisons are made on small problems using the assumption-based evidential language program (ABEL) of [Anrig et al., 1998] and the PSAT program of [Jaumard et al., 1991].
Originally developed as an automatic inductivetheorem prover [2] based on res- olution and paramodulation, the inka system was redesigned in inka 4.0 in the early ’90s [8] to meet the requirements arising f...
ISBN:
(纸本)3540662227
Originally developed as an automatic inductivetheorem prover [2] based on res- olution and paramodulation, the inka system was redesigned in inka 4.0 in the early ’90s [8] to meet the requirements arising from its designated use in formal methods. Meanwhile several large industrial applications of the verication sup- port environment (VSE) [7] have been performed which gave rise to thousands of proof obligations to be tackled by its underlying deductive system inka.
the theory of programming languages is one of the core areas of computer sci- ence offering a wealth of models and methods. Yet the complexity of most real programming languages means that a complete formalization of ...
ISBN:
(纸本)3540662227
the theory of programming languages is one of the core areas of computer sci- ence offering a wealth of models and methods. Yet the complexity of most real programming languages means that a complete formalization of their semantics is only of limited use unless it is supported by mechanical means for reasoning about the formalization. this line of research started in earnest withthe seminal paper by Gordon [1] who dened the semantics of a simple while-language in the HOL system and derived Hoare logic from the semantics. Since then, an ever growing number of more and more sophisticated programming languages have been embedded in theorem provers. this talk surveys some of the important developments in this area before concentrating on a specic instance, Bali. Bali (http://***/Bali/) is an embedding of a subset of Java in Isabelle/HOL. So far, the following aspects have been covered:
We reduce the provability problem of any formula of the Lambek calculus to some context-free parsing problem. this reduction, which is based on non-commutative proof-net theory, allows us to derive an automatic ...
详细信息
Equational problems (i.e.: First-order formulae with quantifier prefix ∃*∀*, whose only predicate symbol is syntactic equality) are an important tool in many areas of automated deduction, e.g.: Restricting the set of ...
详细信息
the proceedings contain 37 papers. the special focus in this conference is on Evolutionary Methods for Modeling, Training and Alternative Frameworks for the Computational Study of Evolutionary Social Systems. the topi...
ISBN:
(纸本)9783540627883
the proceedings contain 37 papers. the special focus in this conference is on Evolutionary Methods for Modeling, Training and Alternative Frameworks for the Computational Study of Evolutionary Social Systems. the topics include: Complexity formalisms, order and disorder in the structure of art;the application of evolutionary computation to selected problems in molecular biology;parallel evolutionary programming for constructing artificial neural networks;scaling behavior of the evolution strategy when evolving neuronal control architectures for autonomous agents;an object oriented simulation platform applied to markets and organizations;an agent-based computational model for the evolution of trade networks;performance-enhanced genetic programming;comparing subtree crossover with macromutation;composing 16th-century counterpoint with genetic programming and symbiosis;design of a high-gain operational amplifier and other circuits by means of genetic programming;modeling speculators with genetic programming;fast evolution strategies;airspace congestion smoothing by stochastic optimization;evolutionary optimization based on lagrangian with constraint scaling;solving static and dynamic fuzzy constraint networks using evolutionary hill-climbing;applying family competition to evolution strategies for constrained optimization;supporting polyploidy in genetic algorithms using dominance vectors;an individually variable mutation-rate strategy for genetic algorithms;inductive learning of mutation step-size in evolutionary parameter optimization;a note on the escape probabilities for two alternative methods of selection under gaussian mutation;raising theoretical questions about the utility of genetic algorithms;some geometric and algebraic results on crossover and an analysis of evolutionary algorithms based on neighborhood and step sizes.
暂无评论