Results 11 to 20 of about 279,119 (104)
Efficiently Simulating Higher-Order Arithmetic by a First-Order Theory Modulo [PDF]
Logical Methods in Computer Science, 2011 In deduction modulo, a theory is not represented by a set of axioms but by a congruence on propositions modulo which the inference rules of standard deductive systems---such as for instance natural deduction---are applied.
Guillaume Burel
doaj +1 more source
A Type System Describing Unboundedness [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of ...
Paweł Parys
doaj +1 more source
Constrained ear decompositions in graphs and digraphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a ...
Frédéric Havet, Nicolas Nisse
doaj +1 more source
On interval number in cycle convexity [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they ...
Julio Araujo +3 more
doaj +1 more source
On the computational power and complexity of Spiking Neural Networks [PDF]
Neuro Inspired Computational Elements Workshop, 2020 The last decade has seen the rise of neuromorphic architectures based on artificial spiking neural networks, such as the SpiNNaker, TrueNorth, and Loihi systems.
Johan Kwisthout, N. Donselaar
semanticscholar +1 more source
On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [PDF]
Annual Conference Computational Learning Theory, 2023 A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees, and how these considerations change as we move from few to ...
Dylan J. Foster +3 more
semanticscholar +1 more source
Toward the asymptotic count of bi-modular hidden patterns under probabilistic dynamical sources: a case study [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 Consider a countable alphabet $\mathcal{A}$. A multi-modular hidden pattern is an $r$-tuple $(w_1,\ldots , w_r)$, where each $w_i$ is a word over $\mathcal{A}$ called a module.
Loïck Lhote, Manuel E. Lladser
doaj +1 more source
Permutation Pattern matching in (213, 231)-avoiding permutations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 Given permutations σ of size k and π of size n with k < n, the permutation pattern matching problem is to decide whether σ occurs in π as an order-isomorphic subsequence.
Both Neou +2 more
doaj +1 more source
Improved Quantum Communication Complexity Bounds for Disjointness and Equality [PDF]
, 2001 We prove new bounds on the quantum communication complexity of the disjointness and equality problems. For the case of exact and non-deterministic protocols we show that these complexities are all equal to n+1, the previous best lower bound being n/2. We
A. Razborov +9 more
core +4 more sources
Source coding by efficient selection of ground states clusters [PDF]
, 2004 In this letter, we show how the Survey Propagation algorithm can be generalized to include external forcing messages, and used to address selectively an exponential number of glassy ground states. These capabilities can be used to explore efficiently the
Battaglia, Demian +3 more
core +3 more sources