scientific article

Publication date: 1986

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

finite automata regular languages hierarchies finite monoids varieties of semigroups varieties of languages

Formal languages and automata (68Q45) Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

Varieties of completely regular semigroups generated by Mal'cev products, State complexity of projection on languages recognized by permutation automata and commuting letters, Shuffle on positive varieties of languages, Vectorial languages and linear temporal logic, Primitive morphisms, Morphic congruences and D0L languages, The word problem for omega-terms over the Trotter-Weil hierarchy, Complexity of the identity checking problem for finite semigroups., Factorization forests for infinite words and applications to countable scattered linear orderings, Polynomial closure of group languages and open sets of the Hall topology, Sofic shifts with synchronizing presentations, Monoids respecting $n$-chains of intervals, Left and right negatively orderable semigroups and a one-sided version of Simon's theorem, Quantaloids, enriched categories and automata theory, Locally trivial categories and unambiguous concatenation, On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups, On calculating the Krohn-Rhodes decomposition of automata, Locality of DS and associated varieties, Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts., Deletion along trajectories, Operators and products in the lattice of existence varieties of regular semigroups, Remarks on isomorphisms of regressive transformation semigroups, Profinite categories, implicit operations and pseudovarieties of categories, On a conjecture of Rhodes, A method for the construction of complete congruences on lattices of pseudovarieties, The $\kappa$-word problem over $\mathsf{DRH}$, Recognizing splicing languages: syntactic monoids and simultaneous pumping, Tree algebras and varieties of tree languages, Regular languages and partial commutations, Finite semigroup varieties defined by programs, A proof of Simon's theorem on piecewise testable languages, Size lower bounds for quantum automata, An algebraic approach to data languages and timed languages, The size of power automata., Unambiguous Büchi automata., Finite semigroups, feedback, and the Letichevsky criteria on non-empty words in finite automata., Varieties of recognizable tree series over fields, Language theoretical properties of hairpin formations, The representation theory of the monoid of all partial functions on a set and related monoids as EI-category algebras., Upper set monoids and length preserving morphisms, Piecewise testable languages via combinatorics on words, On the varieties of languages associated with some varieties of finite monoids with commuting idempotents, On the word problem for syntactic monoids of piecewise testable languages., Semidirectly closed pseudovarieties of locally trivial semigroups, Closures of regular languages for profinite topologies., Unary enhancements of inherently non-finitely based semigroups., Topologies for the free monoid, The automata that define representations of monomial algebras., Languages and scanners, On iterated semidirect products of finite semilattices, Modal functions for concise definition of state machines and products, Polynomial operations and hierarchies of concatenation, Normal forms under Simon's congruence, Quantaloidal nuclei, the syntactic congruence and tree automata, Logically defined subsets of $\mathbb{N}{}^ k$, The varieties of languages corresponding to the varieties of finite band monoids, The dual equivalence of equations and coequations for automata, A note on the commutative closure of star-free languages, An algebraic characterization of frontier testable tree languages, Dynamical properties of PWD0L systems, Regular languages in $NC$, Semigroups of order preserving mappings on a finite chain: A new class of divisors, Fine hierarchies and m-reducibilities in theoretical computer science, Finite basis problem for involution monoids of unitriangular Boolean matrices, Formulas, regular languages and Boolean circuits, Star-free trace languages, Efficient simplicity testing of automata, Local varieties of completely regular monoids, Quantum finite automata: advances on Bertoni's ideas, On varieties of meet automata, Locally commutative power semigroups and counting factors of words, Monoid varieties defined by $x^{n+1}=x$ are local, Closure of varieties of languages under products with counter, Bilateral semidirect product decompositions of transformation monoids., A unified syntactical approach to theorems of Putcha, Margolis, and Straubing on finite power semigroups, Some results on the generalized star-height problem, Fragments of first-order logic over infinite words, Extensions to Barrington's M-program model, On deterministic finite automata and syntactic monoid size, An application of a theorem of Ash to finite covers., The expressive power of the shuffle product, On the lattice of sub-pseudovarieties of DA., Burrows-Wheeler transformations and de Bruijn words, Inverse semigroups and varieties of finite semigroups, Inverse monoids of partial graph automorphisms, Infinite-vertex free profinite semigroupoids and symbolic dynamics., Catalan monoids, monoids of local endomorphisms, and their presentations, A conjugacy invariant for reducible sofic shifts and its semigroup characterizations, General varieties of tree languages, Minimal automaton for a factorial, transitive, and rational language, On locally reversible languages, Varieties, The factorisation forest theorem, The semilattices of nilextensions of left groups and their varieties, Associativity of products of existence varieties of regular semigroups, Automata, Boolean matrices, and ultimate periodicity., Languages defined with modular counting quantifiers, Non-uniform automata over groups, Sequential machines realized by group representations, Join decompositions of pseudovarieties involving semigroups with commuting idempotents, State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs, Locality and Centrality: The Variety ZG, The monoid of all orientation-preserving and extensive partial transformations on a finite chain, On the transition monoid of the Stallings automaton of a subgroup of a free group, Forbidden Patterns for FO² Alternation Over Finite and Infinite Words, Recognizability in residuated lattices, Reaching the minimum ideal in a finite semigroup, On the expressive power of temporal logic, Finite abundant semigroups in which the idempotents form a subsemigroup., The Boolean Formula Value Problem as Formal Language, Construction of a Deterministicω-Automaton Using Derivatives, A Survey on Difference Hierarchies of Regular Languages, Complexity Analysis: Transformation Monoids of Finite Automata, Characterization of the pseudovariety generated by finite monoids satisfying $\mathcal R=\mathcal H$., Glider automata on all transitive sofic shifts, The monoid of orientation-preserving $k$-extensive transformations, An aperiodicity problem for multiwords, On FO 2 Quantifier Alternation over Words, On uniformity within $NC^ 1$, Matrix versions of aperiodic $K$-rational identities, The syntactic monoid of hairpin-free languages, The monoid of all orientation-preserving and extensive full transformations on a finite chain, Well quasi-orders arising from finite ordered semigroups, Green's relations in finite transformation semigroups, A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II, Finite loops recognize exactly the regular open languages, A positive extension of Eilenberg's variety theorem for non-regular languages, Extensions of an idea of McNaughton, New results on the generalized star-height problem, Unnamed Item, On formations of monoids, Characterizing classes of regular languages using prefix codes of bounded synchronization delay, Regularity Conditions for Iterated Shuffle on Commutative Regular Languages, Tropical representations and identities of the stylic monoid, A natural partial order on partition order-decreasing transformation semigroups, Locally countable pseudovarieties, Face monoid actions and tropical hyperplane arrangements, Representation theory of order-related monoids of partial functions as locally trivial category algebras, Deciding whether a relation defined in Presburger logic can be defined in weaker logics, Efficiency of automata in semi-commutation verification techniques, On nilpotent subsemigroups of the order-preserving and decreasing transformation semigroups, A new algebraic invariant for weak equivalence of sofic subshifts, Hierarchies of Piecewise Testable Languages, Algebras for classifying regular tree languages and an application to frontier testability, Hierarchies and reducibilities on regular languages related to modulo counting, On the computational power of programs over $\mathsf{BA}_2$ monoid, Theme and Variations on the Concatenation Product, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages, ω♯-Algebras, A hierarchy of cyclic languages, Morphic refinements of nonregular languages, Varieties of Commutative Semigroups, The pseudovariety $J$ is hyperdecidable, On Rough Approximations of Languages under Infinite Index Indiscernibility Relations, The loop problem for Rees matrix semigroups., Membership of $\mathbf A\vee\mathbf G$ for classes of finite weakly abundant semigroups., The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, On semidirectly closed pseudovarieties of aperiodic semigroups, Actions, wreath products of $\mathcal C$-varieties and concatenation product., SC-hyperdecidability of $\mathbf R$, Unnamed Item, Free profinite locally idempotent and locally commutative semigroups, Krohn-Rhodes complexity pseudovarieties are not finitely based, Imre Simon: an exceptional graduate student, A Robust Class of Regular Languages, The Height of Factorization Forests, Implicit operations on finite ${\mathcal J}$-trivial semigroups and a conjecture of I. Simon, On the equation ${\mathbf V}*{\mathbf G}={\mathcal E}{\mathbf V}$, Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures, A sufficient condition to polynomially compute a minimum separating DFA, Learning in varieties of the form $\mathbf {V^{*}LI}$ from positive data, Unnamed Item, Semidirect product with an order-computable pseudovariety and tameness., An embedding of semigroups into regular semigroups that preserves structure and finiteness., The Shuffle Product: New Research Directions, On the index of Simon's congruence for piecewise testability, Circuit complexity and the expressive power of generalized first-order formulas, The structure of finite monoids satisfying the relation $\mathcal R=\mathcal H$., Representation theory of finite semigroups, semigroup radicals and formal language theory, Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG], On the pseudovariety generated by all finite monoids satisfying $\mathcal R=\mathcal H$., The Booleanization of an inverse semigroup, Representations of relatively free profinite semigroups, irreducibility, and order primitivity, Unnamed Item, Regular Languages Definable by Majority Quantifiers with Two Variables, Solution sets for equations over free groups are EDT0L languages, A Structure Preserving Embedding of Semigroups Into Regular Semigroups, Green's relations in deterministic finite automata, Unnamed Item, Operations on Weakly Recognizing Morphisms, Structural aspects of semigroups based on digraphs, One quantifier alternation in first-order logic with modular predicates, Geometrically closed positive varieties of languages, Syntactic structures of regular languages, Languages and formations generated by $D_4$ and $Q_8$, A hierarchy of shift equivalent sofic shifts, Positive varieties of tree languages, Fixed point generation of varieties of languages, Identities and bases in the hypoplactic monoid, Omega-rational expressions with bounded synchronization delay, Commutative images of rational languages and the Abelian kernel of a monoid, Regularity conditions for iterated shuffle on commutative regular languages, The commutative closure of shuffle languages over group languages is regular, State complexity of permutation and related decision problems on alphabetical pattern constraints