scientific article

Dominique Perrin, Jean Berstel, Christophe Reutenauer

Publication date: 21 December 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

entropy decoder automata factorization permutation group monoids cyclic group prefix code codes circular code minimal ideal bifix code Schützenberger representation semaphore code synchronized code

Mathematics Subject Classification ID

Cryptography (94A60) Semigroups in automata theory, linguistics, etc. (20M35) Theory of error-correcting codes and error-detecting codes (94Bxx) General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to information and communication theory (94-00)

Related Items

On the Commutative Equivalence of Algebraic Formal Series and Languages ⋮ A profinite approach to complete bifix decodings of recurrent languages ⋮ On Substitutions Preserving Their Return Sets ⋮ \(n\)-PS-codes, 2-infix-outfix codes and some related classes of codes ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ Topologies for error-detecting variable-length codes ⋮ Measuring power of generalised definite languages ⋮ Unnamed Item ⋮ State complexity of binary coded regular languages ⋮ Generalizations of Code Languages with Marginal Errors ⋮ Specular sets ⋮ New results on Nyldon words and Nyldon-like sets ⋮ On the size of transducers for bidirectional decoding of prefix codes ⋮ Reducing local alphabet size in recognizable picture languages ⋮ Factorization in Formal Languages ⋮ Enumeration Formulæ in Neutral Sets ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Upper Bounds on Mixing Time of Finite Markov Chains ⋮ Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences ⋮ Cross-bifix-free sets generation via Motzkin paths ⋮ Conway's work on iteration ⋮ Holonomy theorem for finite semigroups ⋮ Syntactic complexity of bifix-free languages ⋮ Generalized Dyck shifts ⋮ Robbins and Ardila meet Berstel ⋮ Careful synchronization of partial deterministic finite automata ⋮ Groups and semigroups defined by colorings of synchronizing automata ⋮ On the group of a rational maximal bifix code ⋮ Hall sets, Lazard sets and comma-free codes ⋮ Unbordered Pictures: Properties and Construction ⋮ A characterization of free pairs of upper triangular free monoid morphisms ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ Recognizability of morphisms ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ The second step in characterizing a three-word code ⋮ Mixing time for Markov chain on linear extensions ⋮ Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions ⋮ When variable-length codes meet the field of error detection ⋮ On the length of uncompletable words in unambiguous automata ⋮ Completely simple codes ⋮ Sofic-Dyck shifts ⋮ Some results on \((k, m)\)-comma codes ⋮ Relativized codes ⋮ Embedding subshifts of finite type into the Fibonacci–Dyck shift ⋮ Recognizability of the support of recognizable series over the semiring of the integers is undecidable ⋮ Unnamed Item ⋮ Bifix codes and Sturmian words ⋮ Structure and properties of strong prefix codes of pictures ⋮ Unnamed Item ⋮ Groups and decompositions of codes ⋮ Unnamed Item ⋮ Recent results on syntactic groups of prefix codes. ⋮ An automaton group with \textsf{PSPACE}-complete word problem ⋮ Codes and noncommutative stochastic matrices ⋮ Graded alphabets, circular codes, free Lie algebras and comma-free codes ⋮ A quadratic algorithm for road coloring ⋮ A coloring problem for infinite words ⋮ Representation theory of finite semigroups over semirings. ⋮ A Kraft-McMillan inequality for free semigroups of upper-triangular matrices ⋮ Unified theory for finite Markov chains ⋮ Homomorphic characterization of tree languages based on comma-free encoding ⋮ Automata for solid codes ⋮ Greedy Palindromic Lengths ⋮ Hybrid and generalized marked systems ⋮ The Karoubi envelope of the mirage of a subshift ⋮ On the decomposition of prefix codes ⋮ Freeness Problem for Matrix Semigroups of Parikh Matrices ⋮ Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages ⋮ Random walks on semaphore codes and delay de Bruijn semigroups ⋮ The semaphore codes attached to a Turing machine via resets and their various limits ⋮ The finite index basis property ⋮ Bifix codes and interval exchanges ⋮ Decision problems for convex languages ⋮ Binary codes that do not preserve primitivity ⋮ On the groups of codes with empty kernel. ⋮ Deciding regularity of hairpin completions of regular languages in polynomial time ⋮ Embeddings of local automata ⋮ The algebraic theory of Parikh automata ⋮ Polynomial-time right-ideal morphisms and congruences ⋮ Maximal bifix codes of degree 3 ⋮ Unique decipherability in formal languages ⋮ Shifts of \(k\)-nested sequences ⋮ Neutral and tree sets of arbitrary characteristic ⋮ Embedding a \(\theta \)-invariant code into a complete one ⋮ Finite maximal codes and triangle conjecture ⋮ Sets of Pictures Avoiding Overlaps ⋮ Maximal bifix decoding ⋮ Simplicity of augmentation submodules for transformation monoids ⋮ Complexity of proper prefix-convex regular languages ⋮ Complexity of proper prefix-convex regular languages ⋮ Complexity of bifix-free regular languages ⋮ Rationally almost periodic sequences, polynomial multiple recurrence and symbolic dynamics ⋮ Some combinatorial properties of solid codes ⋮ Implementation of Code Properties via Transducers ⋮ The intersection of \(3\)-maximal submonoids ⋮ Bernoulli measure on strings, and Thompson-Higman monoids. ⋮ Nyldon words ⋮ Černý's conjecture and the road colouring problem ⋮ On Nonnegative Integer Matrices and Short Killing Words ⋮ Attainable Values of Reset Thresholds ⋮ Normal distributions of finite Markov chains ⋮ Variable-length codes independent or closed with respect to edit relations ⋮ An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences ⋮ Acyclic, connected and tree sets ⋮ Binary codes that do not preserve primitivity ⋮ Theoretical and implementational aspects of the formal language server (LaSer) ⋮ Two-dimensional codes ⋮ State complexity of binary coded regular languages ⋮ An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences