Search results for "F.4.3"
showing 7 items of 7 documents
Topological Logics with Connectedness over Euclidean Spaces
2013
We consider the quantifier-free languages, Bc and Bc °, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of R n ( n ≥ 2) and, additionally, over the regular closed semilinear sets of R n . The resulting logics are examples of formalisms that have recently been proposed in the Artificial Intelligence literature under the rubric Qualitative Spatial Reasoning. We prove that the satisfiability problem for Bc is undecidable over the regular closed semilinear sets in all dimensions greater than 1,…
Splicing Systems from Past to Future: Old and New Challenges
2014
A splicing system is a formal model of a recombinant behaviour of sets of double stranded DNA molecules when acted on by restriction enzymes and ligase. In this survey we will concentrate on a specific behaviour of a type of splicing systems, introduced by P\u{a}un and subsequently developed by many researchers in both linear and circular case of splicing definition. In particular, we will present recent results on this topic and how they stimulate new challenging investigations.
Abelian Repetitions in Sturmian Words
2012
We investigate abelian repetitions in Sturmian words. We exploit a bijection between factors of Sturmian words and subintervals of the unitary segment that allows us to study the periods of abelian repetitions by using classical results of elementary Number Theory. We prove that in any Sturmian word the superior limit of the ratio between the maximal exponent of an abelian repetition of period $m$ and $m$ is a number $\geq\sqrt{5}$, and the equality holds for the Fibonacci infinite word. We further prove that the longest prefix of the Fibonacci infinite word that is an abelian repetition of period $F_j$, $j>1$, has length $F_j(F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j(F_{j+1}+F_{j-1}…
Enumeration and Structure of Trapezoidal Words
2013
Trapezoidal words are words having at most $n+1$ distinct factors of length $n$ for every $n\ge 0$. They therefore encompass finite Sturmian words. We give combinatorial characterizations of trapezoidal words and exhibit a formula for their enumeration. We then separate trapezoidal words into two disjoint classes: open and closed. A trapezoidal word is closed if it has a factor that occurs only as a prefix and as a suffix; otherwise it is open. We investigate open and closed trapezoidal words, in relation with their special factors. We prove that Sturmian palindromes are closed trapezoidal words and that a closed trapezoidal word is a Sturmian palindrome if and only if its longest repeated …
A Classification of Trapezoidal Words
2011
Trapezoidal words are finite words having at most n+1 distinct factors of length n, for every n>=0. They encompass finite Sturmian words. We distinguish trapezoidal words into two disjoint subsets: open and closed trapezoidal words. A trapezoidal word is closed if its longest repeated prefix has exactly two occurrences in the word, the second one being a suffix of the word. Otherwise it is open. We show that open trapezoidal words are all primitive and that closed trapezoidal words are all Sturmian. We then show that trapezoidal palindromes are closed (and therefore Sturmian). This allows us to characterize the special factors of Sturmian palindromes. We end with several open problems.
Languages associated with saturated formations of groups
2013
International audience; In a previous paper, the authors have shown that Eilenberg's variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower.; Dans un article précédent, les auteurs avaient montré comment étendre le théorème des variétés d'Eilenberg à des structures plus g…
Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited
2014
International audience; We present an extension of Eilenberg's variety theorem, a well-known result connecting algebra to formal languages. We prove that there is a bijective correspondence between formations of finite monoids and certain classes of languages, the formations of languages. Our result permits to treat classes of finite monoids which are not necessarily closed under taking submonoids, contrary to the original theory. We also prove a similar result for ordered monoids.; Nous présentons une extension du théorème des variétés d'Eilenberg, un résultat célèbre reliant l'algèbre à la théorie des langages formels. Nous montrons qu'il existe une correspondance bijective entre les form…