Communication Complexity Method for Measuring Nondeterminism in Finite Automata

While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the concept of communication complexity is applied in order to achieve progress in this problem area. The main results are as follows:1. Deterministic communication complexity provides lower bounds on the size of nfa's with bounded unambiguity. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified and presented in a uniform way.2. There is a family of languages KON_k² with an exponential size gap between nfa's with polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially provides an answer to the open problem posed by B. Ravikumar and O. Ibarra (1989, SIAM J. Comput.18, 1263–1282) and H. Leung (1998, SIAM J. Comput.27, 1073–1082).     

The Complexity of the Exponential Output Size Problem for Top-Down and Bottom-Up Tree Transducers,

The exponential output size problem is to determine whether the size of output trees of a tree transducer grows exponentially in the size of input trees. In this paper the complexity of this problem is studied. It is shown to be NL-complete for total top-down tree transducers, DEXPTIME-complete for general top-down tree transducers, and P-complete for bottom-up tree transducers.     

Optimal Computing the Chessboard Distance Transform on Parallel Processing Systems

Thedistance transform(DT) is an image computation tool which can be used to extract the information about the shape and the position of the foreground pixels relative to each other. It converts a binary image into a grey-level image, where each pixel has a value corresponding to the distance to the nearest foreground pixel. The time complexity for computing the distance transform is fully dependent on the different distance metrics. Especially, the more exact the distance transform is, the worse execution time reached will be. Nowadays, quite often thousands of images are processed in a limited time. It seems quite impossible for a sequential computer to do such a computation for the distance transform in real time. In order to provide efficient distance transform computation, it is considerably desirable to develop a parallel algorithm for this operation. In this paper, based on the diagonal propagation approach, we first provide anO(N²) time sequential algorithm to compute thechessboard distance transform(CDT) of anN×Nimage, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. Following the mapping as proposed by Lee and Horng, the algorithm for the medial axis transform is also efficiently derived. The medial axis transform of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. The proposed parallel algorithms are composed of a set of prefix operations. In each prefix operation phase, only increase (add-one) operation and minimum operation are employed. So, the algorithms are especially efficient in practical applications.     

A Monadic Second-Order Definition of the Structure of Convex Hypergraphs

We consider finite hypergraphs with hyperedges defined as sets of vertices of unbounded cardinality. Each such hypergraph has a unique modular decomposition, which is a tree, the nodes of which correspond to certain subhypergraphs (induced by certain sets of vertices called strong modules) of the considered hypergraph. One can define this decomposition by monadic second-order (MS) logical formulas. Such a hypergraph is convex if the vertices are linearly ordered in such a way that the hyperedges form intervals. Our main result says that the unique linear order witnessing the convexity of a prime hypergraph (i.e., of one, the modular decomposition of which is trivial) can be defined in MS logic. As a consequence, we obtain that if a set of bipartite graphs that correspond (in the usual way) to convex hypergraphs has a decidable monadic second-order theory (which means that one can decide whether a given MS formula is satisfied in some graph of the set) then it has bounded clique-width. This yields a new case of validity of a conjecture which is still open.     

Nonerasing, Counting, and Majority over the Linear Time Hierarchy

In this paper, we investigate several extensions of the linear time hierarchy (denoted by LTH). We first prove that it is not necessary to erase the oracle tape between two successive oracle calls, thereby lifting a common restriction on LTH machines. We also define a natural counting extension of LTH and show that it corresponds to a robust notion of counting bounded arithmetic predicates. Finally, we show that the computational power of the majority operator is equivalent to that of the exact counting operator in both contexts.     

Working with ARMs: Complexity Results on Atomic Representations of Herbrand Models

An atomic representation of a Herbrand model (ARM) is a finite set of (not necessarily ground) atoms over a given Herbrand universe. Each ARM represents a possibly infinite Herbrand interpretation. This concept has emerged independently in different branches of computer science as a natural and useful generalization of the concept of finite Herbrand interpretation. It was shown that several recursively decidable problems on finite Herbrand models (or interpretations) remain decidable on ARMs.The following problems are essential when working with ARMs: Deciding the equivalence of two ARMs, deciding subsumption between ARMs, and evaluating clauses over ARMs. These problems were shown to be decidable, but their computational complexity has remained obscure so far. The previously published decision algorithms require exponential space. In this paper, we prove that all mentioned problems are coNP-complete.     

One-way simple multihead finite automata

The first half of this paper investigates the accepting powers of various types of simple one-way multihead finite automata. It is shown that(1)for each k?1, simple one-way (k+1)-head finite automata are more powerful than simple one-way k-head finite automata.(2)for each k?2, nondeterministic simple one-way k-head finite automata are more powerful than deterministic ones, and(3)for each k?2, sensing simple one-way k-head finite automata are more powerful than non-sensing ones.In the latter half, closure properties for various types of simple one-way multihead finite automata are investigated.Finally, we demonstrate that languages accepted by nondeterministic sensing simple one-way 2-head finite automata are related to some open problem concerning deterministic and nondeterministic tape-bounded Turing computations.     

