Algebraic decision procedures for local testability

DOI10.1007/BF01761708zbMATH Open0287.02022MaRDI QIDQ4773689FDOQ4773689

Authors: Robert McNaughton 

Publication date: 1974

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

Mathematics Subject Classification ID

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

Cites Work

• Characterizations of locally testable events
• The Theory of Definite Automata
• Locally testable semigroups
• Locally testable languages

Cited In (58)

• La finitude des représentations linéaires des semi-groupes est decidable
• Hierarchies and reducibilities on regular languages related to modulo counting
• Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
• On generalized locally testable languages
• A Note on Decidable Separability by Piecewise Testable Languages
• Languages and scanners
• Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words)
• Strongly locally testable semigroups with commuting idempotents and related languages
• Grammatical inference of directed acyclic graph languages with polynomial time complexity
• \(NC^ 1\): The automata-theoretic viewpoint
• Tameness of joins involving the pseudovariety of local semilattices.
• TAMENESS OF THE PSEUDOVARIETY LS1
• Products of languages with counter
• Inclusion relations between some congruences related to the dot-depth hierarchy
• Biinfinite words with maximal recurrent unbordered factors.
• Families of locally testable languages
• Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts.
• The varieties of n-testable semigroups
• Local testability from words to traces, a suitable definition
• Free profinite \(\mathcal R\)-trivial, locally idempotent and locally commutative semigroups
• Expressive power of existential first-order sentences of Büchi's sequential calculus
• Left and right negatively orderable semigroups and a one-sided version of Simon's theorem
• Over testable languages
• The product of rational languages
• Learning \((k,l)\)-contextual tree languages for information extraction from web pages
• Group-complexity and reversals of finite semigroups
• String assembling systems: comparison to sticker systems and decidability
• Free profinite locally idempotent and locally commutative semigroups
• Properties of code events and homomorphisms over regular events
• Semigroups and languages of dot-depth two
• On stateless two-pushdown automata and restarting automata
• Games, equations and the dot-depth hierarchy
• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
• Measuring power of locally testable languages
• Logic, semigroups and automata on words
• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
• An efficient algorithm for local testability problem of finite state automata
• Locally testable semigroups
• Title not available (Why is that?)
• Finite semigroup varieties of the form V*D
• LANGAGE: A Maple package for automaton characterization of regular languages
• Locally testable languages
• GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• The Burnside problem for semigroups
• Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices
• On bases of identities for the \(\omega\)-variety generated by locally testable semigroups.
• On the descriptional complexity of stateless deterministic ordered restarting automata
• Languages of dot-depth 3/2
• The covering problem
• On some decision problems for stateless deterministic ordered restarting automata
• The expressivity of autosegmental grammars
• The Karoubi envelope of the mirage of a subshift
• Right and left locally testable languages
• Relativized adjacency
• Locality and Centrality: The Variety ZG
• The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin
• Measuring power of generalised definite languages

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4773689)