Search results for "Algorithm"

showing 10 items of 4887 documents

Algorithm 105: Newton Maehly

1962

General Computer ScienceAlgorithmMathematicsCommunications of the ACM
researchProduct

Algorithm 153: gomory

1963

General Computer ScienceAlgorithmMathematicsCommunications of the ACM
researchProduct

Higher-Fidelity Frugal and Accurate Quantile Estimation Using a Novel Incremental <italic>Discretized</italic> Paradigm

2018

Traditional pattern classification works with the moments of the distributions of the features and involves the estimation of the means and variances. As opposed to this, more recently, research has indicated the power of using the quantiles of the distributions because they are more robust and applicable for non-parametric methods. The estimation of the quantiles is even more pertinent when one is mining data streams. However, the complexity of quantile estimation is much higher than the corresponding estimation of the mean and variance, and this increased complexity is more relevant as the size of the data increases. Clearly, in the context of infinite data streams, a computational and sp…

General Computer ScienceDiscretizationLearning automataData stream miningComputer scienceGeneral EngineeringEstimatorContext (language use)02 engineering and technologyRobustness (computer science)0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingGeneral Materials ScienceAlgorithmQuantileIEEE Access
researchProduct

Word assembly through minimal forbidden words

2006

AbstractWe give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.

General Computer ScienceFragment assemblyFactor automaton[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technology01 natural sciencesMinimal forbidden wordTheoretical Computer ScienceCombinatorics0202 electrical engineering electronic engineering information engineeringFinite setComputingMilieux_MISCELLANEOUSCombinatorics on wordMathematicsShortest superstringCombinatorics on wordsRepetition index16. Peace & justice010201 computation theory & mathematics020201 artificial intelligence & image processingAlphabetConstant (mathematics)Word (computer architecture)Computer Science::Formal Languages and Automata TheoryComputer Science(all)
researchProduct

Mathematical logic and quantum finite state automata

2009

AbstractThis paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.

General Computer ScienceMeasure-many quantum finite-state automataComputational logicMultimodal logicQuantum dot cellular automatonIntermediate logicMeasure-once quantum finite-state automataNonlinear Sciences::Cellular Automata and Lattice GasesTheoretical Computer ScienceAlgebraTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESModular logicComputerSystemsOrganization_MISCELLANEOUSComputer Science::Logic in Computer ScienceQuantum finite automataDynamic logic (modal logic)Automata theoryQuantum finite-state automataFirst-order logicAlgorithmComputer Science::Formal Languages and Automata TheoryMathematicsQuantum cellular automatonComputer Science(all)Theoretical Computer Science
researchProduct

From Nerode's congruence to Suffix Automata with mismatches

2009

AbstractIn this paper we focus on the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with Sk. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of Sk to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the…

General Computer ScienceOpen problem[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyString searching algorithm01 natural sciencesTheoretical Computer ScienceCombinatoricsDeterministic automatonSuffix automata0202 electrical engineering electronic engineering information engineeringCombinatorics on words Indexing Suffix Automata Languages with mismatches Approximate string matchingMathematicsDiscrete mathematicsCombinatorics on wordsApproximate string matchingSettore INF/01 - InformaticaLanguages with mismatchesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)PrefixCombinatorics on wordsDeterministic finite automaton010201 computation theory & mathematicsSuffix automatonIndexing020201 artificial intelligence & image processingSuffixComputer Science::Formal Languages and Automata TheoryComputer Science(all)
researchProduct

Motif patterns in 2D

2008

AbstractMotif patterns consisting of sequences of intermixed solid and don’t-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of …

General Computer SciencePattern discoveryTheoretical Computer ScienceCombinatoricsExponential growthMotif extraction Pattern discovery 2D MotifsMotif2D irredundant motifsMotif (music)Pattern matchingRemainderPattern matchingDesign and analysis of algorithmsMathematicsComputer Science(all)Theoretical Computer Science
researchProduct

Low-cost approximate reconstructing of heterogeneous microstructures

2016

We propose an approximate reconstruction of random heterogeneous microstructures using the two-exponent power-law (TEPL). This rule originates from the entropic descriptor (ED) that is a multi-scale measure of spatial inhomogeneity for a given microstructure. A digitized target sample is a cube of linear size L in voxels. Then, a number of trial configurations can be generated by a model of overlapping spheres of a fixed radius, which are randomly distributed on a regular lattice. The TEPL describes the averaged maximum of the ED as a function of the phase concentration and the radius. Thus, it can be used to determine the radius. The suggested approach is tested on surrogate samples of cer…

General Computer SciencePhase (waves)FOS: Physical sciencesGeneral Physics and Astronomyentropic descriptor02 engineering and technologycomputer.software_genre01 natural sciencesMeasure (mathematics)heterogeneous microstructuresVoxel0103 physical sciencesGeneral Materials Science010306 general physicsCondensed Matter - Statistical MechanicsMathematicsStatistical Mechanics (cond-mat.stat-mech)3D microstructure reconstructiontwo-exponent power-lawGeneral ChemistryRadiusFunction (mathematics)021001 nanoscience & nanotechnologyMicrostructureSample (graphics)Computational MathematicsMechanics of MaterialsSPHERES0210 nano-technologycomputerAlgorithm
researchProduct

On the exhaustive generation of k-convex polyominoes

2017

The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.

General Computer SciencePolyomino0102 computer and information sciences02 engineering and technologyComputer Science::Computational Geometry01 natural sciencesConvexityTheoretical Computer ScienceCombinatoricsCAT algorithmIntegerExhaustive generation0202 electrical engineering electronic engineering information engineeringConvex polyominoeConvexity K-convex polyominoes.Convex polyominoesComputer Science::DatabasesMathematicsDiscrete mathematicsAmortized analysisMathematics::CombinatoricsDegree (graph theory)Settore INF/01 - InformaticaComputer Science (all)Regular polygonMonotone polygon010201 computation theory & mathematicsPath (graph theory)020201 artificial intelligence & image processingCAT algorithms; Convex polyominoes; Exhaustive generation;CAT algorithms
researchProduct

Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes

2006

A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…

General Computer SciencePower graphAstrophysics::High Energy Astrophysical PhenomenaInduced subgraphDisjoint setsAstrophysics::Cosmology and Extragalactic Astrophysics[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Theoretical Computer ScienceCombinatoricssymbols.namesakeTriangle meshGreedy algorithmDiscrete Mathematics and CombinatoricsAstrophysics::Solar and Stellar AstrophysicsColoringPolygon meshProduct graphMathematicsComputingMethodologies_COMPUTERGRAPHICSDiscrete mathematicsGreedy algorithm.lcsh:MathematicsApproximation algorithmGraph theory[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]Cartesian productlcsh:QA1-939Approximation algorithmPlanar graphGraph theory[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]symbolsMulticoloring
researchProduct