Search

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [ABSTRACT FROM AUTHOR]

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n3), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n2log n log|Σ|) and O(|Σ|n2log2 n log log n), with Σ denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences. The present paper describes an off-line algorithm for binary strings that takes O(n2) time. The algorithm does not need to resort to the FFT and yet its performance is optimal for finite Σ. [ABSTRACT FROM AUTHOR]

Analysis of infinitary safety properties with automated compositional reasoning through learning is discussed in the paper. We consider the class of intuitionistically closed regular languages and show that it forms a Heyting algebra and is finitely approximatable. Subsequently, compositional proof rules can be verified automatically and learning algorithms for finitary regular languages suffice. We also establish an axiom to deduce circular compositional proof rules for the infinitary languages. [ABSTRACT FROM AUTHOR]

In this paper, we present efficient geometric algorithms for the discrete constrained 1-D K-means clustering problem and extend our solutions to the continuous version of the problem. One key clustering constraint we consider is that the maximum difference in each cluster cannot be larger than a given threshold. These constrained 1-D K-means clustering problems appear in various applications, especially in intensity-modulated radiation therapy (IMRT). Our algorithms improve the efficiency and accuracy of the heuristic approaches used in clinical IMRT treatment planning. [ABSTRACT FROM AUTHOR]

Approximate pattern matching has a wide range of applications and, depending on the type of approximation, there exist numerous algorithms for solving it. In this article we focus on texts which originate from OCRed documents, whose errors quite often have a particular form and are far from being random errors. We introduce a new variant of the edit distance metric, where apart from the traditional edit operations, two new operations are supported. The combination operation allows two or more symbols from a string x to be interpreted as a single symbol and then "matched" (or aligned) against a single symbol of a second string y. Its dual is the operation of a split, where a single symbol from x is broken down into a sequence of two or more other symbols, that can then be matched against an equal number of symbols from y. Our algorithm requires O(L) time for preprocessing, and O(mnk) time for computing the edit distance, where L is the total length of all the valid combinations/splits, m and n are the lengths of the two strings under comparison and k is an upper bound on the number of valid splits for any single symbol. The expected running time is O(mn). [ABSTRACT FROM AUTHOR]

Two formal languages are f-equivalent if their symmetric difference L1 Δ L2 is a finite set — that is, if they differ on only finitely many words. The study of f-equivalent languages, and particularly the DFAs that accept them, was recently introduced [3]. First, we restate the fundamental results in this new area of research. Second, we introduce our main result, which is a faster algorithm for the natural minimization problem: given a starting DFA D, find the smallest (by number of states) DFA D′ such that L(D) and L(D′) are f-equivalent. Finally, we suggest a technique that combines this hyper-minimization with the well-studied notion of a deterministic finite cover automaton [2, 4, 5], or DFCA, thereby extending the applicability of DFCAs from finite to infinite regular languages. [ABSTRACT FROM AUTHOR]

We show that parametric context-sensitive L-systems with affine geometry interpretation provide a succinct description of some of the most fundamental algorithms of geometric modeling of curves. Examples include the Lane-Riesenfeld algorithm for generating B-splines, the de Casteljau algorithm for generating Bézier curves, and their extensions to rational curves. Our results generalize the previously reported geometric-modeling applications of L-systems, which were limited to subdivision curves. [ABSTRACT FROM AUTHOR]

Minimal deterministic finite automata (DFAs) can be reduced further at the expense of a finite number of errors. Recently, such minimization algorithms have been improved to run in time O(n log n), where n is the number of states of the input DFA, by [GAWRYCHOWSKI and JEŻ: Hyper-minimisation made efficient. Proc. MFCS, LNCS 5734, 2009] and [HOLZER and MALETTI: An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010]. Both algorithms return a DFA that is as small as possible, while only committing a finite number of errors. These algorithms are further improved to return a DFA that commits the least number of errors at the expense of an increased (quadratic) run-time. This solves an open problem of [BADR, GEFFERT, and SHIPMAN: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl. 43, 2009]. In addition, an experimental study on random automata is performed and the effects of the existing algorithms and the new algorithm are reported. [ABSTRACT FROM AUTHOR]

We consider properties of the solution set of a word equation with one unknown. We prove that the solution set of a word equation possessing infinite number of solutions is of the form (pq)*p where pq is primitive. Next, we prove that a word equation with at most four occurrences of the unknown possesses either infinitely many solutions or at most two solutions. We show that there are equations with at most four occurrences of the unknown possessing exactly two solutions. Finally, we prove that a word equation with at most 2k occurrences of the unknown possesses either infinitely many solutions or at most 8 log k + O(1) solutions. Hence, if we consider a class εk of equations with at most 2k occurrences of the unknown, then each equation in this class possesses either infinitely many solutions or O(log k) number of solutions. Our considerations allow to construct the first alphabet independent linear time algorithm for computing the solution set of an equation in a nontrivial class of equations. [ABSTRACT FROM AUTHOR]

A weighted finite-state machine with n tapes describes a rational relation on n strings. We recall some basic operations on n-ary rational relations, recast the important join operation in terms of "auto-intersection", and propose restricted algorithms for both operations. If two rational relations are joined on more than one tape, it can unfortunately lead to non-rational relations with undecidable properties. As a consequence, there cannot be a fully general algorithm, able to compile any rational join or auto-intersection. We define a class of triples 〈A,i,j〉 for which we are able to compile the auto-intersection of the machine A w.r.t. tapes i and j. We hope that this class is sufficient for many practical applications. [ABSTRACT FROM AUTHOR]