scientific article; zbMATH DE number 3561239
From MaRDI portal
zbMath0359.94067MaRDI QIDQ4132170
Publication date: 1976
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Formal languages and automata (68Q45) Semigroups of transformations, relations, partitions, etc. (20M20) Groups and semigroups of linear operators (47D03) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02)
Related Items
Bilateral locally testable languages., On the expressive power of temporal logic, Shuffle on positive varieties of languages, Minimal schedulability interval for real-time systems of periodic tasks with offsets, About the power pseudovariety \(\mathbf{PCS}\), Arithmetics properties of substitutions and infinite automata, Pointlike sets for varieties determined by groups, Nonstandard characterization of pseudovarieties, Powers of subsets in a finite semigroup, Cohomological results in monoid and category theory via classifying spaces, Subsemigroups and complexity via the presentation lemma, Quantaloids, enriched categories and automata theory, Algebra for Infinite Forests with an Application to the Temporal Logic EF, Pseudovarieties of completely regular semigroups, On uniformity within \(NC^ 1\), Newton’s Forward Difference Equation for Functions from Words to Words, Covers for regular semigroups and an application to complexity, Green's relations in finite transformation semigroups, Operators and products in the lattice of existence varieties of regular semigroups, Inclusion relations between some congruences related to the dot-depth hierarchy, Recognizing pro-\(\mathrm{R}\) closures of regular languages, The \(\kappa\)-word problem over \(\mathsf{DRH}\), Parikh-reducing Church-Rosser representations for some classes of regular languages, A positive extension of Eilenberg's variety theorem for non-regular languages, Laws of the lattices of \(\sigma \)-local formations of finite groups, The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy, Equations and Coequations for Weighted Automata, On formations of monoids, Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions, Recognizable series on graphs and hypergraphs, Tropical representations and identities of the stylic monoid, Effective dimension of finite semigroups., Locally countable pseudovarieties, Iterated periodicity over finite aperiodic semigroups, Equational axioms associated with finite automata for fixed point operations in cartesian categories, On κ-reducibility of pseudovarieties of the form V ∗D, On the lattice of subvarieties of the wreath product of the variety of semilattices and the variety of semigroups with zero multiplication, A noncommutative extension of Mahler's theorem on interpolation series, Subword balance, position indices and power sums, Axiomatizing weighted synchronization trees and weighted bisimilarity, Complete κ-reducibility of pseudovarieties of the form DRH, A quadratic algorithm for road coloring, The \(\mathbf G\)-exponent of a pseudovariety of semigroups, Towards a pseudoequational proof theory, Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups, Finite aperiodic semigroups with commuting idempotents and generalizations, The variety of Kleene algebras with conversion is not finitely based, WCET free time analysis of hard real-time systems on multiprocessors: A regular language-based model, Irreducible actions., Classes of monoids with applications: formations of languages and multiply local formations of finite groups, On a locality-like property of the pseudovariety J, The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages, Theme and Variations on the Concatenation Product, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages, Once more on the lattice of subvarieties of the wreath product of the variety of semilattices and the variety of semigroups with zero multiplication, A minimal nonfinitely based semigroup whose variety is polynomially recognizable., Injective envelope and parallel decomposition of a transition system, Learning expressions and programs over monoids, Actions, wreath products of \(\mathcal C\)-varieties and concatenation product., Finite semigroup varieties of the form V*D, Expressive power of existential first-order sentences of Büchi's sequential calculus, Fuzzy tree language recognizability, Varieties of finite supersolvable groups with the M.~Hall property., Functional models of neurobiological processes, Rationality of the Möbius function of a composition poset, Pro-aperiodic monoids via saturated models, A topological approach to non-uniform complexity, Morita equivalence of finite semigroups, Learning in varieties of the form \(\mathbf {V^{*}LI}\) from positive data, Pointlike reducibility of pseudovarieties of the form V ∗D, The Shuffle Product: New Research Directions, Regular Geometrical Languages and Tiling the Plane, Profinite Monads, Profinite Equations, and Reiterman’s Theorem, Logic, semigroups and automata on words, Green's relations in deterministic finite automata, Prime decomposition theorem for arbitrary semigroups: General holonomy decomposition and synthesis theorem, Games, equations and the dot-depth hierarchy, Decomposition techniques for finite semigroups, using categories. I, Decomposition techniques for finite semigroups, using categories. II, Max-plus automata, Varieties, Profinite topologies, Geometrically closed positive varieties of languages, Bases for pseudovarieties closed under bideterministic product, Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes, Syntactic structures of regular languages, Languages and formations generated by \(D_4\) and \(Q_8\), On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids, Directed nonabelian sandpile models on trees, Positive varieties of tree languages, Algebraic tools for the concatenation product., Languages defined with modular counting quantifiers, The many faces of a translation, Character theory of monoids over an arbitrary field., The lattice of varieties of monoids, A noncommutative extension of Mahler's interpolation theorem, Keeping Secrets in Resource Aware Components, On the fine-structure of regular algebra, Free Burnside Semigroups, A conjecture on the concatenation product, Varieties and covarieties of languages (extended abstract), Star-free sets of integers, On varieties of rational languages and variable length codes. II, Groups in the syntactic monoid of a composed code, Logical relations and parametricity -- a Reynolds programme for category theory and programming languages, The equivalence and inclusion problems for NTS languages, Addition molle et fonctions p-locales, Embedding of regular semigroups in wreath products. II, Embedding of regular semigroups in wreath products. III, Pointlike sets and separation: a personal perspective, Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words, State complexity of projection on languages recognized by permutation automata and commuting letters, Carathéodory extensions of subclasses of regular languages, An extension of the wreath product principle for finite Mazurkiewicz traces, Isomorphisms of wreath products of monoids. I, The global dimension of the full transformation monoid (with an appendix by V. Mazorchuk and B. Steinberg), On the Cantor-Dedekind property of the Tilson order on categories and graphs, Generalized Pascal triangle for binomial coefficients of words, Some pseudovariety joins involving the pseudovariety of finite groups, The structure of the centralizer of a permutation, An introduction to the regular theory of fairness, Locally trivial categories and unambiguous concatenation, On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups, Wreath products of acts over monoids. I: Regular and inverse acts, Representation and uniformization of algebraic transductions, Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words), Languages polylog-time reducible to dot-depth 1/2, Semigroups and languages of dot-depth two, Two algebraic approaches to variants of the concatenation product, 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, The varieties of n-testable semigroups, Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts., Families of recognizable sets corresponding to certain varieties of finite monoids, Completing commutative actions., Polynomials, fragments of temporal logic and the variety DA over traces, Tree algebras and varieties of tree languages, On the maximality of languages with combined types of code properties, On the irreducibility of pseudovarieties of semigroups., Schützenberger and Eilenberg theorems for words on linear orderings, Varieties of recognizable tree series over fields, Bisimulations for fuzzy automata, Upper set monoids and length preserving morphisms, Some decision problems about controlled rewriting systems, The kernel of monoid morphisms, Geometrical regular languages and linear Diophantine equations: the strongly connected case, Recent results on syntactic groups of prefix codes., On the varieties of languages associated with some varieties of finite monoids with commuting idempotents, Products of languages with counter, Semidirectly closed pseudovarieties of locally trivial semigroups, Solving and factoring boundary problems for linear ordinary differential equations in differential algebras, Turing machines and bimachines, On the acceptance power of regular languages, The dual equivalence of equations and coequations for automata, An algebraic characterization of frontier testable tree languages, Varieties and rational functions, A decomposition theorem for probabilistic transition systems, Characterizations of rational \(\omega\)-languages by means of right congruences, Subword histories and associated matrices, Standard automata and semidirect products of transformation semigroups, Locally commutative power semigroups and counting factors of words, Equations and dot-depth one, Weighted automata with discounting, Criteria for the matrix equivalence of words, Descriptional and computational complexity of finite automata -- a survey, The expressive power of the shuffle product, Learning in the limit with lattice-structured hypothesis spaces, Inverse semigroups and extensions of groups by semilattices, Inverse semigroups and varieties of finite semigroups, Fuzzy relation equations and reduction of fuzzy automata, Infinite iteration of matrix semigroups. II: Structure theorem for arbitrary semigroups up to aperiodic morphism, Categories as algebra: An essential ingredient in the theory of monoids, The algebraic theory of Parikh automata, Local testability from words to traces, a suitable definition, An algebraic foundation for factoring linear boundary problems, Infinite-vertex free profinite semigroupoids and symbolic dynamics., Non-finitely based monoids., Finitely based monoids., Intersection graphs of \(S\)-acts, On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics, Synchronization and simplification, The Rhodes expansion and free objects in varieties of completely regular semigroups, The one-block property in varieties of semigroups, On generalized locally testable languages, On locally reversible languages, Fuzzy homomorphisms of algebras, On semidirect products of two finite semilattices, Generalized varieties of commutative and nilpotent semigroups, On M-varieties generated by power monoids, A language theoretic interpretation of the Schützenberger representations with applications to certain varieties of languages, Cascade decomposition of nonlinear systems, foliations and ideals of transitive Lie algebras, Almost finite expansions of arbitrary semigroups, Iteration of expansions. Unambiguous semigroups, Embedding of regular semigroups in wreath products, Non-uniform automata over groups, On the membership problem for pseudovarieties of commutative semigroups, Infinite iteration of matrix semigroups. I: Structure theorem for torsion semigroups, Power pseudovarieties of semigroups. I, Power pseudovarieties of semigroups. II, Equations on the semidirect product of a finite semilattice by a finite commutative monoid, Varieties of completely regular semigroups generated by Mal'cev products, Bounds on the variety generated by completely regular syntactic monoids from finite prefix codes, \(E\)-minimal semigroups, Level two of the quantifier alternation hierarchy over infinite words, The word problem for omega-terms over the Trotter-Weil hierarchy, Polynomial closure of group languages and open sets of the Hall topology, Over testable languages, Monoids respecting \(n\)-chains of intervals, Left and right negatively orderable semigroups and a one-sided version of Simon's theorem, Polynomial closure and unambiguous product, On calculating the Krohn-Rhodes decomposition of automata, Characterization of idempotent transformation monoids, The algebra of implicit operations, Thue-Morse sequence and p-adic topology for the free monoid, Programs over aperiodic monoids, Profinite categories and semidirect products, A method for the construction of complete congruences on lattices of pseudovarieties, Inverse monoids of dot-depth two, On a generalization of the Dyck-language over a two letter alphabet, The generating function of the number of subpatterns of a DOL sequence, La représentation ergodique d'un automate fini, Finite semigroup varieties defined by programs, Completeness of Park induction, Endomorphism monoids of free acts and O-wreath products of monoids. I. Annihilator properties, k-transformation semigroups and a conjecture of Tilson, A Krohn-Rhodes theorem for categories, Machines in a category, Series formelles et algèbres syntactiques, Finite semigroups, feedback, and the Letichevsky criteria on non-empty words in finite automata., Languages of R-trivial monoids, Variétés de langages et monoide des parties, A generalization of the Schützenberger product of finite monoids, Sur les séries associees à certains systèmes de Lindenmayer, Regular four-spiral semigroups, idempotent-generated semigroups and the Rees construction, An upper bound for the complexity of transformation semigroups, Classification of finite monoids: the language approach, A new class of C.F.L. for which the equivalence is decidable, The Birkhoff theorem for finite algebras, On ideal extensions of completely simple semigroups, On the holonomy decomposition of transformation semigroups, On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties., Recognizable languages and congruences, Unions of groups of small height, The variety generated by finite nilpotent monoids, Decidability of complexity one-half for finite semigroups, Classifying regular events in symbolic logic, Topologies for the free monoid, On the determination of Green's relations in finite transformation semigroups, A note on isomorphic simulation of automata by networks of two-state automata, Results on homomorphic realization of automata by \(\alpha_ 0\)-products, Complete systems of \(\mathcal B\)-rational identities, Which Kleene semigroups are finite?, On iterated semidirect products of finite semilattices, Two-sided wreath product of categories, Polynomial operations and hierarchies of concatenation, Quantaloidal nuclei, the syntactic congruence and tree automata, The cardinalities of the Green classes of the free objects in varieties of bands, Logically defined subsets of \(\mathbb{N}{}^ k\), The varieties of languages corresponding to the varieties of finite band monoids, Centralizers in symmetric inverse semigroups: Structure and order, Regular languages in \(NC\), Formulas, regular languages and Boolean circuits, On noncounting regular classes, Varieties of finite monoids and Büchi-McNaughton theorem, Efficient simplicity testing of automata, Local varieties of completely regular monoids, Bilateral semidirect products of transformation semigroups, Which finite monoids are syntactic monoids of rational \(\omega\)-languages, On a conjecture concerning dot-depth two languages, Closure of varieties of languages under products with counter, A unified syntactical approach to theorems of Putcha, Margolis, and Straubing on finite power semigroups, Varieties of automata and transformation semigroups, Some results on the dot-depth hierarchy, Some results on the generalized star-height problem, On pseudovarieties, A generalization of finiteness, Syntaktische Monoide und Hypercodes, On finite semigroups of matrices, Sur le produit de concatenation non ambigu, Kernel systems - a global study of homomorphisms on finite semigroups, Variétés de langages et opérations, On the interpolation of DOL-sequences, Semidirect products of pseudovarieties from the universal algebraist's point of view, The join of the pseudovarieties of \(\mathcal R\)-trivial and \(\mathcal L\)-trivial monoids, Trees, congruences and varieties of finite semigroups, Languages recognized by finite aperiodic groupoids, General varieties of tree languages, Group axioms for iteration, \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata, A proof of the Krohn--Rhodes Decomposition Theorem, Characterization of Glushkov automata, Free profinite \(\mathcal R\)-trivial, locally idempotent and locally commutative semigroups, Semigroup expansions using the derived category, kernel, and Malcev products, Right and left locally testable languages, Rees matrix covers and semidirect products of regular semigroups, Equations and monoid varieties of dot-depth one and two, On the support of graph Lie algebras, Completely regular semigroup varieties generated by Mal'cev products with groups, On a complete set of generators for dot-depth two, Transformation Semigroups for Rough Sets, Conelikes and ranker comparisons, A Theory of Formal Choreographic Languages, Parikh Matrices: Subword Indicators and Degrees of Ambiguity, Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages, Forbidden Patterns for FO2 Alternation Over Finite and Infinite Words, On the translation of automata to linear temporal logic, Classifying regular languages by their syntactic algebras, Substitution Principle and semidirect products, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Unnamed Item, Strongly locally testable semigroups with commuting idempotents and related languages, Syntactic monoids in the construction of systolic tree automata, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Polynomial closure of group languages and open sets of the Hall topology, A Parametrization of the Irreducible Representations of a Compact Inverse Semigroup, ON THE KROHN–RHODES COMPLEXITY OF SEMIGROUPS OF UPPER TRIANGULAR MATRICES, Décompositions en cascades des systèmes automatiques et feuilletages invariants, Reducibility vs. definability for pseudovarieties of semigroups, Polynomial closure and unambiguous product, Graph congruences and pair testing, FINITE SEMIGROUPS WITH INFINITE IRREDUNDANT IDENTITY BASES, Some reducibility properties for pseudovarieties of the form DRH, Unnamed Item, Varieties of finite categories, Unnamed Item, Extensions of an idea of McNaughton, Unnamed Item, Testing membership: Beyond permutation groups, Unnamed Item, On semidirectly closed pseudovarieties of finite semigroups and monoids, 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, Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples, Locality and Centrality: The Variety ZG, Sur le produit avec compteur modulo un nombre premier, Unnamed Item, Unnamed Item, Duality and Equational Theory of Regular Languages, Unnamed Item, A new algebraic invariant for weak equivalence of sofic subshifts, Unnamed Item, Generalized Eilenberg Theorem, Hierarchies of Piecewise Testable Languages, Subsequence Counting, Matrix Representations and a Theorem of Eilenberg, Literal Varieties of Languages Induced by Homomorphisms onto Nilpotent Groups, Algebras for classifying regular tree languages and an application to frontier testability, The product of rational languages, PSPACE-completeness of certain algorithmic problems on the subgroups of free groups, Algebraic and topological theory of languages, Projective indecomposable modules and quivers for monoid algebras, On semidirectly closed non-aperiodic pseudovarieties of finite monoids, Fairness and regularity for SCCS processes, Unnamed Item, BRET TILSON: HIS LIFE AND WORK, APERIODIC POINTLIKES AND BEYOND, The Karoubi envelope of the mirage of a subshift, Groups acting on semimetric spaces and quasi-isometries of monoids, Product Rules and Distributive Laws, Level Two of the Quantifier Alternation Hierarchy over Infinite Words, The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy, On the Krohn-Rhodes Cascaded Decomposition Theorem, On semidirectly closed pseudovarieties of aperiodic semigroups, SC-hyperdecidability of \(\mathbf R\), Divisible, torsion-free, and act regular generalized act wreath products, On dot-depth two, Free profinite locally idempotent and locally commutative semigroups, Eilenberg Theorems for Free, An application of the Ehrenfeucht-Fraisse game in formal language theory, The globals of pseudovarieties of ordered semigroups containingB2and an application to a problem proposed by Pin, Some results onC-varieties, Imre Simon: an exceptional graduate student, A Robust Class of Regular Languages, Unnamed Item, Testing Whether a Binary and Prolongeable Regular Language L Is Geometrical or Not on the Minimal Deterministic Automaton of Pref(L), Unnamed Item, A graphic language based on timing diagrams, On the equation \({\mathbf V}*{\mathbf G}={\mathcal E}{\mathbf V}\), The Power of Diversity, Geometrical Regular Languages and Linear Diophantine Equations, Minimal length normal forms for some soluble groups, Unnamed Item, Semidirect product with an order-computable pseudovariety and tameness., Minimal generators of submonoids of $A^\infty $, Circuit complexity and the expressive power of generalized first-order formulas, On reverse and general definite tree languages, On \(F\)-inverse covers of finite-above inverse monoids., Degree 2 transformation semigroups as continuous maps on graphs: Foundations and structure, Descriptional and Computational Complexity of Finite Automata, A Kleene Theorem for Forest Languages, MEALY MULTISET AUTOMATA, Morita equivalence of factorizable semigroups, Representations of relatively free profinite semigroups, irreducibility, and order primitivity, Matrix Mortality and the Černý-Pin Conjecture, On All Things Star-Free, AN EFFICIENT ALGORITHM TO TEST WHETHER A BINARY AND PROLONGEABLE REGULAR LANGUAGE IS GEOMETRICAL, Low Growth Equational Complexity, A Mahler's Theorem for Word Functions, Unnamed Item, Join irreducible semigroups, The Power of Programs over Monoids in DA, Sur une propriété d'itération des langages algébriques déterministes, Markov chains, ${\mathscr R}$-trivial monoids and representation theory, Weak Separation Problem for Tree Languages, Unnamed Item, The Relationship Among Fuzzy Languages, Upper Sets and Fuzzy Ordered Monoids, Identities and bases in the hypoplactic monoid, The ℛ-height of semigroups and their bi-ideals
