Accession Number : AD0722093

Title :   Locally Testable Events and Semigroups,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Zalcstein,Yechezkel

Report Date : MAR 1971

Pagination or Media Count : 25

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)

Descriptors :   (*GROUPS(MATHEMATICS), THEOREMS), COMBINATORIAL ANALYSIS, SET THEORY, MONOIDS, AUTOMATA

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE