The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We propose a novel approach to constraint-based type inference based on coinductive logic. Constraint generation corresponds to translation into a conjunction of Horn clauses P, and constraint satisfaction is defined in terms of the coinductive Herbrand model of P. We illustrate the approach by formally defining this translation for a small object-oriented language similar to Featherweight Java, where...
We discuss the formalization, in the Matita Interactive Theorem Prover, of a famous result by Chebyshev concerning the distribution of prime numbers, essentially subsuming, as a corollary, Bertrand’s postulate. Even if Chebyshev’s result has been later superseded by the stronger prime number theorem, his machinery, and in particular the two functions ψ and θ still play a central role in the modern...
In Type Theory, definition by dependently-typed case analysis can be expressed by means of a set of equations — the semantic approach — or by an explicit pattern-matching construction — the syntactic approach. We aim at putting together the best of both approaches by extending the pattern-matching construction found in the Coq proof assistant in order to obtain the expressivity and flexibility of...
The Java Micro Edition platform (JME), a Java enabled technology, provides the Mobile Information Device Profile (MIDP) standard that facilitates applications development and specifies a security model for the controlled access to sensitive resources of the device. The model builds upon the notion of protection domain, which in turn can be grasped as a set of permissions. An alternative model has...
We investigate the notion of ‘infinitary strong normalization’ (SN ∞ ), introduced in [6], the analogue of termination when rewriting infinite terms. A (possibly infinite) term is SN ∞ if along every rewrite sequence each fixed position is rewritten only finitely often. In [9], SN ∞ has been investigated as a system-wide property, i.e. SN ∞ for all terms of a given rewrite system. This global...
Typically, an object is a monolithic entity with a fixed interface. To increase flexibility in this area, this paper presents first-class object sets as a language construct. An object set offers an interface which is a disjoint union of the interfaces of its member objects. It may also be used for a special kind of method invocation involving multiple objects in a dynamic lookup process. With support...
This paper proposes and analyses a monadic translation of an intuitionistic sequent calculus. The source of the translation is a typed λ-calculus previously introduced by the authors, corresponding to the intuitionistic fragment of the call-by-name variant of of Curien and Herbelin, and the target is a variant of Moggi’s monadic meta-language, where the rewrite...
We argue that it is high time that types had a beneficial impact in the field of Answer Set Programming and in particular Disjunctive Datalog as exemplified by the DLV system. Things become immediately more challenging, as we wish to present a type system for DLV-Complex, an extension of DLV with uninterpreted function symbols, external implemented predicates and types. Our type system owes to the...
We study the type inference problem for the Soft Type Assignment system (STA) for λ-calculus introduced in [1], which is correct and complete for polynomial time computations. In particular we design an algorithm which, given in input a λ-term, provides all the constraints that need to be satisfied in order to type it. For the propositional fragment of STA, the satisfiability of the constraints is...
The proof assistant Isabelle has recently acquired a “local theory” concept that integrates a variety of mechanisms for structured specifications into a common framework. We explicitly separate a local theory “target”, i.e. a fixed axiomatic specification consisting of parameters and assumptions, from its “body” consisting of arbitrary definitional extensions. Body elements may be added incrementally,...
Superdeduction and deduction modulo are two methods designed to ease the use of first-order theories in predicate logic. Superdeduction modulo combines both in a single framework. Although soundness is ensured, using superdeduction modulo to extend deduction with awkward theories can jeopardize cut-elimination or completeness w.r.t predicate logic. In this paper our aim is to design criteria for theories...
The aim of this article is to support component-based software engineering by modelling exclusive and inclusive usage of software components. Truong and Bezem describe in several papers abstract languages for component software with the aim to find bounds of the number of instances of components. Their language includes primitives for instantiating and deleting instances of components and operators...
There are two different styles for writing natural deduction proofs: the ‘Gentzen’ style in which a proof is a tree with the conclusion at the root and the assumptions at the leaves, and the ‘Fitch’ style (also called ‘flag’ style) in which a proof consists of lines that are grouped together in nested boxes. In the world of proof assistants these two kinds of natural deduction correspond to...
We propose a (limited) solution to the problem of constructing stream values defined by recursive equations that do not respect the guardedness condition. The guardedness condition is imposed on definitions of corecursive functions in Coq, AGDA, and other higher-order proof assistants. In this paper, we concentrate in particular on those non-guarded equations where recursive calls appear under functions...
Manifest fields in a type of modules are shown to be expressible in intensional type theory without strong extensional equality rules. These intensional manifest fields are made available with the help of coercive subtyping. It is shown that, for both Σ-types and dependent record types, the with-clause for expressing manifest fields can be introduced by means of the intensional manifest fields. This...
As a case-study in machine-checked reasoning about the complexity of algorithms in type theory, we describe a proof of the average-case complexity of Quicksort in Coq. The proof attempts to follow a textbook development, at the heart of which lies a technical lemma about the behaviour of the algorithm for which the original proof only gives an intuitive justification. We introduce a general...
In this work we present a modular theory of the coalgebras and bisimulation in the intensional type theory implemented in coq. On top of that we build the theory of weakly final coalgebras and develop the λ-coiteration scheme, thereby extending the class of specifications definable in coq. We provide an instantiation of the theory for the coalgebra of streams and show how some of the productive specifications...
We use linProc (i.e. a typed process calculus based on the calculus of solos) in order to express computational processes generated by SlPCF−, namely a simple programming language conceived in order to program only linear functions. We define a faithful translation of SlPCF− on linProc which enables us to process redexes of SlPCF− in a parallel way. Afterward, we prove that a suitable observational...
We introduce a multimodal stratified framework MS that generalizes an idea hidden in the definitions of Light Linear/Affine logical systems: “More modalities means more expressiveness”. MS is a set of building-rule schemes that depend on parameters. We interpret the values of the parameters as modalities. Fixing the parameters yields deductive systems as instances of MS, that we call subsystems. Every...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.