Algebraic decision procedures for local testability

DOI10.1007/BF01761708zbMath0287.02022MaRDI QIDQ4773689

Publication date: 1974

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (58)

Strongly locally testable semigroups with commuting idempotents and related languages ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Over testable languages ⋮ Left and right negatively orderable semigroups and a one-sided version of Simon's theorem ⋮ String assembling systems: comparison to sticker systems and decidability ⋮ Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words) ⋮ 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. ⋮ Inclusion relations between some congruences related to the dot-depth hierarchy ⋮ Unnamed Item ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ 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. ⋮ Measuring power of generalised definite languages ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE ⋮ Products of languages with counter ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ The product of rational languages ⋮ Languages and scanners ⋮ Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups ⋮ On bases of identities for the \(\omega\)-variety generated by locally testable semigroups. ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ The expressivity of autosegmental grammars ⋮ TAMENESS OF JOINS INVOLVING THE PSEUDOVARIETY OF LOCAL SEMILATTICES ⋮ Grammatical inference of directed acyclic graph languages with polynomial time complexity ⋮ Group-complexity and reversals of finite semigroups ⋮ The Karoubi envelope of the mirage of a subshift ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ Languages of dot-depth 3/2 ⋮ TAMENESS OF THE PSEUDOVARIETY LS1 ⋮ The Burnside problem for semigroups ⋮ Locally testable 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 ⋮ The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin ⋮ ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA ⋮ Properties of code events and homomorphisms over regular events ⋮ Local testability from words to traces, a suitable definition ⋮ La finitude des représentations linéaires des semi-groupes est decidable ⋮ Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices ⋮ Unnamed Item ⋮ Learning \((k,l)\)-contextual tree languages for information extraction from web pages ⋮ Logic, semigroups and automata on words ⋮ On generalized locally testable languages ⋮ Games, equations and the dot-depth hierarchy ⋮ Locally testable languages ⋮ Families of locally testable languages ⋮ LANGAGE: A Maple package for automaton characterization of regular languages ⋮ Free profinite \(\mathcal R\)-trivial, locally idempotent and locally commutative semigroups ⋮ On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata ⋮ Right and left locally testable languages ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata

Cites Work

This page was built for publication: Algebraic decision procedures for local testability