Results 31 to 40 of about 1,420,577 (310)
On Minimum Maximal Distance-k Matchings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$
Yury Kartynnik, Andrew Ryzhikov
doaj +1 more source
Polynomial Size Analysis of First-Order Shapely Functions [PDF]
Logical Methods in Computer Science, 2009 We present a size-aware type system for first-order shapely function definitions. Here, a function definition is called shapely when the size of the result is determined exactly by a polynomial in the sizes of the arguments.
Olha Shkaravska +2 more
doaj +1 more source
An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms [PDF]
Logical Methods in Computer Science, 2011 This paper presents a new exponential lower bound for the two most popular deterministic variants of the strategy improvement algorithms for solving parity, mean payoff, discounted payoff and simple stochastic games. The first variant improves every node
Oliver Friedmann
doaj +1 more source
Improved Algorithms for Parity and Streett objectives [PDF]
Logical Methods in Computer Science, 2017 The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness ...
Krishnendu Chatterjee +2 more
doaj +1 more source
A feasible interpolation for random resolution [PDF]
Logical Methods in Computer Science, 2017 Random resolution, defined by Buss, Kolodziejczyk and Thapen (JSL, 2014), is a sound propositional proof system that extends the resolution proof system by the possibility to augment any set of initial clauses by a set of randomly chosen clauses (modulo ...
Jan Krajicek
doaj +1 more source
Theory of Computing, 2013 We give an overview of the history of fast algorithms for matrix multiplication. Along the way, we look at some other fundamental problems in algebraic complexity like polynomial evaluation. This exposition is self-contained.
M. Bläser
semanticscholar +1 more source
Quasipolynomial Normalisation in Deep Inference via Atomic Flows and Threshold Formulae [PDF]
Logical Methods in Computer Science, 2016 Je\v{r}\'abek showed that cuts in classical propositional logic proofs in deep inference can be eliminated in quasipolynomial time. The proof is indirect and it relies on a result of Atserias, Galesi and Pudl\'ak about monotone sequent calculus and a ...
Paola Bruscoli +3 more
doaj +1 more source
A Generic Framework for Reasoning about Dynamic Networks of Infinite-State Processes [PDF]
Logical Methods in Computer Science, 2009 We propose a framework for reasoning about unbounded dynamic networks of infinite-state processes. We propose Constrained Petri Nets (CPN) as generic models for these networks.
Ahmed Bouajjani +4 more
doaj +1 more source
Efficient Open World Reasoning for Planning [PDF]
Logical Methods in Computer Science, 2006 We consider the problem of reasoning and planning with incomplete knowledge and deterministic actions. We introduce a knowledge representation scheme called PSIPLAN that can effectively represent incompleteness of an agent's knowledge while allowing for ...
Tamara Babaian, James G. Schmolze
doaj +1 more source
Unique perfect matchings, forbidden transitions and proof nets for linear logic with Mix [PDF]
Logical Methods in Computer Science, 2020 This paper establishes a bridge between linear logic and mainstream graph theory, building on previous work by Retor\'e (2003). We show that the problem of correctness for MLL+Mix proof nets is equivalent to the problem of uniqueness of a perfect ...
Lê Thành Dũng Nguyên
doaj +1 more source