The Power of Nondeterminism and Randomness for Oblivious Branching Programs

Abstract. This paper abstracts and generalizes the known approaches for proving lower bounds on the size of various variants of oblivious branching programs (oblivious BPs for short), providing an easy-to-use technique which works for all nondeterministic and randomized modes of acceptance. The technique is applied to obtain the following results concerning the power of nondeterminism and randomness for oblivious BPs: <p>— Oblivious read-once BPs, better known as OBDDs (ordered binary decision diagrams), are used in many applications and their structure is well understood in the deterministic case. It has been open so far to compare the power of nondeterministic OBDDs with so-called partitioned BDDs which are a variant of nondeterministic branching programs also used in practice. A k -partitioned BDD has a nondeterministic node at the top by which one out of k deterministic OBDDs with possibly different variable orders is chosen. It is proven here that the two models are incomparable as long as k is bounded by a logarithmic function in the input length. <p>— It is shown that deterministic oblivious read-k -times BPs for an explicitly defined function require superpolynomial size, for k logarithmic in the input length, while there are Las Vegas oblivious read-twice BPs of linear size for this function. This is in contrast to the situation for OBDDs, for which the respective size measures are polynomially related. <p>— Furthermore, an explicitly defined function is presented for which randomized oblivious read-k -times BPs with bounded error require exponential size, while the function as well as its complement can be represented in polynomial size by nondeterministic oblivious read-k -times BPs and deterministic oblivious read-(k+1) -times BPs, where k=o(log n) .     

Complementing two-way finite automata

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n⁸)-state 2nfa. Here we also make 2nfa’s halting. This allows the simulation of unary 2nfa’s by probabilistic Las Vegas two-way automata with O(n⁸) states.     

Improved constructions of mixed state quantum automata

Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A. Ambainis and R. Freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. There was an unpublished “folk theorem” proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable.     

Test Sets for the Universal and Existential Closure of Regular Tree Languages

Finite test sets are a useful tool for deciding the membership problem for the universal closure of a given tree language, that is, for deciding whether a term has all its ground instances in the given language. A uniform test set for the universal closure must serve the following purpose: In order to decide membership of a term, it is sufficient to check whether all its test set instances belong to the underlying language. A possible application, and our main motivation, is ground reducibility, an essential concept for many approaches to inductive reasoning. Ground reducibility modulo some rewrite system is membership in the universal closure of the set of reducible ground terms. Here, test sets always exist, and several algorithmic approaches are known. The resulting sets, however, are often unnecessarily large. In this paper we consider regular languages and linear closure operators. We prove that universal as well as existential closure, defined analogously, preserve regularity. By relating test sets to tree automata and to appropriate congruence relations, we show how to characterize, how to compute, and how to minimize ground and non-ground test sets. In particular, optimal solutions now replace previous ad hoc approximations for the ground reducibility problem.     

On the Minimization of (Complete) Ordered Binary Decision Diagrams

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions. Some applications work with a restricted variant called complete OBDDs which is strongly related to nonuniform deterministic finite automata. One of its complexity measures is the width which has been investigated in several areas in computer science like machine learning, property testing, and the design and analysis of implicit graph algorithms. For a given function the size and the width of a (complete) OBDD is very sensitive to the choice of the variable ordering but the computation of an optimal variable ordering for the OBDD size is known to be NP-hard. Since optimal variable orderings with respect to the OBDD size are not necessarily optimal for the complete model or the OBDD width and hardly anything about the relation between optimal variable orderings with respect to the size and the width is known, this relationship is investigated. Here, using a new reduction idea it is shown that the size minimization problem for complete OBDDs and the width minimization problem are NP-hard.     

A Probabilistic Model for Recovering Camera Translation

This paper describes the mathematical basis and application of a probabilistic model for recovering the direction of camera translation (heading) from optical flow. According to the theorem that heading cannot lie between two converging points in a stationary environment, one can compute the posterior probability distribution of heading across the image and choose the heading with maximum a posteriori (MAP). The model requires very simple computation, provides confidence level of the judgments, applies to both linear and curved trajectories, functions in the presence of camera rotations, and exhibited high accuracy up to 0.1°–0.2° in random dot simulations.     

Fuzzy Distance Transform: Theory, Algorithms, and Applications

