On the influence of the state encoding on OBDD-representations of finite state machines
On the Influence of the State Encoding on OBDD-Representations of Finite State Machines
Ordered binary decision diagrams are an important data structure for the representation of Boolean functions. Typically, the underlying variable ordering is used as an optimization parameter. When finite state machines are represented by OBDDs the state encoding can be used as an additional optimization parameter. In this paper, we analyze the influence of the state encoding on the OBDD-representations of counter-type finite state machines. In particular, we prove lower bounds, derive exact...
On the invertibility of finite linear transducers
Linear finite transducers underlie a series of schemes for Public Key Cryptography (PKC) proposed in the 90s of the last century. The uninspiring and arid language then used, condemned these works to oblivion. Although some of these schemes were afterwards shown to be insecure, the promise of a new system of PKC relying on different complexity assumptions is still quite exciting. The algorithms there used depend heavily on the results of invertibility of linear transducers. In this paper we introduce...
On the k-reversibility of finite automata.
On the lower bound for minimum comparison selection
On the median-of- version of Hoare’s selection algorithm
On the median-of-k version of Hoare's selection algorithm
In Hoare's (1961) original version of the algorithm the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.
On the membership problem for pseudo-varieties of commutative semigroups.
On the minimum error in addition processes of positive floating-point numbers
On the Number of Critical Free Contacts of a Convex Polygonal Object Moving in Two-Dimensional Polygonal Space.
On the number of initial segments of a finite set of sequences (finite language)
On the number of iterations required by Von Neumann addition
We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.
On the number of iterations required by Von Neumann addition
We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.
On the Number of Minimal 1-Steiner Trees.
On the Optimality of Sample-Based Estimates of the Expectation of the Empirical Minimizer***
We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the empirical minimizer in a data dependent manner. We establish three main results. First, we provide an algorithm that upper bounds the expectation of the empirical minimizer in a completely data-dependent manner. This bound is based on a structural result due to Bartlett and Mendelson, which relates...
On the orthogonalization of arbitrary Boolean formulae.
On the parallel complexity of linear groups
On the parallel complexity of the alternating hamiltonian cycle problem
On the parallel complexity of the alternating Hamiltonian cycle problem
Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...
On the parameterized complexity of approximate counting
In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class , the parameterized analogue of . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.