The Experts below are selected from a list of 103605 Experts worldwide ranked by ideXlab platform
Daniel Reidenbach - One of the best experts on this subject based on the ideXlab platform.
-
WORDS - Ambiguity of Morphisms in a Free Group
Lecture Notes in Computer Science, 2015Co-Authors: Joel D. Day, Daniel ReidenbachAbstract:A Morphism g is ambiguous with respect to a word u if there exists a Morphism \(h \not = g\) such that \(g(u) = h(u)\). The ambiguity of Morphisms has so far been studied in a free monoid. In the present paper, we consider the ambiguity of Morphisms of the free group. Firstly, we note that a direct generalisation results in a trivial problem. We provide a natural reformulation of the problem along with a characterisation of elements of the free group which have an associated unambiguous injective Morphism. This characterisation matches an existing result known for the free monoid. Secondly, we note a second formulation of the problem which leads to a non-trivial situation: when terminal symbols are permitted. In this context, we investigate the ambiguity of the Morphism erasing all non-terminal symbols. We provide, for any alphabet, a pattern which can only be mapped to the empty word exactly by this Morphism. We then generalize this construction to give, for any Morphism g, a pattern \(\alpha \) such that \(h(\alpha )\) is the empty word if and only if \(h = g\).
-
Weakly unambiguous Morphisms
Theoretical Computer Science, 2012Co-Authors: Dominik D. Freydenberger, Hossein Nevisi, Daniel ReidenbachAbstract:A nonerasing Morphism @s is said to be weakly unambiguous with respect to a word s if @s is the only nonerasing Morphism that can map s to @s(s), i.e., there does not exist any other nonerasing Morphism @t satisfying @t(s)=@s(s). In the present paper, we wish to characterise those words with respect to which there exists such a Morphism. This question is nontrivial if we consider so-called length-increasing Morphisms, which map a word to an image that is strictly longer than the word. Our main result is a compact characterisation that holds for all Morphisms with ternary or larger target alphabets. We also comprehensively describe those words that have a weakly unambiguous length-increasing Morphism with a unary target alphabet, but we have to leave the problem open for binary alphabets, where we can merely give some non-characteristic conditions.
-
Restricted ambiguity of erasing Morphisms
Theoretical Computer Science, 2011Co-Authors: Daniel Reidenbach, Johannes C. SchneiderAbstract:A Morphism h is called ambiguous for a string s if there is another Morphism that maps s to the same image as h; otherwise, it is called unambiguous. In this paper, we examine some fundamental problems on the ambiguity of erasing Morphisms. We provide a detailed analysis of so-called ambiguity partitions, and our main result uses this concept to characterise those strings that have a Morphism of strongly restricted ambiguity. Furthermore, we demonstrate that there are strings for which the set of unambiguous Morphisms, depending on the size of the target alphabet of these Morphisms, is empty, finite or infinite. Finally, we show that the problem of the existence of unambiguous erasing Morphisms is equivalent to some basic decision problems for nonerasing multi-pattern languages.
-
STACS - Weakly Unambiguous Morphisms
2011Co-Authors: Dominik D. Freydenberger, Hossein Nevisi, Daniel ReidenbachAbstract:A nonerasing Morphism sigma is said to be weakly unambiguous with respect to a word w if sigma is the only nonerasing Morphism that can map w to sigma(w), i.e., there does not exist any other nonerasing Morphism tau satisfying tau(w) = sigma(w). In the present paper, we wish to characterise those words with respect to which there exists such a Morphism. This question is nontrivial if we consider so-called length-increasing Morphisms, which map a word to an image that is strictly longer than the word. Our main result is a compact characterisation that holds for all Morphisms with ternary or larger target alphabets. We also comprehensively describe those words that have a weakly unambiguous length-increasing Morphism with a unary target alphabet, but we have to leave the problem open for binary alphabets, where we can merely give some non-characteristic conditions.
-
The unambiguity of segmented Morphisms
Discrete Applied Mathematics, 2009Co-Authors: Dominik D. Freydenberger, Daniel ReidenbachAbstract:AbstractThis paper studies the ambiguity of Morphisms in free monoids. A Morphism σ is said to be ambiguous with respect to a string α if there exists a Morphism τ which differs from σ for a symbol occurring in α, but nevertheless satisfies τ(α)=σ(α); if there is no such τ then σ is called unambiguous. Motivated by the recent initial paper on the ambiguity of Morphisms, we introduce the definition of a so-called segmented Morphism σn, which, for any n∈N, maps every symbol in an infinite alphabet onto a word that consists of n distinct factors in ab+a, where a and b are different letters. For every n, we consider the set U(σn) of those finite strings over an infinite alphabet with respect to which σn is unambiguous, and we comprehensively describe its relation to any U(σm), m≠n.Thus, our work features the first approach to a characterisation of sets of strings with respect to which certain fixed Morphisms are unambiguous, and it leads to fairly counter-intuitive insights into the relations between such sets. Furthermore, it shows that, among the widely used homogeneous Morphisms, most segmented Morphisms are optimal in terms of being unambiguous for a preferably large set of strings. Finally, our paper yields several major improvements of crucial techniques previously used for research on the ambiguity of Morphisms
Thomas Noll - One of the best experts on this subject based on the ideXlab platform.
-
matching lexicographic and conjugation orders on the conjugation class of a special sturmian Morphism
International Conference on Combinatorics on Words, 2017Co-Authors: David Clampitt, Thomas NollAbstract:The conjugation class of a special Sturmian Morphism carries a natural linear order by virtue of the two elementary conjugations \(conj_a\) and \(conj_b\) with the single letters a and b, with the standard Morphism of the class as the smallest element in this order. We show that a lexicographic order on the Morphisms of the given conjugation class can be defined that matches the conjugation order.
-
WORDS - Matching Lexicographic and Conjugation Orders on the Conjugation Class of a Special Sturmian Morphism
Lecture Notes in Computer Science, 2017Co-Authors: David Clampitt, Thomas NollAbstract:The conjugation class of a special Sturmian Morphism carries a natural linear order by virtue of the two elementary conjugations \(conj_a\) and \(conj_b\) with the single letters a and b, with the standard Morphism of the class as the smallest element in this order. We show that a lexicographic order on the Morphisms of the given conjugation class can be defined that matches the conjugation order.
Gwenaël Richomme - One of the best experts on this subject based on the ideXlab platform.
-
On Quasiperiodic Morphisms
2013Co-Authors: Florence Levé, Gwenaël RichommeAbstract:Weakly and strongly quasiperiodic Morphisms are tools introduced to study quasiperiodic words. Formally they map respectively at least one or any non-quasiperiodic word to a quasiperiodic word. Considering them both on finite and infinite words, we get four families of Morphisms between which we study relations. We provide algorithms to decide whether a Morphism is strongly quasiperiodic on finite words or on infinite words.
-
On Morphisms preserving infinite Lyndon words
Discrete Mathematics and Theoretical Computer Science, 2007Co-Authors: Gwenaël RichommeAbstract:In a previous paper, we characterized free monoid Morphisms preserving finite Lyndon words. In particular, we proved that such a Morphism preserves the order on finite words. Here we study Morphisms preserving infinite Lyndon words and Morphisms preserving the order on infinite words. We characterize them and show relations with Morphisms preserving Lyndon words or the order on finite words. We also briefly study Morphisms preserving border-free words and those preserving the radix order.
-
Existence of finite test-sets for k-power-freeness of uniform Morphisms
Discrete Applied Mathematics, 2007Co-Authors: Gwenaël Richomme, Francis WlazinskiAbstract:A challenging problem is to find an algorithm to decide whether a Morphism is k-power-free. We provide such an algorithm when k >= 3 for uniform Morphisms showing that in such a case, contrarily to the general case, there exist finite test-sets for k-power-freeness.
-
Some algorithms to compute the conjugates of episturmian Morphisms
RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), 2003Co-Authors: Gwenaël RichommeAbstract:Episturmian Morphisms generalize Sturmian Morphisms. They are defined as compositions of exchange Morphisms and two particular Morphisms G, and D. Epistandard Morphisms are the Morphisms obtained without considering D. In a previous paper, a general study of these morphims and of conjugacy of Morphisms is given. Here, given a decomposition of an episturmian Morphism f over exchange Morphisms and {G, D}, we consider two problems: how to compute a decomposition of one conjugate of f; how to compute a list of decompositions of all the conjugates of f when f is epistandard. For each problem, we give several algorithms. Although the proposed methods are fundamently different, we show that some of these lead to the same result. We also give other algorithms, using the same input, to compute for instance the length of the Morphism, or its number of conjugates.
-
Some results on k-power-free Morphisms
Theoretical Computer Science, 2002Co-Authors: Gwenaël Richomme, Francis WlazinskiAbstract:One way to generate infinite k-power-free words is to iterate a k-power-free Morphism, that is a Morphism that preserves finite k-power-free words. We first prove that the monoid of k-power-free endoMorphisms on an alphabet containing at least three letters is not finitely generated. Test-sets for k-power-free Morphisms (that is, the sets T such that a Morphism f is k-power-free if and only if f(T) is k-power-free) give characterizations of these Morphisms. In the case of binary Morphisms and k = 3, we prove that a set T of cube-free words is a test-set for cube-freeness if and only if it contains twelve particular factors. Consequently, a Morphism f on {a, b} is cube-free if and only if f(aabbababbabbaabaababaabb) is cube-free (length 24 is optimal). Another consequence is an unpublished result of Leconte: A binary Morphism is cube-free if and only if the images of all cube-free words of length 7 are cube-free. When k ≥ 3, we show that no finite test-set exists for Morphisms defined on an alphabet containing at least three letters. In the last part, we show that to generate an infinite cube-free word by iterating a Morphism, we do not necessarily need a cube-free Morphism. We give a new characterization of some Morphisms that generate infinite cube-free words.
David Clampitt - One of the best experts on this subject based on the ideXlab platform.
-
matching lexicographic and conjugation orders on the conjugation class of a special sturmian Morphism
International Conference on Combinatorics on Words, 2017Co-Authors: David Clampitt, Thomas NollAbstract:The conjugation class of a special Sturmian Morphism carries a natural linear order by virtue of the two elementary conjugations \(conj_a\) and \(conj_b\) with the single letters a and b, with the standard Morphism of the class as the smallest element in this order. We show that a lexicographic order on the Morphisms of the given conjugation class can be defined that matches the conjugation order.
-
WORDS - Matching Lexicographic and Conjugation Orders on the Conjugation Class of a Special Sturmian Morphism
Lecture Notes in Computer Science, 2017Co-Authors: David Clampitt, Thomas NollAbstract:The conjugation class of a special Sturmian Morphism carries a natural linear order by virtue of the two elementary conjugations \(conj_a\) and \(conj_b\) with the single letters a and b, with the standard Morphism of the class as the smallest element in this order. We show that a lexicographic order on the Morphisms of the given conjugation class can be defined that matches the conjugation order.
Manfred Kufleitner - One of the best experts on this subject based on the ideXlab platform.
-
The complexity of weakly recognizing Morphisms
Theoretical Informatics and Applications, 2018Co-Authors: Lukas Fleischer, Manfred KufleitnerAbstract:Weakly recognizing Morphisms from free semigroups onto finite semigroups are a classical way for defining the class of ω -regular languages, i.e. , a set of infinite words is weakly recognizable by such a Morphism if and only if it is accepted by some Buchi automaton. We study the descriptional complexity of various constructions and the computational complexity of various decision problems for weakly recognizing Morphisms. The constructions we consider are the conversion from and to Buchi automata, the conversion into strongly recognizing Morphisms, as well as complementation. We also show that the fixed membership problem is NC 1 -complete, the general membership problem is in L and that the inclusion, equivalence and universality problems are NL-complete. The emptiness problem is shown to be NL-complete if the input is given as a non-surjective Morphism.
-
Operations on Weakly Recognizing Morphisms
arXiv: Formal Languages and Automata Theory, 2016Co-Authors: Lukas Fleischer, Manfred KufleitnerAbstract:Weakly recognizing Morphisms from free semigroups onto finite semigroups are a classical way for defining the class of omega-regular languages, i.e., a set of infinite words is weakly recognizable by such a Morphism if and only if it is accepted by some B\"uchi automaton. We consider the descriptional complexity of various constructions for weakly recognizing Morphisms. This includes the conversion from and to B\"uchi automata, the conversion into strongly recognizing Morphisms, and complementation. For some problems, we are able to give more precise bounds in the case of binary alphabets or simple semigroups.
