The Experts below are selected from a list of 2358 Experts worldwide ranked by ideXlab platform
Kloibhofer Johannes - One of the best experts on this subject based on the ideXlab platform.
-
Ein Fixpunktsatz für Horn-Formelgleichungen
Wien, 2021Co-Authors: Kloibhofer JohannesAbstract:Arbeit an der Bibliothek noch nicht eingelangt - Daten nicht geprüftAbweichender Titel nach Übersetzung der Verfasserin/des VerfassersFormula equations are logical equations in which the unknowns are formulas. They naturally occur in many areas like program verification or automated Theorem proving. In these communities similar problems are treated independently. Our motivation is to state general Theorems about formula equations which then will be used to generalize and simplify results in various different applications. In this thesis we treat the special case of Horn formula equations, this restriction is justified as it covers many applications. For Horn formula equations we are able to compute canonical solutions if a solution exists. This will be achieved by defining an operator such that every solution of the Horn formula equation is a fixed point of it. Now the least fixed point, which exists due to the Knaster-Tarski Theorem, turns out to always be a solution if there exists one. This canonical solution will be described by least fixed-point formulas. Furthermore the canonical solution implies every solution of the Horn formula equation. We then use the Horn fixed-point Theorem to obtain a first-order approximation of second-order formulas as well as to get a different perspective on Hoare triples in program verification and to get more insights in inductive Theorem proving.4
-
Ein Fixpunktsatz für Horn-Formelgleichungen
Wien, 2021Co-Authors: Kloibhofer JohannesAbstract:Abweichender Titel nach Übersetzung der Verfasserin/des VerfassersFormula equations are logical equations in which the unknowns are formulas. They naturally occur in many areas like program verification or automated Theorem proving. In these communities similar problems are treated independently. Our motivation is to state general Theorems about formula equations which then will be used to generalize and simplify results in various different applications. In this thesis we treat the special case of Horn formula equations, this restriction is justified as it covers many applications. For Horn formula equations we are able to compute canonical solutions if a solution exists. This will be achieved by defining an operator such that every solution of the Horn formula equation is a fixed point of it. Now the least fixed point, which exists due to the Knaster-Tarski Theorem, turns out to always be a solution if there exists one. This canonical solution will be described by least fixed-point formulas. Furthermore the canonical solution implies every solution of the Horn formula equation. We then use the Horn fixed-point Theorem to obtain a first-order approximation of second-order formulas as well as to get a different perspective on Hoare triples in program verification and to get more insights in inductive Theorem proving.4
Lawrence C. Paulson - One of the best experts on this subject based on the ideXlab platform.
-
C.: A fixedpoint approach to (co)inductive and (co)datatype definitions. Latest version http://isabelle.in.tum.de/doc/ind-defs.pdf
2009Co-Authors: Lawrence C. PaulsonAbstract:This paper presents a fixedpoint approach to inductive definitions. Instead of using a syntactic test such as “strictly positive, ” the approach lets definitions involve any operators that have been proved monotone. It is conceptually simple, which has allowed the easy implementation of mutual recursion and iterated definitions. It also handles coinductive definitions: simply replace the least fixedpoint by a greatest fixedpoint. The method has been implemented in two of Isabelle’s logics, zf set theory and higher-order logic. It should be applicable to any logic in which the Knaster-Tarski Theorem can be proved. Examples include lists of n elements, the accessible part of a relation and the set of primitive recursive functions. One example of a coinductive definition is bisimulations for lazy lists. Recursive datatypes are examined in detail, as well as one example of a codatatype: lazy lists. The Isabelle package has been applied in several large case studies, including two proofs of the Church-Rosser Theorem and a coinductive proof of semantic consistency. The package can be trusted because it proves Theorems from definitions, instead of asserting desired properties as axioms. Copyright c ○ 2009 by Lawrence C. Paulso
-
set theory for verification ii induction and recursion
arXiv: Logic in Computer Science, 2000Co-Authors: Lawrence C. PaulsonAbstract:A theory of recursive definitions has been mechanized in Isabelle's Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set. Recursive functions are defined by well-founded recursion and its derivatives, such as transfinite recursion. Recursive data structures are expressed by applying the Knaster-Tarski Theorem to a set, such as V[omega], that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees and mutually recursive trees and forests. The Schr\"oder-Bernstein Theorem and the soundness of propositional logic are proved in Isabelle sessions.
-
Set theory for verification. II: Induction and recursion
Journal of Automated Reasoning, 1995Co-Authors: Lawrence C. PaulsonAbstract:A theory of recursive definitions has been mechanized in Isabelle's Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs, and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set. Recursive functions are defined by well-founded recursion and its derivatives, such as transfinite recursion. Recursive data structures are expressed by applying the Knaster-Tarski Theorem to a set, such as V _ω, that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees, and mutually recursive trees and forests. The Schröder-Bernstein Theorem and the soundness of propositional logic are proved in Isabelle sessions.
-
Set theory for verification: II. induction and recursion
1995Co-Authors: Lawrence C. PaulsonAbstract:Abstract. A theory of recursive definitions has been mechanized in Isabelle’s Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set. Recursive functions are defined by well-founded recursion and its derivatives, such as transfinite recursion. Recursive data structures are expressed by applying the Knaster-Tarski Theorem to a set, such as Vω, that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees and mutually recursive trees and forests. The Schröder-Bernstein Theorem and the soundness of propositional logic are proved in Isabelle sessions. Key words: Isabelle, set theory, recursive definitions, the Schröder-Bernstein Theore
-
Set Theory for Verification: II - Induction and Recursion
1995Co-Authors: Lawrence C. PaulsonAbstract:. A theory of recursive definitions has been mechanized in Isabelle's Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set. Recursive functions are defined by well-founded recursion and its derivatives, such as transfinite recursion. Recursive data structures are expressed by applying the Knaster-Tarski Theorem to a set, such as V# , that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees and mutually recursive trees and forests. The Schroder-Bernstein Theorem and the soundness of propositional logic are proved in Isabelle sessions. Key words: Isabelle, set theory, recursive definitions, the Schroder-Bernstein Theorem Contents 1 Introd..
Bachir Mohammed - One of the best experts on this subject based on the ideXlab platform.
-
Une r\'eflexion \`a partir de la Nature de Spinoza : "La substance ou la Nature comme Treillis"
2018Co-Authors: Bachir Mohammed, Baruch, Mohammed Bachir En Hommage ÀAbstract:We propose a simple mathematical model based on two axioms and the set theory to approach the problem developed by the philosopher B. Spinoza in "the Ethics". We then use the Knaster-Tarski Theorem to prove the existence and uniqueness of the Substance asserted by Spinoza.Comment: in Frenc
-
Une réflexion à partir de la Nature de Spinoza : "La substance ou la Nature comme Treillis".
HAL CCSD, 2018Co-Authors: Bachir MohammedAbstract:We propose a simple mathematical model based on two axioms and the set theory to approach the problem developed by the philosopher B. Spinoza in "the Ethics". We then use the Knaster-Tarski Theorem to prove the existence and uniqueness of the Substance asserted by Spinoza.On propose un modèle mathématique basé sur deux axiomes et la théorie des ensembles pour approcher la problématique développé par le philosophe B. Spinoza, dans l'Ethique. On utilise ensuite le Théorème de Knaster-Tarski pour démontrer l'existence et l'unicité de la Substance affirmée par Spinoza
Wiśnicki Andrzej - One of the best experts on this subject based on the ideXlab platform.
-
The Knaster-Tarski Theorem versus monotone nonexpansive mappings
'Institute of Mathematics Polish Academy of Sciences', 2018Co-Authors: Espínola Rafael, Wiśnicki AndrzejAbstract:Let $X$ be a partially ordered set with the property that each family of order intervals of the form $[a,b],[a,\rightarrow )$ with the finite intersection property has a nonempty intersection. We show that every directed subset of $X$ has a supremum. Then we apply the above result to prove that if $X$ is a topological space with a partial order $\preceq $ for which the order intervals are compact, $\mathcal{F}$ a nonempty commutative family of monotone maps from $X$ into $X$ and there exists $c\in X$ such that $c\preceq Tc$ for every $T\in \mathcal{F}$, then the set of common fixed points of $\mathcal{F}$ is nonempty and has a maximal element. The result, specialized to the case of Banach spaces gives a general fixed point Theorem that drops almost all assumptions from the recent results in this area. An application to the theory of integral equations of Urysohn's type is also given
Baruch, Mohammed Bachir En Hommage À - One of the best experts on this subject based on the ideXlab platform.
-
Une r\'eflexion \`a partir de la Nature de Spinoza : "La substance ou la Nature comme Treillis"
2018Co-Authors: Bachir Mohammed, Baruch, Mohammed Bachir En Hommage ÀAbstract:We propose a simple mathematical model based on two axioms and the set theory to approach the problem developed by the philosopher B. Spinoza in "the Ethics". We then use the Knaster-Tarski Theorem to prove the existence and uniqueness of the Substance asserted by Spinoza.Comment: in Frenc