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 give a model of dependent type theory with one univalent universe and propositional truncation interpreting a type as a stack, generalizing the groupoid model of type theory. As an application, we show that countable choice cannot be proved in dependent type theory with one univalent universe and propositional truncation.
Stable event structures, and their duality with prime algebraic domains (arising as partial orders of configurations), are a landmark of concurrency theory, providing a clear characterisation of causality in computations. They have been used for defining a concurrent semantics of several formalisms, from Petri nets to linear graph rewriting systems, which in turn lay at the basis of many visual frameworks...
We extend Kawamura and Cook's framework for computational complexity for operators in analysis. This model is based on second-order complexity theory for functionals on the Baire space, which is lifted to metric spaces via representations. Time is measured in the length of the input encodings and the output precision.
We study 2-player turn-based perfect-information stochastic games with countably infinite state space. The players aim at maximizing/minimizing the probability of a given event (i.e., measurable set of infinite plays), such as reachability, Büchi, ω-regular or more general objectives.
Brunet and Pous showed at LICS 2015 that the equational theory of identity-free relational Kleene lattices (a fragment of Kleene allegories) is decidable in EXPSPACE. In this paper, we show that the equational theory of Kleene allegories is decidable, and is EXPSPACE-complete, answering the first open question posed by their work. The proof proceeds by designing partial derivatives on graphs, which...
This paper studies sets of rational numbers definable by continuous Petri nets and extensions thereof. First, we identify a polynomial-time decidable fragment of existential FO(ℚ,+,<) and show that the sets of rationals definable in this fragment coincide with reachability sets of continuous Petri nets. Next, we introduce and study continuous vector addition systems with states (CVASS), which are...
Compute the coarsest simulation preorder included in an initial preorder is used to reduce the resources needed to analyze a given transition system. This technique is applied on many models like Kripke structures, labeled graphs, labeled transition systems or even word and tree automata. Let (Q,→) be a given transition system and ℛinit be an initial preorder over Q. Until now, algorithms to compute...
We investigate interrelationships among different notions from mathematical analysis, effective topology, and classical computability theory. Our main object of study is the class of computable functions defined over an interval with the boundary being a left-c.e. real number. We investigate necessary and sufficient conditions under which such functions can be computably extended. It turns out that...
We show how to derive natural deduction systems for the necessity fragment of various constructive modal logics by exploiting a pattern found in sequent calculi. The resulting systems are dual-context systems, in the style pioneered by Girard, Barber, Plotkin, Pfenning, Davies, and others. This amounts to a full extension of the Curry-Howard-Lambek correspondence to the necessity fragments of a constructive...
We prove that the solvability of systems of linear equations and related linear algebraic properties are definable in a fragment of fixed-point logic with counting that only allows polylogarithmically many iterations of the fixed-point operators. This enables us to separate the descriptive complexity of solving linear equations from full fixed-point logic with counting by logical means. As an application...
We study the descriptive complexity of summation problems in Abelian groups and semigroups. In general, an input to the summation problem consists of an Abelian semigroup G, explicitly represented by its multiplication table, and a subset X of G. The task is to determine the sum over all elements of X.
We present two finitary cut-free sequent calculi for the modal μ-calculus. One is a variant of Kozen's axiomatisation in which cut is replaced by a strengthening of the induction rule for greatest fixed point. The second calculus derives annotated sequents in the style of Stirling's ‘tableau proof system with names’ (2014) and features a generalisation of the ν-regeneration rule that allows discharging...
In many instances in first order logic or computable algebra, classical theorems show that many problems are undecidable for general structures, but become decidable if some rigidity is imposed on the structure. For example, the set of theorems in many finitely axiomatisable theories is nonrecursive, but the set of theorems for any finitely axiomatisable complete theory is recursive. Finitely presented...
We consider the problem of counting the number of answers to a first-order formula on a finite structure. We present and study an extension of first-order logic in which algorithms for this counting problem can be naturally and conveniently expressed, in senses that are made precise and that are motivated by the wish to understand tractable cases of the counting problem.
We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of a logic over some “background structure”. We show that within this framework, concepts defined by first-order formulas over a background structure of at most polylogarithmic degree can be learned in polylogarithmic time in the “probably approximately correct” learning sense.
It has been shown that for a general-valued constraint language Γ the following statements are equivalent: (1) any instance of VCSP(Γ) can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy; (2) any instance of VCSP(Γ) can be solved to optimality using the third level of the Sherali-Adams LP hierarchy; (3) the support of Γ satisfies the “bounded width condition”, i.e...
We introduce fibred type-theoretic fibration categories which are fibred categories between categorical models of Martin-Löf type theory. Fibred type-theoretic fibration categories give a categorical description of logical predicates for identity types. As an application, we show a relational parametricity result for homotopy type theory. As a corollary, it follows that every closed term of type of...
Descriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive complexity for counting complexity classes, such as FP and #P, has not been systematically studied, and it is not as developed as its decision counterpart. In this paper, we propose a framework based on Weighted Logics to...
Final coalgebras as “categorical greatest fixed points” play a central role in the theory of coalgebras. Somewhat analogously, most proof methods studied therein have focused on greatest fixed-point properties like safety and bisimilarity. Here we make a step towards categorical proof methods for least fixed-point properties over dynamical systems modeled as coalgebras. Concretely, we seek a categorical...
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.