Search results for "Algorithm"

showing 10 items of 4887 documents

Balls into non-uniform bins

2014

Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…

Discrete mathematicsMathematical optimizationComputational complexity theoryComputer Networks and CommunicationsComputer scienceDistributed computingAstrophysics::Cosmology and Extragalactic AstrophysicsPhysics::Data Analysis; Statistics and ProbabilityLoad balancing (computing)BinTheoretical Computer ScienceLoad managementCapacity planningArtificial IntelligenceHardware and ArchitectureTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYBounded functionBall (bearing)Resource allocationHardware_ARITHMETICANDLOGICSTRUCTURESGame theorySoftwareMathematicsMathematicsofComputing_DISCRETEMATHEMATICS2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS)
researchProduct

The Phagocyte Lattice of Dyck Words

2006

We introduce a new lattice structure on Dyck words. We exhibit efficient algorithms to compute meets and joins of Dyck words.

Discrete mathematicsMathematics::CombinatoricsAlgebra and Number TheoryNoncrossing partitionEfficient algorithm010102 general mathematicsJoinsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)0102 computer and information sciences01 natural sciences[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]CombinatoricsComputational Theory and Mathematics010201 computation theory & mathematicsLattice (order)[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]Geometry and Topology0101 mathematicsComputer Science::Formal Languages and Automata TheoryComputingMilieux_MISCELLANEOUSMathematics
researchProduct

Optimal paths in weighted timed automata

2004

AbstractWe consider the optimal-reachability problem for a timed automaton with respect to a linear cost function which results in a weighted timed automaton. Our solution to this optimization problem consists of reducing it to computing (parametric) shortest paths in a finite weighted directed graph. We call this graph a parametric sub-region graph. It refines the region graph, a standard tool for the analysis of timed automata, by adding the information which is relevant to solving the optimal-reachability problem. We present an algorithm to solve the optimal-reachability problem for weighted timed automata that takes time exponential in O(n(|δ(A)|+|wmax|)), where n is the number of clock…

Discrete mathematicsModel checkingHybrid systemsOptimization problemGeneral Computer ScienceComputer scienceOptimal reachabilityTimed automatonBüchi automatonDirected graphTheoretical Computer ScienceAutomatonCombinatoricsDeterministic automatonReachabilityShortest path problemState spaceAutomata theoryGraph (abstract data type)Two-way deterministic finite automatonTimed automataAlgorithmComputer Science::Formal Languages and Automata TheoryComputer Science(all)Mathematics
researchProduct

Complete, exact, and efficient computations with cubic curves

2004

The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quart…

Discrete mathematicsModuli of algebraic curvesGeometric designConic sectionComputationFamily of curvesApplied mathematicsGravitational singularityAlgebraic curveSweep line algorithmMathematicsProceedings of the twentieth annual symposium on Computational geometry
researchProduct

Tensor product multiresolution analysis with error control for compact image representation

2002

A class of multiresolution representations based on nonlinear prediction is studied in the multivariate context based on tensor product strategies. In contrast to standard linear wavelet transforms, these representations cannot be thought of as a change of basis, and the error induced by thresholding or quantizing the coefficients requires a different analysis. We propose specific error control algorithms which ensure a prescribed accuracy in various norms when performing such operations on the coefficients. These algorithms are compared with standard thresholding, for synthetic and real images.

Discrete mathematicsMultiresolution analysisMathematicsofComputing_NUMERICALANALYSISWavelet transformImage processingReal imageThresholdingTensor productControl and Systems EngineeringSignal ProcessingComputer Vision and Pattern RecognitionElectrical and Electronic EngineeringChange of basisAlgorithmSoftwareMathematicsImage compressionSignal Processing
researchProduct

An extension of the Burrows-Wheeler Transform and applications to sequence comparison and data compression

2005

We introduce a generalization of the Burrows-Wheeler Transform (BWT) that can be applied to a multiset of words. The extended transformation, denoted by E, is reversible, but, differently from BWT, it is also surjective. The E transformation allows to give a definition of distance between two sequences, that we apply here to the problem of the whole mitochondrial genome phylogeny. Moreover we give some consideration about compressing a set of words by using the E transformation as preprocessing.

Discrete mathematicsMultisetBurrows-Wheeler transform; Data Compression; Mitochondrial genome phylogenyBurrows–Wheeler transformMultiplicity (mathematics)Mitochondrial genome phylogenyBurrows-Wheeler transformData CompressionSurjective functionConjugacy classSequence comparisonPreprocessorAlgorithmMathematicsData compression
researchProduct

A loopless algorithm for generating the permutations of a multiset

2003

AbstractMany combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shuffle on trajectories (defined previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects.

Discrete mathematicsMultisetMathematics::CombinatoricsGeneral Computer ScienceMultiset permutationsLoopless algorithmStructure (category theory)Context (language use)Gray codesTheoretical Computer ScienceCombinatoricsGray codePermutationLoopless generating algorithmsShuffle combinatorial objectsBinomial coefficientWord (computer architecture)Computer Science::Formal Languages and Automata TheoryMathematicsMathematicsofComputing_DISCRETEMATHEMATICSComputer Science(all)Theoretical Computer Science
researchProduct

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines

1999

The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…

Discrete mathematicsNTIMEComputational complexity theoryUnary operationCombinatoricsNondeterministic algorithmTuring machinesymbols.namesakeNon-deterministic Turing machinesymbolsUnary functionTime complexityComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Hopcroft’s Algorithm and Cyclic Automata

2008

Minimization of deterministic finite automata is a largely studied problem of the Theory of Automata and Formal Languages. It consists in finding the unique (up to isomorphism) minimal deterministic automaton recognizing a set of words. The first approaches to this topic can be traced back to the 1950’s with the works of Huffman and Moore (cf. [12,15]). Over the years several methods to solve this problem have been proposed but the most efficient algorithm in the worst case was given by Hopcroft in [11]. Such an algorithm computes in O(n log n) the minimal automaton equivalent to a given automaton with n states. The Hopcroft’s algorithm has been widely studied, described and implemented by …

Discrete mathematicsNested wordSettore INF/01 - InformaticaComputer scienceTimed automatonSturmian wordsω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesHopcroft's algorithmCombinatoricsDFA minimizationDeterministic automatonAutomata theoryQuantum finite automataNondeterministic finite automatonAlgorithmComputer Science::Formal Languages and Automata Theory
researchProduct

Hopcroft's algorithm and tree-like automata

2011

Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have running time with the same asymptotic growth rate. In particular, we provide a lower and upper bound for the running time of the algorithm expressed in terms of combinatorial properties of the trees…

Discrete mathematicsNested wordSettore INF/01 - InformaticaGeneral MathematicsAutomata minimizationω-automatonHopcroft's algorithmComputer Science ApplicationsCombinatoricsDeterministic finite automatonDFA minimizationDeterministic automatonContinuous spatial automatonQuantum finite automataAutomata theoryword treesAlgorithmComputer Science::Formal Languages and Automata TheorySoftwareMathematics
researchProduct