Search results for "Algorithm"

showing 10 items of 4887 documents

TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES

2013

We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternating machines working within strong, middle and weak space, and processing general or unary inputs. In most cases, we are able to show that the lower bounds for one-way machines remain tight in the real-time case. Memory lower bounds for nonregular acceptance on other devices are also addressed. It is shown that increasing the number of stacks of real-time pushdown automata can result in exponential improvement in the total amount of space usage for nonregular language recognition.

Discrete mathematicsNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESUnary operationComputationTheory of computationComputer Science (miscellaneous)Pushdown automatonSpace (mathematics)MathematicsLanguage recognitionExponential functionInternational Journal of Foundations of Computer Science
researchProduct

Some properties of [tr(Q2p)]12p with application to linear minimax estimation

1990

Abstract A nondifferentiable minimization problem is considered which occurs in linear minimax estimation. This problem is solved by replacing the nondifferentiable maximal eigenvalue of a real nonnegative definite matrix Q with [tr( Q 2 p )] 1/2 p . It is shown that any descent algorithm with inexact step-length rule can be used to obtain linear minimax estimators for the parameter vector of a parameter-restricted linear model.

Discrete mathematicsNumerical AnalysisAlgebra and Number TheoryMinimization problemLinear modelMathematics::Optimization and ControlMinimaxMinimax approximation algorithmMatrix (mathematics)Discrete Mathematics and CombinatoricsGeometry and TopologyMinimax estimatorDescent algorithmEigenvalues and eigenvectorsMathematicsLinear Algebra and its Applications
researchProduct

New Developments in Quantum Algorithms

2010

In this survey, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(\sqrt{N}). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N^{2.37...}) where N is the size of the system, the …

Discrete mathematicsOR gateTrue quantified Boolean formulaGeneralizationTheoryofComputation_GENERAL0102 computer and information sciencesSystem of linear equations01 natural sciences010201 computation theory & mathematicsQuantum stateComputerSystemsOrganization_MISCELLANEOUS0103 physical sciencesQuantum algorithm010306 general physicsBoolean functionQuantumMathematics
researchProduct

On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching

2010

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of Parikh vector q (a “jumbled string”) in the text s requires to find a substring t of s with p(t) = q. The corresponding decision problem is to verify whether at least one such match exists. So, for example for the alphabet Σ = {a, b, c}, the string s = abaccbabaaa has Parikh vector p(s) = (6,3,2), and the Parikh vector q = (2,1,1) appears once in s in position (1,4). Like its more precise counterpart, the renown Exact String Matching, Jumbled Pattern Matching has ubiquitous applications, e.g., string matching with a dyslectic word processor, table rearrangements, …

Discrete mathematicsParikh vectors jumbled pattern matching scrabble approximate pattern matching000AnagramParikh vectorsString searching algorithmApproximate string matchingDecision problemalgorithmsData structureJumbled Pattern MatchingSubstringscrabbleapproximate pattern matchingString MatchingWavelet TreePattern matchingMathematics
researchProduct

Fine and Wilf's Theorem for Three periods and a Generalization of Sturmian Words

1999

AbstractWe extend the theorem of Fine and Wilf to words having three periods. We then define the set 3-PER of words of maximal length for which such result does not apply. We prove that the set 3-PER and the sequences of complexity 2n + 1, introduced by Arnoux and Rauzy to generalize Sturmian words, have the same set of factors.

Discrete mathematicsPeriodicityEuclid's algorithmCombinatorics on wordsGeneral Computer ScienceGeneralizationSturmian wordSturmian wordsTheoretical Computer ScienceCombinatoricsSet (abstract data type)Combinatorics on wordsWord lengthComputer Science(all)Mathematics
researchProduct

A note on the packing of two copies of some trees into their third power

2003

Abstract It is proved in [1] that if a tree T of order n is not a star, then there exists an edge-disjoint placement of two copies of this tree into its fourth power. In this paper, we prove the packing of some trees into their third power.

Discrete mathematicsPermutationFourth powerApplied MathematicsA* search algorithmlaw.inventionPackingCombinatoricslawOrder (group theory)Tree (set theory)Power treeEmbeddingPlacementMathematicsApplied Mathematics Letters
researchProduct

Analysis of properties of recombination operators proposed for the node-depth encoding

2011

The node-depth encoding is a representation for evolutionary algorithms applied to tree problems. Its represents trees by storing the nodes and their depth in a proper ordered list. The original formulation of the node-depth encoding has only mutation operators as the search mechanism. Although it is computationally efficient, the exclusive use of mutation restricts the exploration of the search space and the algorithm convergence. Then, this work proposes two specific recombination operators to improve the convergence of the algorithm using the node-depth encoding representation. These operators are based on recombination operators for permutation representations. Analysis of the proposed …

Discrete mathematicsPermutationTree (data structure)Encoding (memory)Mutation (genetic algorithm)Convergence (routing)Evolutionary algorithmQuantitative Biology::Populations and EvolutionNode (circuits)Representation (mathematics)AlgorithmMathematicsProceedings of the 13th annual conference companion on Genetic and evolutionary computation
researchProduct

A Polynomial Quantum Query Lower Bound for the Set Equality Problem

2004

The set equality problem is to tell whether two sets A and B are equal or disjoint under the promise that one of these is the case. This problem is related to the Graph Isomorphism problem. It was an open problem to find any ω(1) query lower bound when sets A and B are given by quantum oracles. We will show that any error-bounded quantum query algorithm that solves the set equality problem must evaluate oracles \(\Omega(\sqrt[5]{\frac{n}{\ln n}})\) times, where n=|A|=|B|.

Discrete mathematicsPolynomial (hyperelastic model)CombinatoricsOpen problemGraph isomorphism problemTheoryofComputation_GENERALCollision problemQuantum algorithmDisjoint setsIsomorphismUpper and lower boundsMathematics
researchProduct

Deciding reachability for planar multi-polynomial systems

1996

In this paper we investigate the decidability of the reachability problem for planar non-linear hybrid systems. A planar hybrid system has the property that its state space corresponds to the standard Euclidean plane, which is partitioned into a finite number of (polyhedral) regions. To each of these regions is assigned some vector field which governs the dynamical behaviour of the system within this region. We prove the decidability of point to point and region to region reachability problems for planar hybrid systems for the case when trajectories within the regions can be described by polynomials of arbitrary degree.

Discrete mathematicsPolynomialReachability problemReachabilityTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYHybrid systemState spaceVector fieldFinite setMathematicsofComputing_DISCRETEMATHEMATICSDecidabilityMathematics
researchProduct

On the size of transducers for bidirectional decoding of prefix codes

2012

In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [ IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X . We find some bounds of such a number of states in relation wi…

Discrete mathematicsPrefix codeBlock codeSettore INF/01 - InformaticaGeneral MathematicsConcatenated error correction codeprefix codeList decodingSerial concatenated convolutional codesSequential decodingLinear codeComputer Science ApplicationsPrefixbilateral decodingVariable length codetransducersAlgorithmComputer Science::Formal Languages and Automata TheorySoftwareMathematics
researchProduct