Characterizations of locally testable events

DOI10.1016/S0012-365X(73)80005-6zbMath0255.94032OpenAlexW2081443805MaRDI QIDQ2558849

Publication date: 1973

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(73)80005-6

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Bilateral locally testable languages., Equations on the semidirect product of a finite semilattice by a finite commutative monoid, Unnamed Item, Conjugacy languages in groups, ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS, PROFINITE METHODS IN SEMIGROUP THEORY, LOCAL GROUPS IN FREE GROUPOIDS SATISFYING CERTAIN MONOID IDENTITIES, Strongly locally testable semigroups with commuting idempotents and related languages, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, A property of the Schützenberger product, Canonical finite models of Kleene algebra with tests, Over testable languages, Left and right negatively orderable semigroups and a one-sided version of Simon's theorem, A characterization of constant-time cellular automata computation, Graph congruences and pair testing, Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words), Polynomial closure and unambiguous product, Semigroups and languages of dot-depth two, Measuring power of locally testable languages, The varieties of n-testable semigroups, Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts., Varieties of finite categories, Profinite categories and semidirect products, Inverse monoids of dot-depth two, Unnamed Item, Equations on the semidirect product of a finite semilattice by a $\mathcal {J}$-trivial monoid of height $k$, Relativized adjacency, Locality and Centrality: The Variety ZG, An efficient algorithm for local testability problem of finite state automata, Biinfinite words with maximal recurrent unbordered factors., Finite semigroups, feedback, and the Letichevsky criteria on non-empty words in finite automata., Simulation by Rounds of Letter-to-Letter Transducers, Measuring power of generalised definite languages, Efficiency of automata in semi-commutation verification techniques, GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE, Products of languages with counter, A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS, Classifying regular events in symbolic logic, The product of rational languages, Languages and scanners, Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups, Catégories et langages de dot-depth un, On bases of identities for the $\omega$-variety generated by locally testable semigroups., Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order, On the acceptance power of regular languages, TAMENESS OF JOINS INVOLVING THE PSEUDOVARIETY OF LOCAL SEMILATTICES, BRET TILSON: HIS LIFE AND WORK, A STRUCTURAL APPROACH TO THE LOCALITY OF PSEUDOVARIETIES OF THE FORM LH ⓜ V, Reversible Regular Languages: Logical and Algebraic Characterisations, Group-complexity and reversals of finite semigroups, The Karoubi envelope of the mirage of a subshift, ON FREE SPECTRA OF VARIETIES OF LOCALLY THRESHOLD TESTABLE SEMIGROUPS, $NC^ 1$: The automata-theoretic viewpoint, On a conjecture concerning dot-depth two languages, Games, equations and dot-depth two monoids, Equations and dot-depth one, THE GLOBALS OF SOME SUBPSEUDOVARIETIES OF $\mathsf{DA}$, TAMENESS OF THE PSEUDOVARIETY LS1, A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL, SOME OPERATORS THAT PRESERVE THE LOCALITY OF A PSEUDOVARIETY OF SEMIGROUPS, Reducing the time complexity of testing for local threshold testability, The Burnside problem for semigroups, Finite semigroup varieties of the form V*D, Expressive power of existential first-order sentences of Büchi's sequential calculus, Free profinite locally idempotent and locally commutative semigroups, Determination of finite automata accepting subregular languages, THE GLOBALS OF SOME SUBPSEUDOVARIETIES OF $\mathsf{DA}$, The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin, Categories as algebra: An essential ingredient in the theory of monoids, A generalization of finiteness, Properties of code events and homomorphisms over regular events, Learning in varieties of the form $\mathbf {V^{*}LI}$ from positive data, Local testability from words to traces, a suitable definition, La finitude des représentations linéaires des semi-groupes est decidable, Classes of formal grammars, Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices, Unnamed Item, Identities of locally testable semigroups, Semidirect products of pseudovarieties from the universal algebraist's point of view, Logic, semigroups and automata on words, ON FREE SPECTRA OF LOCALLY TESTABLE SEMIGROUP VARIETIES, On generalized locally testable languages, Games, equations and the dot-depth hierarchy, Locally testable languages, Families of locally testable languages, Programs over semigroups of dot-depth one, Optimal estimation on the order of local testability of finite automata, LANGAGE: A Maple package for automaton characterization of regular languages, Sur une propriété d'itération des langages algébriques déterministes, Free profinite $\mathcal R$-trivial, locally idempotent and locally commutative semigroups, On semidirect products of two finite semilattices, Right and left locally testable languages, Mutation systems, Commutative regular languages with product-form minimal automata, State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Algebraic decision procedures for local testability, Free Burnside Semigroups

Cites Work