Search results for "Algorithm"

showing 10 items of 4887 documents

Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

2017

We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The “memoryless” term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. As an application of communicatio…

Discrete mathematicsSublinear functionComputational complexity theory010102 general mathematics0102 computer and information sciencesFunction (mathematics)01 natural sciencesUpper and lower boundsCombinatorics010201 computation theory & mathematicsQuantum algorithm0101 mathematicsQuantum information scienceCommunication complexityQuantum computerMathematics
researchProduct

Quantum Random Walks – New Method for Designing Quantum Algorithms

2008

Quantum walks are quantum counterparts of random walks. In the last 5 years, they have become one of main methods of designing quantum algorithms. Quantum walk based algorithms include element distinctness, spatial search, quantum speedup of Markov chains, evaluation of Boolean formulas and search on "glued trees" graph. In this talk, I will describe the quantum walk method for designing search algorithms and show several of its applications.

Discrete mathematicsTheoretical computer scienceHeterogeneous random walk in one dimensionQuantum annealingTheoryofComputation_GENERALRandom walkMathematics::ProbabilitySearch algorithmComputerSystemsOrganization_MISCELLANEOUSQuantum phase estimation algorithmQuantum algorithmQuantum walkQuantum computerMathematics
researchProduct

Probabilities to Accept Languages by Quantum Finite Automata

1999

We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the corresponding probability for the preceding language in the hierarchy. These probabilities converge to 1/2.

Discrete mathematicsTheoretical computer scienceNested wordFinite-state machineHierarchy (mathematics)Computer scienceComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Turing machinesymbols.namesakeNonlinear Sciences::Exactly Solvable and Integrable SystemsRegular languageProbabilistic automatonAnalytical hierarchysymbolsComputer Science::Programming LanguagesQuantum finite automataQuantum algorithmNondeterministic finite automaton
researchProduct

Finite State Transducers with Intuition

2010

Finite automata that take advice have been studied from the point of view of what is the amount of advice needed to recognize nonregular languages. It turns out that there can be at least two different types of advice. In this paper we concentrate on cases when the given advice contains zero information about the input word and the language to be recognized. Nonetheless some nonregular languages can be recognized in this way. The help-word is merely a sufficiently long word with nearly maximum Kolmogorov complexity. Moreover, any sufficiently long word with nearly maximum Kolmogorov complexity can serve as a help-word. Finite automata with such help can recognize languages not recognizable …

Discrete mathematicsTheoretical computer scienceNested wordKolmogorov complexityComputer scienceComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonKolmogorov structure functionProbabilistic automatonQuantum finite automataNondeterministic finite automatonComputer Science::Formal Languages and Automata Theory
researchProduct

Nondeterministic Moore automata and Brzozowski's minimization algorithm

2012

AbstractMoore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. We propose an algorithm that is a variant of Brzozowski’s minimization algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice. Moreover, we explore more general classes of NMA and analyze the applicability of the algorithm. For some of such classes the algorith…

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESGeneral Computer ScienceBrzozowski’s minimization algorithmSettore INF/01 - InformaticaPowerset constructionAutomata minimizationBüchi automatonNonlinear Sciences::Cellular Automata and Lattice GasesTheoretical Computer ScienceNondeterministic algorithmDeterministic finite automatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDFA minimizationDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonBrzozowski's minimization algorithmComputer Science::Formal Languages and Automata TheoryComputer Science(all)MathematicsNondeterministic Moore automata
researchProduct

Standard Sturmian words and automata minimization algorithms

2015

The study of some close connections between the combinatorial properties of words and the performance of the automata minimization process constitutes the main focus of this paper. These relationships have been, in fact, the basis of the study of the tightness and the extremal cases of Hopcroft's algorithm, that is, up to now, the most efficient minimization method for deterministic finite state automata. Recently, increasing attention has been paid to another minimization method that, unlike the approach proposed by Hopcroft, is not based on refinement of the set of states of the automaton, but on automata operations such as determinization and reverse, and is also applicable to non-determ…

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordFinite-state machineGeneral Computer ScienceAutomata minimizationComputer Science (all)ω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesStandard Sturmian wordTheoretical Computer ScienceAutomatonCombinatoricsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDFA minimizationAutomata theoryQuantum finite automataBrzozowski's minimization algorithmTime complexityAlgorithmComputer Science::Formal Languages and Automata TheoryMathematicsTheoretical Computer Science
researchProduct

Nondeterministic Moore Automata and Brzozowski’s Algorithm

2011

Moore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. In this paper we propose an algorithm that is a variant of Brzozowski's algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice.

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESSettore INF/01 - InformaticaPowerset constructionBüchi automatonNonlinear Sciences::Cellular Automata and Lattice GasesNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonDFA minimizationDeterministic automatonTwo-way deterministic finite automatonMoore automata minimization Brzozowski'algorithmNondeterministic finite automatonAlgorithmComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

On Extremal Cases of Hopcroft’s Algorithm

2009

In 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 sequences of refinements of the set of the states that lead to the final partition. We find an infinite family of binary automata for which such a process is unique. Some recent papers (cf. [3,7,1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated to circular words. However, automata minimization can be achieved also in linear time when the alphabet has only one letter (cf. [14]), so in …

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESSettore INF/01 - InformaticaUnary operationBinary numberHopcroft's algorithmNonlinear Sciences::Cellular Automata and Lattice GasesAutomatonCombinatoricsSet (abstract data type)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonDFA minimizationMinificationAlgorithmTime complexityComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Minimal nontrivial space complexity of probabilistic one- way turing machines

2005

Languages recognizable in o(log log n) space by probabilistic one — way Turing machines are proved to be regular. This solves an open problem in [4].

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESSuper-recursive algorithmProbabilistic Turing machineLinear speedup theoremNSPACEDescription numberCombinatoricsTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESNon-deterministic Turing machinesymbolsTime hierarchy theoremComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards

2007

The guarded fragment of first-order logic, GF, enjoys the finite model property, so the satisfiability and the finite satisfiability problems coincide. We are concerned with two extensions of the two-variable guarded fragment that do not possess the finite model property, namely, GF2 with equivalence and GF2 with transitive guards. We prove that in both cases every finitely satisfiable formula has a model of at most double exponential size w.r.t. its length. To obtain the result we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NEXPTIME-upper bound on the complexity of the fini…

Discrete mathematicsTransitive relationFinite model propertyDouble exponential functionEquivalence (formal languages)AlgorithmSatisfiabilityFinite satisfiabilityMathematics
researchProduct