Algorithms for Approximate K-Covering of Strings |
2005 |
2469 |
Computing approximate patterns in strings or sequences has important applications in DNA sequence analysis, data compression, musical text analysis, and so on. In this paper, we introduce approximate k-covers and study them under various commonly use... |
Border Correlations of Partial Words |
2010 |
2029 |
Partial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ◊’s. Setting = A◊ → {◊}, denotes the set of all partial words over A. In... |
Codes, orderings, and partial words |
2004 |
2145 |
Codes play an important role in the study of the combinatorics of words. In this paper, we introduce pcodes that play a role in the study of combinatorics ofpartial words. Partial words are strings over a finite alphabet that may contain a number of ... |
Computing the Partial Word Avoidability Indices of Binary Patterns |
2013 |
1438 |
We complete the classification of binary patterns in partial words that was started in earlier publications by proving that the partial word avoidability index of the binary pattern ABABA is two and the one of the binary pattern ABBA is three. |
Computing the Partial Word Avoidability Indices of Ternary Patterns |
2013 |
2240 |
We study pattern avoidance in the context of partial words. The problem of classifying the avoidable binary patterns has been solved, so we move on to ternary and more general patterns. Our results, which are based on morphisms (iterated or not), det... |
Conjugacy on partial words |
2002 |
1500 |
The study of the combinatorial properties of strings of symbols from a finite alphabet (also referred to as words) is profoundly connected to numerous fields such as biology, computer science, mathematics, and physics. In this paper, we examine to wh... |
Counting Minimal Semi-Sturmian Words |
2013 |
2110 |
A finite Sturmian word w is a balanced word over the binary alphabet {a,b}, that is, for all subwords u andv of w of equal length, ||u|a-|v|a|=1, where |u|a and |v|a denote the number of occurrences of the lettera in u and v, respectively. There are ... |
Equations and Dot-Depth One |
1993 |
1741 |
This paper studies the fine structure of the Straubing hierarchy of star-free languages. Sequences of equations are defined and are shown to be sufficiently strong to characterize completely the monoid varieties of a natural subhierarchy of level one... |
EQUATIONS ON PARTIAL WORDS |
2009 |
999 |
It is well-known that some of the most basic properties of words, like the commutativity (xy = yx) and the conjugacy (xz = zy), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on word... |
Equations on the semidirect product of a finite semilattice by a finite commutative monoid |
1994 |
3190 |
Let Comt,q denote the variety of finite monoids that satisfy the equations xy = yx and xt = xt+q . The variety Com1,1 is the variety of finite semilattices also den... |
Equations on Semidirect Products of Commutative Semigroups |
1997 |
2058 |
In this paper; we study equations on semidirect products of commutative semigroups. Let Comq,r denote the pseudovariety of all finite semigroups that satisfy the equations xy = yx and xr + q = xr. The pseudovari... |
Games, equations and dot-depth two monoids |
1992 |
2178 |
Given any finite alphabet A and positive integers m1, …, mk, congruences on A*, denoted by ~(m1, …, mk) and related to a version of the Ehrenfeucht-Fraisse game, are defined. Level k of the Straubing hierarchy of aperiodic monoids can be characterize... |
A generalization of Thue freeness for partial words |
2009 |
2354 |
This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of ?holes?. First, we give an infinite word over a three-letter alphabet which avoids squ... |
Multiset and Set Decipherable Codes |
2001 |
2517 |
We extend some results of Lempel and Restivo on multiset decipherable codes to set decipherable codes. |
Note on Decipherability of Three-Word Codes |
2002 |
1938 |
The theory of uniquely decipherable (UD) codes has been widely developed in connection
with automata theory, combinatorics on words, formal languages, and monoid theory.
Recently, the concepts of multiset decipherable (MSD) and set decipherable (SD... |
A NOTE ON THE NUMBER OF SQUARES IN A PARTIAL WORD WITH ONE HOLE |
2009 |
2150 |
A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate sq... |
Number of Holes in Unavoidable Sets of Partial Words I |
2014 |
1610 |
Partial words are sequences over a finite alphabet that may contain some undefined positions called holes. We consider unavoidable sets of partial words of equal length. We compute the minimum number of holes in sets of size three over a binary alpha... |
Number of Holes in Unavoidable Sets of Partial Words II |
2012 |
1671 |
We are concerned with the complexity of deciding the avoidability of sets of partial words over an arbitrary alphabet. Towards this, we investigate the minimum size of unavoidable sets of partial words with a fixed number of holes. Additionally, we a... |
On dot-depth two |
1990 |
783 |
Etant donnés des entiers positifs m1, …, mk, on définit des congruences ~(m1, …, mk) en relation avec une version du jeu de Ehrenfeucht-Fraissé, et qui correspondent au niveau k de la hiérarchie de concaténation de Straubing. Etant donné un alphabet ... |
On a Product of Finite Monoids |
1998 |
1335 |
In this paper, for each positive integer m, we associate with a finite monoid S0 and m finite commutative monoids S1,…, Sm, a product ◊m(Sm,…, S1, S0). We give a representation o... |
Partial words and the critical factorization theorem revisited |
2007 |
2325 |
In this paper, we consider one of the most fundamental results on the periodicity of words, namely the critical factorization theorem. Given a word w and nonempty words u, v satisfying w = uv, the minimal local period associated with the factorizatio... |
Periodicity on Partial Words |
2004 |
2058 |
A partial word of length n over a finite alphabet A is a partial map from {0, … , n - 1} into A. Elements of {0, … , n-1} without image are called holes (a word is just a partial word without holes). A fundamental periodicity result on words due to F... |
Periodicity properties on partial words |
2008 |
2276 |
The concept of periodicity has played over the years a centra1 role in the development of combinatorics on words and has been a highly valuable too1 for the design and analysis of algorithms. Fine and Wilf’s famous periodicity result, which is one of... |
Periods in Partial Words: An Algorithm |
2012 |
2052 |
Partial words are finite sequences over a finite alphabet that may contain some holes. A variant of the celebrated Fine–Wilf theorem shows the existence of a bound L=L(h,p,q) such that if a partial word of length at least L with h holes has per... |
Recurrent Partial Words |
2011 |
928 |
Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match or are compatible with all letters; partial words without holes are said to be full words (or simply words). Given an infinite partial wor... |
Remarks on Two Nonstandard Versions of Periodicity in Words |
2008 |
1730 |
In this paper, we study some periodicity concepts on words. First, we extend the notion of full tilings which was recently introduced by Karhumäki, Lifshits, and Rytter to partial tilings. Second, we investigate the notion of quasiperiods and show in... |
Some Logical Characterizations of the Dot-Depth Hierarchy and Applications |
1995 |
1986 |
A logical characterization of natural subhierarchies of the dot-depth hierarchy refining a theorem of Thomas and a congruence characterization related to a version of the Ehrenfeucht—Fraïssé game generalizing a theorem of Simon are given. For a seque... |
Strict Bounds for Pattern Avoidance |
2013 |
2597 |
Cassaigne conjectured in 1994 that any pattern with m distinct variables of length at least 3(2m-1) is avoidable over a binary alphabet, and any pattern with m distinct variables of length at least 2m is avoidable over a ternary alphabet. Building ... |
Testing avoidability on sets of partial words is hard |
2009 |
2139 |
We prove that the problem of deciding whether a finite set of partial words is unavoidable is NP-hard for any alphabet of size larger than or equal to two, which is in contrast with the well-known feasability results for unavoidability of a set of fu... |
Testing primitivity on partial words |
2007 |
2143 |
Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or ... |
Trees, Congruences and Varieties of Finite Semigroups |
1998 |
1778 |
A classification scheme for regular languages or finite semigroups was proposed by Pin through tree hierarchies, a scheme related to the concatenation product, an operation on languages, and to the Schützenberger product, an operation on semigroups. ... |
Unavoidable Sets of Partial Words |
2009 |
2247 |
The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer science, in particular with its connection to the study of combinatorics on words. The theory of unavoidable sets has seen extensive st... |
Unbordered partial words |
2009 |
3115 |
An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number... |