Locally testable languages

DOI10.1016/S0022-0000(72)80020-5zbMath0242.68038MaRDI QIDQ2554236

Yechezkel Zalcstein

Publication date: 1972

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Regulated variants of limited context restarting automata ⋮ Bilateral locally testable languages. ⋮ Strongly locally testable semigroups with commuting idempotents and related languages ⋮ Upper Bounds on Mixing Time of Finite Markov Chains ⋮ Over testable languages ⋮ 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) ⋮ Measuring power of locally testable languages ⋮ The varieties of n-testable semigroups ⋮ Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts. ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ An efficient algorithm for local testability problem of finite state automata ⋮ Series formelles et algèbres syntactiques ⋮ Measuring power of generalised definite languages ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ Recognizing malicious software behaviors with tree automata inference ⋮ Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order ⋮ On the acceptance power of regular languages ⋮ Group-complexity and reversals of finite semigroups ⋮ The Karoubi envelope of the mirage of a subshift ⋮ SYSTEM IDENTIFICATION, APPROXIMATION AND COMPLEXITY ⋮ Two-Sided Strictly Locally Testable Languages ⋮ Smoothing and compression with stochastic \(k\)-testable tree languages ⋮ The Burnside problem for semigroups ⋮ Locally testable semigroups ⋮ Free profinite locally idempotent and locally commutative semigroups ⋮ Determination of finite automata accepting subregular languages ⋮ Unnamed Item ⋮ ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA ⋮ 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 ⋮ Classes of formal grammars ⋮ Unnamed Item ⋮ Identities of locally testable semigroups ⋮ Characterizations of locally testable events ⋮ Families of locally testable languages ⋮ Optimal estimation on the order of local testability of finite automata ⋮ 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 ⋮ Algebraic decision procedures for local testability

Cites Work

• Locally testable semigroups
• Generalized sequential machine maps
• Methods of the algebraic theory of machines. I: Decomposition theorem for generalized machines; properties preserved under series and parallel compositions of machines
• Decomposition and complexity of finite semigroups
• Characterizations of locally testable events
• Algebraic decision procedures for local testability
• On finite monoids having only trivial subgroups
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• Lower Bound of the Number of Threshold Functions
• The Theory of Definite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item