Results 21 to 30 of about 698 (72)
Representing Reversible Cellular Automata with Reversible Block Cellular Automata [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size ...
Jérôme Durand-Lose
doaj +1 more source
A Sequential Search Distribution: Proofreading, Russian Roulette, and the Incomplete q-Eulerian Polynomials [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 The distribution for the number of searches needed to find k of n lost objects is expressed in terms of a refinement of the q-Eulerian polynomials, for which formulae are developed involving homogeneous symmetric polynomials. In the case when k=n and the
Travis Herbranson, Don Rawlings
doaj +1 more source
Well-Centered Triangulation [PDF]
, 2008 Meshes composed of well-centered simplices have nice orthogonal dual meshes (the dual Voronoi diagram). This is useful for certain numerical algorithms that prefer such primal-dual mesh pairs.
Guoy, Damrong +3 more
core +3 more sources
Stokes polyhedra for $X$-shaped polyminos [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 Consider a pair of $\textit{interlacing regular convex polygons}$, each with $2(n + 2)$ vertices, which we will be referring to as $\textit{red}$ and $\textit{black}$ ones.
Yu. Baryshnikov +3 more
doaj +1 more source
On Greedy Trie Execution [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping fair coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen.
Zbigniew Gołębiewski, Filip Zagórski
doaj +1 more source
Larger than Life: Digital Creatures in a Family of Two-Dimensional Cellular Automata [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 We introduce the Larger than Life family of two-dimensional two-state cellular automata that generalize certain nearest neighbor outer totalistic cellular automaton rules to large neighborhoods.
Kellie M. Evans
doaj +1 more source
2048 Without New Tiles Is Still Hard [PDF]
, 2016 We study the computational complexity of a variant of the popular 2048 game in which no new tiles are generated after each move. As usual, instances are defined on rectangular boards of arbitrary size.
Abdelkader, Ahmed +2 more
core +1 more source
A Bijection for Directed-Convex Polyominoes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 In this paper we consider two classes of lattice paths on the plane which use \textitnorth, \textiteast, \textitsouth,and \textitwest unitary steps, beginningand ending at (0,0).We enumerate them according to the number ofsteps by means of bijective ...
Alberto Del Lungo +3 more
doaj +1 more source
Why almost all satisfiable $k$-CNF formulas are easy [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 Finding a satisfying assignment for a $k$-CNF formula $(k \geq 3)$, assuming such exists, is a notoriously hard problem. In this work we consider the uniform distribution over satisfiable $k$-CNF formulas with a linear number of clauses (clause-variable ...
Amin Coja-Oghlan +2 more
doaj +1 more source
A Note on the Approximation of Perpetuities [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 We propose and analyze an algorithm to approximate distribution functions and densities of perpetuities. Our algorithm refines an earlier approach based on iterating discretized versions of the fixed point equation that defines the perpetuity.
Margarete Knape, Ralph Neininger
doaj +1 more source