scientific article

zbMath0421.20025MaRDI QIDQ3853827

Publication date: 1979

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

Green's relations free semigroups word problem completely 0-simple semigroups transformation semigroup context-free languages MacMahon's master theorem codes languages Schützenberger groups Burnside problem syntactic monoids algebraic theory of automata algebraic linguistics rational prefix codes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Research exposition (monographs, survey articles) pertaining to group theory (20-02) Semigroups (20Mxx)

Related Items

Rational languages and the Burnside problem, On varieties of rational languages and variable length codes. II, Truncations of infinite matrices and algebraic series associated with some CF grammars, Traces, dependency graphs and DNLC grammars, Systèmes codés. (Coded systems), Groups in the syntactic monoid of a composed code, Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht, A property of the Schützenberger product, Rational strong codes and structure of rational group languages, On permutation properties in groups and semigroups, Monoids with disjunctive identity and their codes, A characterization of rational star languages generated by strong codes, Sémantique asynchrone et comportements infinis en CPS, Noncommutative factorization of variable-length codes, The structure of the centralizer of a permutation, An example of a one-relator group that is not a one-relation monoid, Easy multiplications. I: The realm of Kleene's theorem, On the topological structure of a finitely generated semigroup of matrices, Categoricity results for $L_{\infty \kappa}$-free algebras, Relatively f-disjunctive languages, Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words), Finite biprefix sets of paths in a graph, Theory of traces, Membership testing in commutative transformation semigroups, Semigroups and languages of dot-depth two, The synthesis theorem for finite regular semigroups, and its generalization, Partially ordered finite monoids and a theorem of I. Simon, A short proof that $\hat S^+_ A$ is finite if S is finite, Expletives in languages and middle units in semigroups, Théorèmes de transfert pour les polynômes partiellement commutatifs. (Transfer theorems for partially commutative polynomials), Permutation properties and the Fibonacci semigroup, Counting with rational functions, Concatenation of inputs in a two-way automaton, A note on regular classes in special Thue systems, Characterization of idempotent transformation monoids, On a conjecture of Rhodes, Every finitely generated submonoid of a free monoid has a finite Malcev's presentation, An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group, Sur les automates qui reconnaissent une famille de langages. (On the automata which accept a family of languages), Inverse monoids of dot-depth two, On the descriptive power of special Thue systems, Equational properties of iteration in algebraically complete categories, Inventories of unavoidable languages and the word-extension conjecture, Machines in a category, Operatorenkalkül über freien Monoiden I: Strukturen, Augmentations and wreath products of monoids, Closure operators on languages and binary relations, Sur le calcul du monoide syntaxique d'un sous monoide finiment engendre, Semigroups with each element disjunctive, A semigroup and Gaussian polynomials, Classification of finite monoids: the language approach, On varieties of rational languages and variable-length codes, Thue congruences and the Church-Rosser property, On a special monoid with a single defining relation, Baionnettes et cardinaux, On the syntactic transformation semigroup of a language generated by a finite biprefix code, A synchronization property of pure subsemigroups of a free semigroup, Finite DOL languages and codes, Unions of groups of small height, A finiteness condition for semigroups generalizing a theorem of Hotzel, Topologies for the free monoid, On the determination of Green's relations in finite transformation semigroups, Counting monoids and rational languages, Results on homomorphic realization of automata by $\alpha_ 0$-products, Finiteness and iteration conditions for semigroups, Languages and scanners, Which Kleene semigroups are finite?, Conjugacy in special monoids, On the history of the term semigroup, It is undecidable whether a finite special string-rewriting system presents a group, Inverse monoids and rational Schreier subsets of the free group, Logically defined subsets of $\mathbb{N}{}^ k$, AUTOMATE, a computing package for automata and finite semigroups, The varieties of languages corresponding to the varieties of finite band monoids, Centralizers in symmetric inverse semigroups: Structure and order, On the linear orderability of two classes of finite semigroups, On the structure of some group codes, Regular languages in $NC$, On noncounting regular classes, Star-free trace languages, Efficient simplicity testing of automata, The free partially commutative Lie algebra: Bases and ranks, Some properties of finite special string-rewriting systems, Limited semaphore codes, On a conjecture of Brown, Some results on the dot-depth hierarchy, Some results on the generalized star-height problem, Uniformly synchronous codes, Remarks on the structure of the multiplicative monoid of integers modulo $m$, A conjugacy invariant for reducible sofic shifts and its semigroup characterizations, Syntactic and Rees indices of subsemigroups, Languages recognized by finite aperiodic groupoids, On two problems related to cancellativity, Infinite iteration of matrix semigroups. I: Structure theorem for torsion semigroups, Some quasi-ordered classes of finite commutative semigroups, Complexity results on the conjugacy problem for monoids, Power pseudovarieties of semigroups. I, Pseudo-natural algorithms for the word problem for finitely presented monoids and groups, The lattices of varieties and pseudovarieties of band monoids, On deciding whether a monoid is a free monoid or is a group, On syntactic monoids of biunitary submonoids determined by homomorphisms from free semigroups onto completely simple semigroups, Graded algebras, algebraic functions, planar trees, and elliptic integrals, The fractal nature of folds and the Walsh copolymers, Presentations for monoids of finite partial isometries, The finite basis problem for words with at most two non-linear variables., Factorization forests for infinite words and applications to countable scattered linear orderings, Fuzzy submonoids, fuzzy preorders and quasi-metrics, On the 3-state Mealy automata over an $m$-symbol alphabet of growth order $[n^{\log n/2\log m}$.], Semigroup theory of symmetry, A geometric characterization of automatic semigroups, An algorithmic approach to the problem of a semiretract base, Decidable sentences of Church-Rosser congruences, The varieties of n-testable semigroups, The Möbius function on abelian semigroups., On disjoint unions of finitely many copies of the free monogenic semigroup., On the maximality of languages with combined types of code properties, On residual finiteness of monoids, their Schützenberger groups and associated actions., Graph inverse semigroups: their characterization and completion., A classification of disjoint unions of two or three copies of the free monogenic semigroup., Factorization forests of finite height, Graph products of spheres, associative graded algebras and Hilbert series., Soliton automata, Cancellation in semigroups in which $x^ 2=x^ 3$, Solid codes and disjunctive domains, Groups and decompositions of codes, Decision problems for finite special string-rewriting systems that are confluent on some congruence class, Recent results on syntactic groups of prefix codes., On the varieties of languages associated with some varieties of finite monoids with commuting idempotents, f-disjunctive congruences and a generalization of monoids with length, Products of languages with counter, A correspondence between a class of monoids and self-similar group actions. I., On group codes, $\mathbb{N}$-rationality of zeta functions, On the decomposition of prefix codes, Decompositions of recognizable strong maximal codes, Groups of finite elementary codes, Locally commutative power semigroups and counting factors of words, Green index and finiteness conditions for semigroups., Structure of prime finitely presented monomial algebras., Range sets and partition sets in connection with congruences and algebraic invariants, Adjan's theorem and conjugacy in semigroups, Equations and dot-depth one, Languages with membership determined by single letter factors, Weighted automata with discounting, Supertropical matrix algebra, Bilateral semidirect product decompositions of transformation monoids., Semigroup identities in the monoid of two-by-two tropical matrices., On properties not inherited by monoids from their Schützenberger groups., A note on autodense related languages, On the groups of codes with empty kernel., Inverse semigroups and extensions of groups by semilattices, Inverse semigroups and varieties of finite semigroups, Linear semigroups with permutation properties, Infinite iteration of matrix semigroups. II: Structure theorem for arbitrary semigroups up to aperiodic morphism, On monomial algebras, A note on F-disjunctive languages, On a constant word in finite semigroups, Infinite-vertex free profinite semigroupoids and symbolic dynamics., Regular autodense languages, Semigroup presentations for test local groups., Intersection graphs of $S$-acts, On three approaches to conjugacy in semigroups., On finitely generated idempotent semigroups., Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group, Generalized affine transformation monoid of a free module of finite rank over finite chain rings., Compositions of maximal codes, The applications of solid codes to r-R and r-D languages, Cayley graphs as classifiers for data mining: the influence of asymmetries, Semigroups for which every right congruence of finite index is finitely generated, Green's relations and stability for subsemigroups, On semidirect products of two finite semilattices, L codes and number systems, A combinatorial proof of the Cayley-Hamilton theorem, Realisation locale des systèmes non linéaires, algèbres de Lie filtrees transitives et séries generatrices non commutatives, On M-varieties generated by power monoids, On the centers of a language, Translational hulls and block designs, Some algorithms on the star operation applied to finite languages, A language theoretic interpretation of the Schützenberger representations with applications to certain varieties of languages, Some undecidability results for non-monadic Church-Rosser Thue systems, Inversion of matrices over a commutative semiring, Power monoids and finite J-trivial monoids, An application of the matrix representation of transductions, The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids, Code properties and homomorphisms of DOL systems, Almost finite expansions of arbitrary semigroups, Iteration of expansions. Unambiguous semigroups, Arbitrary vs. regular semigroups, Biprefix codes, inverse semigroups and syntactic monoids of injective automata, Partial commutations and faithful rational transductions, Conjugacy in monoids with a special Church-Rosser presentation is decidable, The groups of the semigroup of compact subsets of a topological group, Quelques propriétés des systèmes générateurs minimaux des monoides. (Some properties of minimal generating systems of monoids), Non-uniform automata over groups, On the expressive power of temporal logic for infinite words, Sequential machines realized by group representations, Test sets for morphisms with bounded delay, Some properties of commutation in free partially commutative monoids, On finitely recognizable semigroups, Diagram groups and directed 2-complexes: homotopy and homology., Equations on the semidirect product of a finite semilattice by a finite commutative monoid, On the effects of noise and speed on computations, On the expressive power of temporal logic, The smallest Mealy automaton of intermediate growth., On factorization forests of finite height, About the power pseudovariety $\mathbf{PCS}$, Semiretracts of a free monoid, Bounds on the variety generated by completely regular syntactic monoids from finite prefix codes, A finiteness condition for semigroups which generalizes Green-Rees' theorem, Periodic endomorphisms of a free monoid, Decidability and independence of conjugacy problems in finitely presented monoids, Reidemeister-Schreier type rewriting for semigroups, Irrationality and codes, On the size of independent systems of equations in semigroups, Sofic shifts with synchronizing presentations, On functors associated to a simple root, Left and right negatively orderable semigroups and a one-sided version of Simon's theorem, Subsemigroups and complexity via the presentation lemma, Slightly commutative Kleene semigroups, Polynomial closure and unambiguous product, Subgroups of free idempotent generated semigroups need not be free., A first step in characterizing three-element codes, Free local semigroup constructions, Some combinatorial properties of infinite words and applications to semigroup theory, Algebras defined by equations, Presentations for subsemigroups -- applications to ideals of semigroups, Formulating patterns in problem solving, Higher dimensional generalizations of the Thompson groups, A note on decidability questions on presentations of word semigroups, A proof of Simon's theorem on piecewise testable languages, The equational logic of fixed points, Completeness of Park induction, On congruences of automata defined by directed graphs, Idempotents and one-sided units: lattice invariants and a semigroup of functors on the category of monoids, Test sets for the universal and existential closure of regular tree languages., Completely simple codes, Hecke-Kiselman monoids of small cardinality., Weak projectives of finite semigroups, Finite generation and presentability of wreath products of monoids., Some results in $r$-disjunctive languages and related topics, Iterated periodicity over finite aperiodic semigroups, On the lattice of subvarieties of the wreath product of the variety of semilattices and the variety of semigroups with zero multiplication, Proper/residually-finite idempotent semirings., Arithmetical complexity of symmetric D0L words., Non-commutative extensions of the MacMahon Master Theorem, Finite aperiodic semigroups with commuting idempotents and generalizations, Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order, Relatively regular languages and thin codes, On the multiplicative monoid of $n\times n$ matrices over $\mathbb{Z}_{p^m}$., Tied monoids, Generalized affine transformation monoids on Galois rings., Once more on the lattice of subvarieties of the wreath product of the variety of semilattices and the variety of semigroups with zero multiplication, Conjugacy in inverse semigroups, Conjugation in semigroups., On the word problem for the free Burnside semigroups satisfying $x^2=x^3$., Möbius inversion formula for the trace group, A finiteness criterion for inverse semigroups, Calcul de longueurs de chaînes de réécriture dans le monoïde libre, On free semilattice-ordered semigroups satisfying $x^{n}=x$, Semigroups arising from asynchronous automata., A spectral property for concurrent systems and some probabilistic applications, Presentations for subgroups of monoids, The lattices of prefixes and overlaps of traces, Logic, semigroups and automata on words, Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings, E-convex infix codes, Commutativity in free inverse monoids, On the disjunctive set problem, Fixed point languages of rational transductions, Prime decomposition theorem for arbitrary semigroups: General holonomy decomposition and synthesis theorem, Minimal automaton for a factorial, transitive, and rational language, Games, equations and the dot-depth hierarchy, An order topology for finitely generated free monoids, Series-parallel languages and the bounded-width property, Membership problems for regular and context-free trace languages, Infinite words with linear subword complexity, Regular monoids generated by two Galois connections, Algorithmic problems in varieties of semigroups, Arithmetic and $k$-maximality of the cyclic free magma, Decomposition techniques for finite semigroups, using categories. I, On recognition and compactification, Group axioms for iteration, Families of locally testable languages, A proof of the Krohn--Rhodes Decomposition Theorem, Optimal estimation on the order of local testability of finite automata, Varieties and pseudovarieties of ordered normal bands, Sur les monoides dont tous les groupes sont resolubles, Determinants and Möbius functions in trace monoids, Automatic semigroups, On a generalization of regular expressions, Completely regular semigroups as semigroups of partial transformations, Regular Gröbner bases, Equations and monoid varieties of dot-depth one and two, The word problem of inverse monoids presented by one idempotent relator, Right projective semigroups with 0, Diagonal ranks of semigroups., Finite reasons for safety, The transitivity of primary conjugacy in regular $\omega$-semigroups, Residual finiteness of a class of semigroups presented by a single relation, Green's equivalences in finite semigroups of binary relations, On the monoid of partial isometries of a finite star graph, Unnamed Item, Deitmar schemes, graphs and zeta functions, Certain Categories Derived from Normal Categories, ON SEPARABILITY FINITENESS CONDITIONS IN SEMIGROUPS, Zeta Functions of Formal Languages, Characterization of the pseudovariety generated by finite monoids satisfying $\mathcal R=\mathcal H$., Transformations of sequential specifications into concurrent specifications by synchronization guards, On uniformity within $NC^ 1$, Efficient solution of some problems in free partially commutative monoids, The syntactic monoid of hairpin-free languages, A GENERALISATION OF HIGHER-RANK GRAPHS, When are Rees Congruences Principal?, Distance desert automata and the star height problem, A note on thue systems with a single defining relation, On the semiprimitivity of finitely generated algebras, Bi-infinitary codes, Compositional representation of rational functions, Trace languages defined by regular string languages, Extensions of an idea of McNaughton, Semiprimeness of semigroup algebras, Testing membership: Beyond permutation groups, New results on the generalized star-height problem, Notes on finite asynchronous automata, Characterizing classes of regular languages using prefix codes of bounded synchronization delay, Equations on the semidirect product of a finite semilattice by a $\mathcal {J}$-trivial monoid of height $k$, Schützenberger-like products in non-free monoids, Reflectors to quantales, Ranks and presentations of some normally ordered inverse semigroups, Idempotent varieties of incidence monoids and bipartite posets, Unnamed Item, Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions, Presentations for three remarkable submonoids of the dihedral inverse monoid on a finite set, Hypercodes, Right Convex Languages and their Syntactic Monoids, Green's classifications and evolutions of fixed-order networks, Acts over semigroups, Some aspects of Green's relations on periodic semigroups, Classifying regular languages by their syntactic algebras, Normal subsemigroups of finite transformation semigroups, A new definition of conjugacy for semigroups, On the monoid of partial isometries of a cycle graph, Recognizability in residuated lattices, On codes having no finite completion, Unnamed Item, Unnamed Item, Variants of epigroups and primary conjugacy, The wreath product of atoms of the lattice of semigroup varieties, GROWTHS OF ENDOMORPHISMS OF FINITELY GENERATED SEMIGROUPS, Bisections reconnaissables, WATSON-CRICK BORDERED WORDS AND THEIR SYNTACTIC MONOID, Algebraic and topological theory of languages, On semidirectly closed non-aperiodic pseudovarieties of finite monoids, A finiteness condition for finitely generated semigroups, Generalized cancellation-and-permutation properties, regular languages and supports of rational series, Unnamed Item, A hierarchy of cyclic languages, Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems, Unnamed Item, Disjunctive languages and compatible orders, Groups acting on semimetric spaces and quasi-isometries of monoids, Varieties of Commutative Semigroups, Unnamed Item, Semigroups of zero entropy, Codes et motifs, Unnamed Item, On one-relator monoids and one-relator groups, Connection between Markov chains on finite simple groups and fundamental groups, A state space approach to the finite automata, On dot-depth two, Unnamed Item, The pseudovariety of semigroups of triangular matrices over a finite field, Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems, On combinatorial properties of the Arshon sequence, Perfect Congruences on a Free Monoid, A generalization of traces, The structure of finite monoids satisfying the relation $\mathcal R=\mathcal H$., [https://portal.mardi4nfdi.de/wiki/Publication:3883200 Rel�vement d'une mesure ergodique par un codage], On the pseudovariety generated by all finite monoids satisfying $\mathcal R=\mathcal H$., Unnamed Item, Properties of the subsemigroups of the bicyclic monoid, Right noetherian semigroups, Factorizing The Polynomial of a Code, On $C^*$-algebras associated to right LCM semigroups, IDENTITIES AND A BOUNDED HEIGHT CONDITION FOR SEMIGROUPS, Ensembles libres de chemins dans un graphe, On the size of independent systems of equations in semigroups, Unnamed Item, COMPLETELY REDUCIBLE SETS, Efficiency for self semi-direct products of the free Abelian monoid on two generators., Infix Congruences on a Free Monoid, QUASI-ISOMETRY AND FINITE PRESENTATIONS OF LEFT CANCELLATIVE MONOIDS, On codes having no finite completion, Codes and Bernoulli partitions, Theory of Constructive Semigroups with Apartness – Foundations, Development and Practice, The Polycyclic Inverse Monoids and the Thompson Groups Revisited, Generalized symmetry of graphs, Free Burnside Semigroups