Search

Any Boolean function can be defined by a Boolean circuit, provided we may use sufficiently strong functions in its gates. On the other hand, what Boolean functions can be defined depends on these gate functions: Each set B of gate functions defines the class of Boolean functions that can be defined by circuits over B. Although these classes have been known since the 1920s, their computational complexity was never investigated. In this paper we will study how difficult it is to decide for a Boolean function f and a class B, whether f is in B. Moreover, we will provide such a decision algorithm with additional information: How difficult is it to decide whether or not f is in B, provided we already know a circuit for f, but with gates from another class A? Given such a circuit, we know that f is in A. Is the problem harder if we do not have a concrete representation for f, but still know that it is from A? For nearly all possible combinations, we show that this is not the case, and that the problem is either in P or coNP-complete. [ABSTRACT FROM AUTHOR]

We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n). [ABSTRACT FROM AUTHOR]