0000000000639994

AUTHOR

Dominique Perrin

showing 2 related works from this author

Recent results on syntactic groups of prefix codes

2012

International audience; We give a simplified presentation of groups in transformation monoids. We use this presentation to describe two recent results on syntactic groups of prefix codes. The first one uses Sturmian words to build finite bifix codes with a given permutation group as syntactic group. The second one describes a class of prefix codes such that all their syntactic groups are cyclic.

Prefix codeDiscrete mathematicsClass (set theory)Group (mathematics)010102 general mathematicsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)0102 computer and information sciencesPermutation group16. Peace & justice01 natural sciencesTransformation (music)Theoretical Computer SciencePrefixTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputational Theory and Mathematics[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]010201 computation theory & mathematicsDiscrete Mathematics and CombinatoricsGeometry and Topology0101 mathematicsArithmeticComputer Science::Formal Languages and Automata Theory[INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]MathematicsEuropean Journal of Combinatorics
researchProduct

A note on Sturmian words

2012

International audience; We describe an algorithm which, given a factor of a Sturmian word, computes the next factor of the same length in the lexicographic order in linear time. It is based on a combinatorial property of Sturmian words which is related with the Burrows-Wheeler transformation.

Discrete mathematicsProperty (philosophy)General Computer ScienceSettore INF/01 - Informatica010102 general mathematics[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Sturmian word0102 computer and information sciencesSturmian wordsLexicographical order01 natural sciencesTheoretical Computer ScienceCombinatoricsTransformation (function)010201 computation theory & mathematicsFactor (programming language)combinatorics0101 mathematicscomputerTime complexitycomputer.programming_languageMathematics
researchProduct