Displaying similar documents to “Division in logspace-uniform NC1”

On the Average Case Complexity of Some P-complete Problems

Maria Serna, Fatos Xhafa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that some classical P-complete problems can be solved efficiently in NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by ( ln 4 + (1))log , asymptotically with high probability, where is the instance size.

Computing -Free NFA from Regular Expressions in ( log()) Time

Christian Hagenah, Anca Muscholl (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The standard procedure to transform a regular expression of size to an -free nondeterministic finite automaton yields automata with states and ( ) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic showed how to build an -free NFA with only ( log()) transitions. The current lower bound on the number of transitions is Ω( log()). A rough running time estimation for the common follow sets (CFS) construction proposed...

Factoring and testing primes in small space

Viliam Geffert, Dana Pardubská (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We discuss how much space is sufficient to decide whether a unary given number is a prime. We show that (log log ) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log ) and also in accept–ASPACE(log log ). Moreover, if the given...

Semi-continuité inférieure d'intégrales multiples et d'intégrandes convergentes

Zhiping Li (2010)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

Lower semicontinuity of multiple integrals ∫ and ∫ are studied. It is proved that the two can derive from each other under certain general hypotheses such as uniform lower compactness property and locally uniform convergence of . The result is applied to obtain some general lower semicontinuity theorems on multiple integrals with quasiconvex integrand ƒ, while are not required to be quasiconvex.

Random Generation for Finitely Ambiguous Context-free Languages

Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in ( log ) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.