Search results for "Algorithm"

showing 10 items of 4887 documents

The Alternating BWT: an algorithmic perspective

2020

Abstract The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures, with important applications in several areas in science and engineering. The Alternating Burrows-Wheeler Transform (ABWT) is another transformation recently introduced in Gessel et al. (2012) [21] and studied in the field of Combinatorics on Words. It is analogous to the BWT, except that it uses an alternating lexicographical order instead of the usual one. Building on results in Giancarlo et al. (2018) [23] , where we have shown that BWT and ABWT are part of a larger class of reversible transformations, …

Discrete mathematicsFOS: Computer and information sciencesSettore INF/01 - InformaticaGeneral Computer ScienceBasis (linear algebra)Computer scienceAlternating Burrows-Wheeler TransformGalois wordRank-invertibilityField (mathematics)Data structureTheoretical Computer ScienceTransformation (function)Difference cover algorithmComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)Time complexityAlternating Burrows-Wheeler Transform; Difference cover algorithm; Galois word; Rank-invertibilityWord (computer architecture)Data compression
researchProduct

Minimal forbidden words and symbolic dynamics

1996

We introduce a new complexity measure of a factorial formal language L: the growth rate of the set of minimal forbidden words. We prove some combinatorial properties of minimal forbidden words. As main result we prove that the growth rate of the set of minimal forbidden words for L is a topological invariant of the dynamical system defined by L.

Discrete mathematicsFactorial010102 general mathematics[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Symbolic dynamicsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciencesInvariant (physics)16. Peace & justice01 natural sciencesCombinatorics010201 computation theory & mathematicsTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMSInformation complexityFormal language0101 mathematicsComputer Science::Formal Languages and Automata TheoryComputingMilieux_MISCELLANEOUSMathematicsofComputing_DISCRETEMATHEMATICSMathematics
researchProduct

Team learning as a game

1997

A machine FIN-learning machine M receives successive values of the function f it is learning; at some point M outputs conjecture which should be a correct index of f. When n machines simultaneously learn the same function f and at least k of these machines outut correct indices of f, we have team learning [k,n]FIN. Papers [DKV92, DK96] show that sometimes a team or a robabilistic learner can simulate another one, if its probability p (or team success ratio k/n) is close enough. On the other hand, there are critical ratios which mae simulation o FIN(p2) by FIN(p1) imossible whenever p2 _< r < p1 or some critical ratio r. Accordingly to [DKV92] the critical ratio closest to 1/2 rom the let is…

Discrete mathematicsFinite-state machineConjectureTeam learningAlgorithm complexityFunction (mathematics)Critical ratioAlgorithmMathematics
researchProduct

Nondeterministic operations on finite relational structures

1998

Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…

Discrete mathematicsFinite-state machineGeneral Computer ScienceComputer scienceLogicFormal languages (recognizable and context-free sets transducers)Unbounded nondeterminismMonad (functional programming)Symbolic computationHypergraphsFirst-order logicLogical theoryDecidabilityTheoretical Computer ScienceNondeterministic algorithmAlgebraDeterministic automatonFormal languageUniversal algebraEquivalence relationTree transducersRewritingComputer Science(all)Theoretical Computer Science
researchProduct

On extremal cases of Hopcroft’s algorithm

2010

AbstractIn this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata as…

Discrete mathematicsFinite-state machineGeneral Computer ScienceUnary operationWord treesStandard treesAutomatonTheoretical Computer ScienceCombinatoricsDeterministic finite automatonDFA minimizationDeterministic automatonHopcroft’s minimization algorithmTree automatonDeterministic finite state automataTime complexityAlgorithmComputer Science::Formal Languages and Automata TheoryMathematicsComputer Science(all)Theoretical Computer Science
researchProduct

Superiority Of One-Way And Realtime Quantum Machines

2012

In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime push…

Discrete mathematicsFinite-state machineTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESGeneral MathematicsPushdown automaton0102 computer and information sciences02 engineering and technologyω-automaton01 natural sciencesComputer Science ApplicationsNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringQuantum finite automataAutomata theory020201 artificial intelligence & image processingAlgorithmSoftwareComputer Science::Formal Languages and Automata TheoryQuantum cellular automatonMathematicsQuantum computer
researchProduct

A Graph Based Algorithm For Intersection Of Subdivision Surfaces

2003

Computing surface intersections is a fundamental problem in geometric modeling. Any boolean operation can be seen as an intersection calculation followed by a selection of the parts necessary for building the surface of the resulting object. A robust and efficient algorithm to compute intersection on subdivision surfaces (surfaces generated by the Loop scheme) is proposed here. This algorithm relies on the concept of a bipartite graph which allows the reduction of the number of faces intersection tests. Intersection computations are accelerated by the use of the bipartite graph and the neighborhood of intersecting faces at a given level of subdivision to deduce intersecting faces at the fol…

Discrete mathematicsFoster graph[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS][ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM][INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Intersection number (graph theory)Intersection graphlaw.inventionCombinatorics[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]IntersectionlawHomeomorphism (graph theory)Subdivision surfaceCircle graphAlgorithmComputingMilieux_MISCELLANEOUS[ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]ComputingMethodologies_COMPUTERGRAPHICSMathematicsDistance-hereditary graph
researchProduct

Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time

2002

This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183--236]. DLIN is essentially the class of all functions that can be computed in linear time on a Random Access Machine which uses only numbers of linear value during its computations. The algebraic characterizations are in terms of recursion schemes that define unary functions. One of these schemes defines several functions simultaneously, while the other one defines only one function. From the algebraic characterizations, we derive two complete problems for DLIN under new, very strict, and mac…

Discrete mathematicsGeneral Computer ScienceUnary operationGeneral Mathematics[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Recursion (computer science)[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyFunction (mathematics)01 natural sciencesRandom-access machine010201 computation theory & mathematicsCompleteness (order theory)0202 electrical engineering electronic engineering information engineeringComplexity class020201 artificial intelligence & image processingAlgebraic numberTime complexityMathematics
researchProduct

On the hardness of optimization in power-law graphs

2008

Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…

Discrete mathematicsGeneral Computer ScienceVertex coverPower-law graphsGraph construction algorithmsClique (graph theory)Theoretical Computer ScienceCombinatoricsIndifference graphDominating setChordal graphIndependent setNP-hardnessCombinatorial optimizationGraph optimization problemsMaximal independent setMathematicsComputer Science(all)Theoretical Computer Science
researchProduct

Bounds for minimum feedback vertex sets in distance graphs and circulant graphs

2008

Graphs and Algorithms

Discrete mathematicsGeneral Computer Science[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Neighbourhood (graph theory)[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Feedback arc setTheoretical Computer ScienceCombinatorics[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Circulant graphChordal graphIndependent setDiscrete Mathematics and CombinatoricsMaximal independent setFeedback vertex setRegular graph[ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]MathematicsMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct