International Journal of Foundations of Computer Science

Many nondeterminism measures for finite automata have been studied in the literature. The tree width of an NFA (nondeterministic finite automaton) counts the number of leaves of computation trees as a function of input length. The trace of an NFA is defined in terms of the largest product of the degrees of nondeterministic choices in computations on inputs of given length. Branching is the corresponding best case measure based on the product of nondeterministic choices in the computation that minimizes this value. We establish upper and lower bounds for the trace of an NFA in terms of its tree width. We give a tight bound for the size blow-up of determinizing an NFA with finite trace. Also we show that the trace of any NFA either is bounded by a constant or grows exponentially.

Low-dimensional Tori are regularly used as interconnection networks in distributed-memory parallel computers. This paper investigates the fault-Hamiltonicity of two-dimensional Tori. A sufficient condition is derived for the graph Row-Torus(m, 2n + 1) with two faulty edges to have a Hamiltonian cycle, where m ≥ 3 and n ≥ 1. By applying the fault-Hamiltonicity of Row-Torus to a two-dimensional torus, we show that Torus(m, n), m, n ≥ 5, with at most four faulty edges is Hamiltonian if the following two conditions are satisfied: (1) the degree of every vertex is at least two, and (2) there do not exist a pair of nonadjacent vertices in a 4-cycle whose degrees are both two after faulty edges are removed.

We continue our research on minimization problems and related problems for automata w.r.t. to different error profiles, now considering nondeterministic finite automata (NFAs) as inputs. Here the error profiles are almost-equivalence and E-equivalence. We show that the minimization problems and their underlying equivalence problems become PSPACE-complete in most cases. The obtained results nicely fit to the known ones on ordinary NFA minimization, and show a significant difference to the previously obtained results on deterministic finite state machines.

Some mathematical aspects of reaction systems introduced by Ehrenfeucht and Rozenberg are considered. Ehrenfeucht et al. have previously obtained a complete classification of functions specified by minimal reaction systems in terms of certain closure properties of the specified functions. In this work, a refined proof of this classification with slight extension is obtained. Furthemore, the recently introduced notion of reaction system rank is studied for functions belonging to this class, as well as for focus functions, the latter which play a significant role in the proof of the classification theorem.

Let us color the vertices of the grid ℤ^d or the infinite regular tree 𝕋_d, using a finite number of colors, with the constraint that some predefined pairs of colors are not allowed for adjacent vertices. The set of admissible colorings is called a nearest-neighbor subshift of finite type (SFT). We study “uniform” probability measures on SFT, with the motivation of having an insight into “typical” admissible configurations. We recall the known results on uniform measures on SFT on grids and we complete the picture by presenting some contributions to the description of uniform measures on SFT on 𝕋_d. Then we focus on the problem of uniform random sampling of configurations of SFT. We propose a first method based on probabilistic cellular automata, which is valid under some restrictive conditions. Then we concentrate on the case of SFT on ℤ for which we propose several alternative sampling methods.

We give faster methods to compute discrete convolutions. We assume that all the inputs are packed, that is, strings are packed into words such that each word is packed with $\begin{array}{l}\alpha =\lfloor \omega /{\log }_2\left|\Sigma \right|\rfloor \\ \end{array}$ characters, where w is the length of a machine word and ∑ is the alphabet. The output of our methods is also packed, that is, each word of the output contains more than one element of the result. The approach is based on the word-level parallelism and the FFT. Given two strings with m and n ( n ≥ m ) characters that are packed into $\lceil m/\alpha \rceil$ and $\lceil n/\alpha \rceil$ words respectively, the convolution of them can be computed in $O\left(\frac{nu}{w}\log \frac{mu}{w}\right)$ time, where $u=\left(\lceil {\log }_{\left|\Sigma \right|}m\rceil +2\right){\log }_2\left|\Sigma \right|$ by the FFT. Experiments show that our method is three times faster than the convolution using the standard trick.

We consider the problem of pattern matching with wildcards on packed strings. It finds all the occurrences of a pattern in a text, both of which may contain wildcards. By the convolution of packed strings, we present algorithms that are faster than the previous $O(n\log m)$-time algorithm, where m is the length of the pattern and n the length of the text. The algorithm runs in $O\left(\frac{nu}{w}\log \frac{mu}{w}+\frac{n\log \left|\Sigma \right|}{w}{\log }^{1+o(1)}\log \left|\Sigma \right|+\frac{m\log \left|\Sigma \right|}{w}\log \frac{w}{\log \left|\Sigma \right|}+occ\right)$ time, where occ is the number of occurrences of the pattern in the input. Experiments show that the method is faster than the bit-parallel wildcard matching algorithm for long patterns.