Additive Combinatorics and its Applications in Theoretical Computer Science
Theory of Computing, 2017 Additive combinatorics (or perhaps more accurately, arithmetic combinatorics) is a branch of mathematics which lies at the intersection of combinatorics, number theory, Fourier analysis and ergodic theory.
Shachar Lovett
semanticscholar +1 more source
Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic [PDF]
Logical Methods in Computer Science, 2007 In a previous work Baillot and Terui introduced Dual light affine logic (DLAL) as a variant of Light linear logic suitable for guaranteeing complexity properties on lambda calculus terms: all typable terms can be evaluated in polynomial time by beta ...
Vincent Atassi +2 more
doaj +1 more source
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning [PDF]
Logical Methods in Computer Science, 2008 Resolution refinements called w-resolution trees with lemmas (WRTL) and with input lemmas (WRTI) are introduced. Dag-like resolution is equivalent to both WRTL and WRTI when there is no regularity condition.
Samuel R. Buss +2 more
doaj +1 more source
Representations of Stream Processors Using Nested Fixed Points [PDF]
Logical Methods in Computer Science, 2009 We define representations of continuous functions on infinite streams of discrete values, both in the case of discrete-valued functions, and in the case of stream-valued functions.
Neil Ghani +2 more
doaj +1 more source
Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations [PDF]
Logical Methods in Computer Science, 2008 Strong and weak simulation relations have been proposed for Markov chains, while strong simulation and strong probabilistic simulation relations have been proposed for probabilistic automata.
Lijun Zhang +3 more
doaj +1 more source
A Reduction-Preserving Completion for Proving Confluence of Non-Terminating Term Rewriting Systems [PDF]
Logical Methods in Computer Science, 2012 We give a method to prove confluence of term rewriting systems that contain non-terminating rewrite rules such as commutativity and associativity.
Takahito Aoto, Yoshihito Toyama
doaj +1 more source
The Threshold for Subgroup Profiles to Agree is Logarithmic
Theory of Computing, 2019 For primes p > 2 and e > 3 there are at least pe−3/e groups of order p2e+2 that have equal multisets of isomorphism types of proper subgroups and proper quotient groups, isomorphic character tables, and power maps.
James B. Wilson
semanticscholar +1 more source
Visibly Tree Automata with Memory and Constraints [PDF]
Logical Methods in Computer Science, 2008 Tree automata with one memory have been introduced in 2001. They generalize both pushdown (word) automata and the tree automata with constraints of equality between brothers of Bogaert and Tison.
Hubert Comon-Lundh +2 more
doaj +1 more source
Formalizing Randomized Matching Algorithms [PDF]
Logical Methods in Computer Science, 2012 Using Je\v{r}\'abek 's framework for probabilistic reasoning, we formalize the correctness of two fundamental RNC^2 algorithms for bipartite perfect matching within the theory VPV for polytime reasoning.
Dai Tri Man Le, Stephen A. Cook
doaj +1 more source
Essential Convexity and Complexity of Semi-Algebraic Constraints [PDF]
Logical Methods in Computer Science, 2012 Let \Gamma be a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets.
Manuel Bodirsky +2 more
doaj +1 more source