Search results for "Complexity"
showing 10 items of 1094 documents
Longest Motifs with a Functionally Equivalent Central Block
2004
International audience; This paper presents a generalization of the notion of longest repeats with a block of k don't care symbols introduced by [Crochemore et al., LATIN 2004] (for k fixed) to longest motifs composed of three parts: a first and last that parameterize match (that is, match via some symbol renaming, initially unknown), and a functionally equivalent central block. Such three-part motifs are called longest block motifs. Different types of functional equivalence, and thus of matching criteria for the central block are considered, which include as a subcase the one treated in [Crochemore et al., LATIN 2004] and extend to the case of regular expressions with no Kleene closure or …
An Efficient Algorithm for the Generation of Z-Convex Polyominoes
2014
We present a characterization of Z-convex polyominoes in terms of pairs of suitable integer vectors. This lets us design an algorithm which generates all Z-convex polyominoes of size n in constant amortized time.
Algorithmic Information Theory and Computational Complexity
2013
We present examples where theorems on complexity of computation are proved using methods in algorithmic information theory. The first example is a non-effective construction of a language for which the size of any deterministic finite automaton exceeds the size of a probabilistic finite automaton with a bounded error exponentially. The second example refers to frequency computation. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. A transducer is a finite-state automaton with an input and an output. We consider the possibilities of probabilistic and frequency transducers and prove sever…
Transition Function Complexity of Finite Automata
2011
State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.
On positive P
2002
Continuing a line of research opened up by Grigni and Sipser (1992) and further pursued by Stewart (1994), we show that a wide variety of equivalent characterizations of P still remain equivalent when restricted to be positive. All these restrictions thus define the same class posP, a proper subclass of monP, the class of monotone problems in P. We also exhibit complete problems for posP under very weak reductions.
Incremental termination proofs and the length of derivations
1991
Incremental termination proofs, a concept similar to termination proofs by quasi-commuting orderings, are investigated. In particular, we show how an incremental termination proof for a term rewriting system T can be used to derive upper bounds on the length of derivations in T. A number of examples show that our results can be applied to yield (sharp) low-degree polynomial complexity bounds.
Lower space bounds for randomized computation
1994
It is a fundamental problem in the randomized computation how to separate different randomized time or randomized space classes (c.f., e.g., [KV87, KV88]). We have separated randomized space classes below log n in [FK94]. Now we have succeeded to separate small randomized time classes for multi-tape 2-way Turing machines. Surprisingly, these “small” bounds are of type n+f(n) with f(n) not exceeding linear functions. This new approach to “sublinear” time complexity is a natural counterpart to sublinear space complexity. The latter was introduced by considering the input tape and the work tape as separate devices and distinguishing between the space used for processing information and the spa…
Padding and the expressive power of existential second-order logics
1998
Padding techniques are well-known from Computational Complexity Theory. Here, an analogous concept is considered in the context of existential second-order logics. Informally, a graph H is a padded version of a graph G, if H consists of an isomorphic copy of G and some isolated vertices. A set A of graphs is called weakly expressible by a formula ϕ in the presence of padding, if ϕ is able to distinguish between (sufficiently) padded versions of graphs from A and padded versions of graphs that are not in A.
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
2017
We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to “width” complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called “reordering”), which allows to build Boolean function g from Boolean Function f, such that if for f we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function g, but for any order. Using it we construct the total function REQ which deterministic OBDD complexity is \(2^{\varOmega (n/log n)}\) and present quantum OBD…
If P ≠ NP then Some Strongly Noninvertible Functions Are Invertible
2001
Rabi, Rivest, and Sherman alter the standard notion of noninvertibility to a new notion they call strong noninvertibility, and show--via explicit cryptographic protocols for secret-key agreement ([RS93, RS97] attribute this to Rivest and Sherman) and digital signatures [RS93, RS97]--that strongly noninvertible functions would be very useful components in protocol design. Their definition of strong noninvertibility has a small twist ("respecting the argument given") that is needed to ensure cryptographic usefulness. In this paper, we show that this small twist has a large, unexpected consequence: Unless P = NP, some strongly noninvertible functions are invertible.