Locally Testable Events and Semigroups,

Abstract

It is an open problem, posed by Papert and McNaughton (1970), to find an algorithm for determining whether a regular event is locally testable. In this paper, the author presents a partial solution. First, one characterizes locally testable events algebraically in terms of their semigroups. Then one finds an effective necessary condition for local testability and proves that it is also sufficient for a large class of finite semigroups including all finite regular semigroups. This conjectured that the condition is necessary and sufficient for all regular events. (Author)

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1971
Accession Number
AD0722093

Entities

People

  • Yechezkel Zalcstein

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Mathematical Modeling and Probability Theory.