scientific article

Publication date: 1985

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

algorithms conjugacy permutation groups deciphering delay prefix codes variable-length codes probabilistic approach semisimple algebras unambiguous automata circular codes biprefix codes syntactic approach factorization of free monoids synchronization of semaphore codes thin codes

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.) (16S10) Ideal theory for semigroups (20M12) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Probability theory on algebraic and topological structures (60B99) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory (94-01) Prefix, length-variable, comma-free codes (94A45) Multiply transitive finite groups (20B20)

Related Items

Automates et codes zigzag ⋮ Polypodic codes ⋮ Zeta Functions of Formal Languages ⋮ On $z$-submonoids and $z$-codes ⋮ Rebootable and suffix-closed $\omega $-power languages ⋮ Finite Completion of comma-free codes Part 1 ⋮ Finite Completion of comma-free codes Part 2 ⋮ Circular splicing and regularity ⋮ The expressibility of languages and relations by word equations ⋮ A completion algorithm for codes with bounded synchronization delay ⋮ Compositional representation of rational functions ⋮ Caractérisation results about $L$ codes ⋮ Intercodes and the semigroups they generate ⋮ The finest homophonic partition and related code concepts ⋮ Finitary codes for biinfinite words ⋮ On the factorization conjecture ⋮ On coding morphisms for zigzag codes ⋮ Product decompositions of semigroups induced by action pairs ⋮ Maximal circular codesversusmaximal codes ⋮ A Construction for Variable Dimension Strong Non-Overlapping Matrices ⋮ Unnamed Item ⋮ On entropy and intrinsic ergodicity of coded subshifts ⋮ Church-Rosser codes ⋮ Codes limites et factorisations finies du monoïde libre ⋮ Unnamed Item ⋮ On codes having no finite completion ⋮ The syntactic monoid of the semigroup generated by a maximal prefix code ⋮ Semaphore Codes and Ideals ⋮ A property of biprefix codes ⋮ The Average State Complexity of the Star of a Finite Set of Words Is Linear ⋮ On a Generalization of Standard Episturmian Morphisms ⋮ On some problems related to palindrome closure ⋮ A hierarchy for circular codes ⋮ How Many Figure Sets Are Codes? ⋮ Bisections reconnaissables ⋮ FINITE COMPLETIONS VIA FACTORIZING CODES ⋮ WATSON-CRICK BORDERED WORDS AND THEIR SYNTACTIC MONOID ⋮ If a DOL language is k-power free then it is circular ⋮ SMALL p-GROUPS WITH FULL-RANK FACTORIZATION ⋮ Valuations and unambiguity of languages, with applications to fractal geometry ⋮ Languages and P0L schemes ⋮ Bijective sequential mappings of a free monoid onto another ⋮ Dépliage d'un graphe pointé en un cactus ⋮ Variable-length codes for error correction ⋮ Completing codes ⋮ Unnamed Item ⋮ Disjunctive languages and compatible orders ⋮ Multiplied Complete Fix-Free Codes and Shiftings Regarding the 3/4-Conjecture ⋮ Factorisation des ensembles préfixiels ⋮ THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY ⋮ A note on the free submonoids of the monoid of prefix codes ⋮ ON NON-PRIMITIVE PALINDROMIC CONTEXT-FREE LANGUAGES ⋮ Infinitely generated semigroups and polynomial complexity ⋮ Irreducibility of certain pseudovarieties¹ ⋮ An algorithm of test for fuzzy codes ⋮ Decidability of code properties ⋮ THE AVERAGE STATE COMPLEXITY OF RATIONAL OPERATIONS ON FINITE LANGUAGES ⋮ The decodability and correctability of codes ⋮ How to Strengthen Pseudo-random Generators by Using Compression ⋮ The Polycyclic MonoidsP_nand the Thompson GroupsV_n,1 ⋮ Some decompositions of Bernoulli sets and codes ⋮ Unnamed Item ⋮ Unique decipherability in the additive monoid of sets of numbers ⋮ On the regularity of circular splicing languages: a survey and new developments ⋮ Brick codes: families, properties, relations ⋮ Watson-Crick Conjugate and Commutative Words ⋮ Characterizations of $k$-comma codes and $k$-comma intercodes ⋮ Decision Problems for Convex Languages ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ INFINITE ITERATED FUNCTION SYSTEMS IN CANTOR SPACE AND THE HAUSDORFF MEASURE OF ω-POWER LANGUAGES ⋮ Generalizations of Code Languages with Marginal Errors ⋮ A more efficient notion of zigzag stability ⋮ K-catenation and applications:k-prefix codes ⋮ Optimal Prefix Codes And Huffman Codes ⋮ UNAMBIGUOUS MORPHIC IMAGES OF STRINGS ⋮ THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE ⋮ FREE MONOID THEORY: MAXIMALITY AND COMPLETENESS IN ARBITRARY SUBMONOIDS ⋮ Ensembles libres de chemins dans un graphe ⋮ Characterizations of the decidability of some problems for regular trace languages ⋮ n-Prefix–suffix languages^∗ ⋮ It is decidable whether or not a permutation-free morphism is an l code ⋮ On codes having no finite completion ⋮ On codes with finite interpreting delay: a defect theorem ⋮ Product of Finite Maximal P-Codes. This paper was supported in part by HK UGC grants 9040596, 9040511 and City U Strategic Grants 7001189, 7001060, and by the Natural Science Foundation of China (project No. 60073056) and the Guangdong Provincial Natural Science Foundation (project No. 001174) ⋮ The Polycyclic Inverse Monoids and the Thompson Groups Revisited ⋮ Puissance extérieure d'un automate déterministe, application au calcul de la fonction zêta d'un système sofique ⋮ Asynchronous sliding block maps ⋮ On varieties of rational languages and variable length codes. II ⋮ On the size of transducers for bidirectional decoding of prefix codes ⋮ Conjugacy relations of prefix codes ⋮ Transducers and the decidability of independence in free monoids ⋮ On the complexity of infinite words generated by countable $q$-automata ⋮ Monoids with disjunctive identity and their codes ⋮ On the Density of Context-Free and Counter Languages ⋮ Generalizations of Code Languages with Marginal Errors ⋮ OVERLAP-FREE LANGUAGES AND SOLID CODES ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Periodic endomorphisms of a free monoid ⋮ On generators of rational $\omega$-power languages ⋮ FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION ⋮ ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS ⋮ Ranks of binary relations ⋮ The syntactic monoid of hairpin-free languages ⋮ Valuations, regular expressions, and fractal geometry ⋮ A note on r-extensible prefix codes ⋮ On the word problem for special monoids ⋮ Measuring power of locally testable languages ⋮ Logarithmic density and measures on semigroups ⋮ Dense property of initial literal shuffles ⋮ Bi-infinitary codes ⋮ A characterization of intercodes ⋮ Permutation cellular automata ⋮ Elementariness of a finite set of words is co-NP-complete ⋮ On a class of infinitary codes ⋮ Fixed points of endomorphisms over special confluent rewriting systems. ⋮ Free submonoids in the monoid of languages ⋮ Left-divisibility and word problems in single relation monoids ⋮ On the proportion of prefix codes in the set of three-element codes ⋮ A genetic scale of reading frame coding ⋮ Deterministic Caterpillar Expressions ⋮ Coding properties of DNA languages. ⋮ An analytical model of gene evolution with 9 mutation parameters: An application to the amino acids coded by the common circular code ⋮ On a Problem of Satyanarayana Regarding the Recognizability of Codes ⋮ Strong representations of the polycyclic inverse monoids: cycles and atoms. ⋮ Defect theorem in the plane ⋮ Uniformly bounded duplication codes ⋮ On the word problem for free products of semigroups and monoids ⋮ Unique decipherability in the monoid of languages: an application of rational relations ⋮ Extremal minimality conditions on automata ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid ⋮ Compatibility relations on codes and free monoids ⋮ A sufficient condition for the Hanna Neumann property of submonoids of a free monoid. ⋮ f-disjunctive congruences and a generalization of monoids with length ⋮ Disjoint long cycles in a graph ⋮ Codes and noncommutative stochastic matrices ⋮ Strongly compatible total orders on free monoids ⋮ The code problem for directed figures ⋮ Strong trinucleotide circular codes ⋮ Codes générateurs minimaux de langages de mots bi-infinis ⋮ Bond-free DNA language classes ⋮ Solid codes and the uniform density of fd-domains. ⋮ Some properties of involution binary relations ⋮ Relatively regular languages and thin codes ⋮ On the structure of some group codes ⋮ The entropies of renewal systems ⋮ On the ratio of prefix codes to all uniquely decodable codes with a given length distribution ⋮ Codes induced by alternative codes ⋮ Limited semaphore codes ⋮ Defect theorems with compatibility relations. ⋮ Two-letter group codes that preserve aperiodicity of inverse finite automata. ⋮ Uniformly synchronous limited codes ⋮ Codes et motifs ⋮ Uniformly synchronous codes ⋮ Generalised operations in free harmonic analysis ⋮ Prefix-primitive annihilators of languages under some operations ⋮ Classifications of bifix codes ⋮ INVOLUTIVELY BORDERED WORDS ⋮ Palindromic richness ⋮ Infinite-vertex free profinite semigroupoids and symbolic dynamics. ⋮ Symbolic Dynamics, Flower Automata and Infinite Traces ⋮ The universal Boolean inverse semigroup presented by the abstract Cuntz-Krieger relations ⋮ On a complete set of operations for factorizing codes ⋮ Generating boxes from ordered sets and graphs ⋮ On the homological classification of semigroups with local units ⋮ DIRECTED FIGURE CODES: DECIDABILITY FRONTIER ⋮ Unique Decipherability in the Monoid of Languages: An Application of Rational Relations ⋮ Locally catenative sequences and Turtle graphics ⋮ A stochastic model of gene evolution with time dependent pseudochaotic mutations ⋮ Maximal prefix products ⋮ On the deficit of a finite set of words ⋮ An order topology for finitely generated free monoids ⋮ PREFIX-FREE ŁUKASIEWICZ LANGUAGES ⋮ F-transforms and semimodule homomorphisms ⋮ CODING PARTITIONS OF REGULAR SETS ⋮ COMPLETELY REDUCIBLE SETS ⋮ On certain inverse semigroups associated with one-sided topological Markov shifts ⋮ Picture codes ⋮ Unambiguous recognizable two-dimensional languages ⋮ On the simplest centralizer of a language ⋮ Confluence problems for trace rewriting systems ⋮ An extended genetic scale of reading frame coding ⋮ On low-complexity bi-infinite words and their factors ⋮ Non literal transducers and some problems of normality ⋮ SE-SYSTEMS, TIMING MECHANISMS, AND TIME-VARYING CODES ⋮ Right $k$-dense languages ⋮ On the degree of finite maximal biprefix codes