Computation times for finite groups, semigroups and automata
- 1 January 1967
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 291-295
- https://doi.org/10.1109/focs.1967.9
Abstract
In this paper two closely related problems in automata theory are considered: 1) What is the time required for a network of elements, each with a limited number of inputs, to compute a finite function? 2) What is the time required for a finite automaton, realized as such a network, to compute its output function? Winograd has considered the first problem, especially for addition and group multiplication [1] and numerical multiplication [2]. By laying bare the methodology implicit in his work, we form a basis upon which we can erect a thoroughgoing analysis of multiplication in groups and semigroups and also can analyze computation of various finite functions. This paper presents the beginning of such an analysis.Keywords
This publication has 1 reference indexed in Scilit:
- On the Time Required to Perform AdditionJournal of the ACM, 1965