On separating sets of words. V. Václav Flaška, Tomáš Kepka, Juha Korteleinen (2011) Acta Universitatis Carolinae. Mathematica et Physica
On some Interconnections Between Combinatorial Optimization and Extremal Graph Theory Dragoš Cvetković, Pierre Hansen, Vera Kovačević-Vujčić (2004) The Yugoslav Journal of Operations Research
On some packing problem related to dynamic storage allocation Marek Chrobak, Maciej Ślusarek (1988) RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
On some problems related to palindrome closure Michelangelo Bucci, Aldo de Luca, Alessandro De Luca, Luca Q. Zamboni (2008) RAIRO - Theoretical Informatics and Applications In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if ϑ is an involutory antimorphism of A*, then the right and left ϑ-palindromic closures of any factor of a ϑ-standard word are also factors of some ϑ-standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting...
On some properties of doubly-periodic words Claudio Baiocchi (1997) Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni We study the functional equation: 1 A B C = C D A where A , B , C and D are words over an alphabet A . In particular we prove a «structure result» for the inner factors B , D : for suitably chosen words X , Y , Z one has: 2 B = X Y Z , D = Z Y X 2 ... On subgraphs without large components Glenn G. Chappell, John Gimbel (2017) Mathematica Bohemica We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for 2 -coloring... On substitution invariant Sturmian words: an application of Rauzy fractals Valérie Berthé, Hiromi Ei, Shunji Ito, Hui Rao (2007) RAIRO - Theoretical Informatics and Applications Sturmian words are infinite words that have exactly n+1 factors of length n for every positive integer n. A Sturmian word sα,p is also defined as a coding over a two-letter alphabet of the orbit of point ρ under the action of the irrational rotation Rα : x → x + α (mod 1). A substitution fixes a Sturmian word if and only if it is invertible. The main object of the present paper is to investigate Rauzy fractals associated with two-letter invertible substitutions. As an application, we give... On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2001) RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications We introduce the notion of a k -synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k -synchronized if its graph is represented, in base k , by a right synchronized rational relation. This is an intermediate notion between k -automatic and k -regular sequences. Indeed, we show that the class of k -automatic sequences is equal to the class of bounded k -synchronized sequences and that the class of k -synchronized sequences is strictly... On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2010) RAIRO - Theoretical Informatics and Applications We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is... On ternary square-free circular words. Shur, Arseny M. (2010) The Electronic Journal of Combinatorics [electronic only] On the approximation of min split-coloring and min cocoloring. Demange, Marc, Ekim, Tinaz, De Werra, Dominique (2006) Journal of Graph Algorithms and Applications On the binary expansion of irrational algebraic numbers Tanguy Rivoal (2009) Actes des rencontres du CIRM On the complexity of covering nodes by K node-disjoint cycles Cerdeira, J. Orestes (1988) Portugaliae mathematica On the complexity of infinite sequences. (Sur la complexité des suites infinies.) Allouche, Jean-Paul (1994) Bulletin of the Belgian Mathematical Society - Simon Stevin On the complexity of the subgraph problem Jaroslav Nešetřil, Svatopluk Poljak (1985) Commentationes Mathematicae Universitatis Carolinae On the computational complexity of centers locating in a graph Ján Plesník (1980) Aplikace matematiky It is shown that the problem of finding a minimum k -basis, the n -center problem, and the p -median problem are N P -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal m -center problem is also N P -complete. On the computational complexity of (O,P)-partition problems Jan Kratochvíl, Ingo Schiermeyer (1997) Discussiones Mathematicae Graph Theory We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P. On the conjectures of Rauzy and Shallit for infinite words Jean-Paul Allouche, Mireille Bousquet-Mélou (1995) Commentationes Mathematicae Universitatis Carolinae We show a connection between a recent conjecture of Shallit and an older conjecture of Rauzy for infinite words on a finite alphabet. More precisely we show that a Rauzy-like conjecture is equivalent to Shallit's. In passing we correct a misprint in Rauzy's conjecture. On the D0L Repetition Threshold Ilya Goldstein (2010) RAIRO - Theoretical Informatics and Applications The repetition threshold is a measure of the extent to which there need to be consecutive (partial) repetitions of finite words within infinite words over alphabets of various sizes. Dejean's Conjecture, which has been recently proven, provides this threshold for all alphabet sizes. Motivated by a question of Krieger, we deal here with the analogous threshold when the infinite word is restricted to be a D0L word. Our main result is that, asymptotically, this threshold does not exceed the unrestricted... On the decidability of semigroup freeness∗ Julien Cassaigne, Francois Nicolas (2012) RAIRO - Theoretical Informatics and Applications This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids.... Currently displaying 541 – 560 of 893 Previous Page 28 Next
On subgraphs without large components Glenn G. Chappell, John Gimbel (2017) Mathematica Bohemica We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for 2 -coloring...
On substitution invariant Sturmian words: an application of Rauzy fractals Valérie Berthé, Hiromi Ei, Shunji Ito, Hui Rao (2007) RAIRO - Theoretical Informatics and Applications Sturmian words are infinite words that have exactly n+1 factors of length n for every positive integer n. A Sturmian word sα,p is also defined as a coding over a two-letter alphabet of the orbit of point ρ under the action of the irrational rotation Rα : x → x + α (mod 1). A substitution fixes a Sturmian word if and only if it is invertible. The main object of the present paper is to investigate Rauzy fractals associated with two-letter invertible substitutions. As an application, we give...
On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2001) RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications We introduce the notion of a k -synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k -synchronized if its graph is represented, in base k , by a right synchronized rational relation. This is an intermediate notion between k -automatic and k -regular sequences. Indeed, we show that the class of k -automatic sequences is equal to the class of bounded k -synchronized sequences and that the class of k -synchronized sequences is strictly...
On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2010) RAIRO - Theoretical Informatics and Applications We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is...
On ternary square-free circular words. Shur, Arseny M. (2010) The Electronic Journal of Combinatorics [electronic only]
On the approximation of min split-coloring and min cocoloring. Demange, Marc, Ekim, Tinaz, De Werra, Dominique (2006) Journal of Graph Algorithms and Applications
On the binary expansion of irrational algebraic numbers Tanguy Rivoal (2009) Actes des rencontres du CIRM
On the complexity of covering nodes by K node-disjoint cycles Cerdeira, J. Orestes (1988) Portugaliae mathematica
On the complexity of infinite sequences. (Sur la complexité des suites infinies.) Allouche, Jean-Paul (1994) Bulletin of the Belgian Mathematical Society - Simon Stevin
On the complexity of the subgraph problem Jaroslav Nešetřil, Svatopluk Poljak (1985) Commentationes Mathematicae Universitatis Carolinae
On the computational complexity of centers locating in a graph Ján Plesník (1980) Aplikace matematiky It is shown that the problem of finding a minimum k -basis, the n -center problem, and the p -median problem are N P -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal m -center problem is also N P -complete.
On the computational complexity of (O,P)-partition problems Jan Kratochvíl, Ingo Schiermeyer (1997) Discussiones Mathematicae Graph Theory We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.
On the conjectures of Rauzy and Shallit for infinite words Jean-Paul Allouche, Mireille Bousquet-Mélou (1995) Commentationes Mathematicae Universitatis Carolinae We show a connection between a recent conjecture of Shallit and an older conjecture of Rauzy for infinite words on a finite alphabet. More precisely we show that a Rauzy-like conjecture is equivalent to Shallit's. In passing we correct a misprint in Rauzy's conjecture.
On the D0L Repetition Threshold Ilya Goldstein (2010) RAIRO - Theoretical Informatics and Applications The repetition threshold is a measure of the extent to which there need to be consecutive (partial) repetitions of finite words within infinite words over alphabets of various sizes. Dejean's Conjecture, which has been recently proven, provides this threshold for all alphabet sizes. Motivated by a question of Krieger, we deal here with the analogous threshold when the infinite word is restricted to be a D0L word. Our main result is that, asymptotically, this threshold does not exceed the unrestricted...
On the decidability of semigroup freeness∗ Julien Cassaigne, Francois Nicolas (2012) RAIRO - Theoretical Informatics and Applications This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....