Results 31 to 40 of about 759,615 (239)
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem [PDF]
Logical Methods in Computer Science, 2012 The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise ...
Libor Barto, Marcin Kozik
doaj +1 more source
Untyping Typed Algebras and Colouring Cyclic Linear Logic [PDF]
Logical Methods in Computer Science, 2012 We prove "untyping" theorems: in some typed theories (semirings, Kleene algebras, residuated lattices, involutive residuated lattices), typed equations can be derived from the underlying untyped equations.
Damien Pous
doaj +1 more source
Reasoning about Strategies: on the Satisfiability Problem [PDF]
Logical Methods in Computer Science, 2017 Strategy Logic (SL, for short) has been introduced by Mogavero, Murano, and Vardi as a useful formalism for reasoning explicitly about strategies, as first-order objects, in multi-agent concurrent games.
Fabio Mogavero +3 more
doaj +1 more source
Some Views on Information Fusion and Logic Based Approaches in Decision Making under Uncertainty
Journal of universal computer science (Online), 2010 Decision making under uncertainty is a key issue in information fusion and logic based reasoning approaches. The aim of this paper is to show noteworthy theoretical and applicational issues in the area of decision making under uncertainty that have been ...
Yang Xu +3 more
semanticscholar +1 more source
Models of Type Theory Based on Moore Paths [PDF]
Logical Methods in Computer Science, 2019 This paper introduces a new family of models of intensional Martin-L\"of type theory. We use constructive ordered algebra in toposes. Identity types in the models are given by a notion of Moore path.
Ian Orton, Andrew M. Pitts
doaj +1 more source
Exhaustible sets in higher-type computation [PDF]
Logical Methods in Computer Science, 2008 We say that a set is exhaustible if it admits algorithmic universal quantification for continuous predicates in finite time, and searchable if there is an algorithm that, given any continuous predicate, either selects an element for which the predicate ...
Martin Escardo
doaj +1 more source
On the strength of proof-irrelevant type theories [PDF]
Logical Methods in Computer Science, 2008 We present a type theory with some proof-irrelevance built into the conversion rule. We argue that this feature is useful when type theory is used as the logical formalism underlying a theorem prover.
Benjamin Werner
doaj +1 more source
Petri Net Reachability Graphs: Decidability Status of First Order Properties [PDF]
Logical Methods in Computer Science, 2012 We investigate the decidability and complexity status of model-checking problems on unlabelled reachability graphs of Petri nets by considering first-order and modal languages without labels on transitions or atomic propositions on markings.
Philippe Darondeau +3 more
doaj +1 more source
The Wadge Hierarchy of Deterministic Tree Languages [PDF]
Logical Methods in Computer Science, 2008 We provide a complete description of the Wadge hierarchy for deterministically recognisable sets of infinite trees. In particular we give an elementary procedure to decide if one deterministic tree language is continuously reducible to another.
Filip Murlak
doaj +1 more source
Proof-irrelevant model of CC with predicative induction and judgmental equality [PDF]
Logical Methods in Computer Science, 2011 We present a set-theoretic, proof-irrelevant model for Calculus of Constructions (CC) with predicative induction and judgmental equality in Zermelo-Fraenkel set theory with an axiom for countably many inaccessible cardinals. We use Aczel's trace encoding
Gyesik Lee, Benjamin Werner
doaj +1 more source