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.
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.
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 …
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, …
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.
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.
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 …
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|.
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.
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…