This paper describes the theory and algorithms of distance transform for fuzzy subsets, called fuzzy distance transform (FDT). The notion of fuzzy distance is formulated by first defining the length of a path on a fuzzy subset and then finding the infimum of the lengths of all paths between two points. The length of a path π in a fuzzy subset of the n-dimensional continuous space ⁿ is defined as the integral of fuzzy membership values along π. Generally, there are infinitely many paths between any two points in a fuzzy subset and it is shown that the shortest one may not exist. The fuzzy distance between two points is defined as the infimum of the lengths of all paths between them. It is demonstrated that, unlike in hard convex sets, the shortest path (when it exists) between two points in a fuzzy convex subset is not necessarily a straight line segment. For any positive number θ≤1, the θ-support of a fuzzy subset is the set of all points in ⁿ with membership values greater than or equal to θ. It is shown that, for any fuzzy subset, for any nonzero θ≤1, fuzzy distance is a metric for the interior of its θ-support. It is also shown that, for any smooth fuzzy subset, fuzzy distance is a metric for the interior of its 0-support (referred to as support). FDT is defined as a process on a fuzzy subset that assigns to a point its fuzzy distance from the complement of the support. The theoretical framework of FDT in continuous space is extended to digital cubic spaces and it is shown that for any fuzzy digital object, fuzzy distance is a metric for the support of the object. A dynamic programming-based algorithm is presented for computing FDT of a fuzzy digital object. It is shown that the algorithm terminates in a finite number of steps and when it does so, it correctly computes FDT. Several potential applications of fuzzy distance transform in medical imaging are presented. Among these are the quantification of blood vessels and trabecular bone thickness in the regime of limited special resolution where these objects become fuzzy.     

Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution

We work with an extension of Resolution, called Res(2), that allows clauses with conjunctions of two literals. In this system there are rules to introduce and eliminate such conjunctions. We prove that the weak pigeonhole principle PHP^cn_n and random unsatisfiable CNF formulas require exponential-size proofs in this system. This is the strongest system beyond Resolution for which such lower bounds are known. As a consequence to the result about the weak pigeonhole principle, Res(log) is exponentially more powerful than Res(2). Also we prove that Resolution cannot polynomially simulate Res(2) and that Res(2) does not have feasible monotone interpolation solving an open problem posed by Krají ek.     

The Use of Boolean Model for Texture Analysis of Grey Images

We generalize here the use of the 1D Boolean model for the analysis of grey level textures. Each grey image is first split into eight binary images using different criteria. Each of these binary images is separately analysed with the help of the 1D Boolean model and features are extracted from it. The final grey texture recognition is performed on the basis of these features using several classification criteria. Experiments have been carried out using an image database of 30 grey level textures, all of them with 512×512 pixels in size, obtaining correct classification rates between 95% and 100%, according to the classification criterion used.     

An Algebra of Discrete Channels That Involve Combinations of Three Basic Error Types

Recently, the author introduced a nonprobabilistic mathematical model of discrete channels, the BEE channels, that involve the error-types substitution, insertion, and deletion. This paper defines an important class of BEE channels, the SID channels, which include channels that permit a bounded number of scattered errors and, possibly at the same time, a bounded burst of errors in any segment of predefined length of a message. A formal syntax is defined for generating channel expressions, and appropriate semantics is provided for interpreting a given channel expression as a communication channel (SID channel) that permits combinations of substitutions, insertions, and deletions of symbols. Our framework permits one to generalize notions such as error correction and unique decodability, and express statements of the form “The code K can correct all errors of type ξ” and “it is decidable whether the code K is uniquely decodable for the channel described by ξ”, where ξ is any SID channel expression.     

Compact Recognizers of Episode Sequences

Given two strings X=a₁…a_n and P=b₁…b_m over an alphabet Σ, the problem of testing whether P occurs as a subsequence of X is trivially solved in linear time. It is also known that a simple O(n log |Σ|) time preprocessing of X makes it easy to decide subsequently, for any P and in at most |P| log |Σ| character comparisons, whether P is a subsequence of X. These problems become more complicated if one asks instead whether P occurs as a subsequence of some substring Y of X of bounded length. This paper presents an automaton built on the textstring X and capable of identifying all distinct minimal substrings Y of X having P as a subsequence. By a substring Y being minimal with respect to P, it is meant that P is not a subsequence of any proper substring of Y. For every minimal substring Y, the automaton recognizes the occurrence of P having the lexicographically smallest sequence of symbol positions in Y. It is not difficult to realize such an automaton in time and space O(n²) for a text of n characters. One result of this paper consists of bringing those bounds down to linear or O(n log n), respectively, depending on whether the alphabet is bounded or of arbitrary size, thereby matching the corresponding complexities of automata constructions for offline exact string searching. Having built the automaton, the search for all lexicographically earliest occurrences of P in X is carried out in time O(∑_i=1^mrocc_i·i) or O(n+∑_i=1^mrocc_i·i· log n), depending on whether the alphabet is fixed or arbitrary, where rocc_i is the number of distinct minimal substrings of X having b₁…b_i as a subsequence (note that each such substring may occur many times in X but is counted only once in the bound). All log factors appearing in the above bounds can be further reduced to log log by resorting to known integer-handling data structures.