Browse Prior Art Database

Characterizations of Linear Iterative Arrays

IP.com Disclosure Number: IPCOM000128571D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 17 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

Characterizations of linear iterative arrays (IdA's) in terms at sequential machines and systolic trellis automata are presented. The sequential machine characterizations are very convenient and powerful tools !or programming the IdA's and investigating their computational complexity. New results are obtained, some of which improve previously known results.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Characterizations of Linear Iterative Arrays

By

Oscar H. Ibarra and Sam M. Kim

Computer Science Department

Institute of Technology

136 Lind Hall University of Minnesota

Minneapolis, Minnesota 55455 ,.

Technical Report 83-20 December 1983

Abstract

Characterizations of linear iterative arrays (IdA's) in terms at sequential machines and systolic trellis automata are presented. The sequential machine characterizations are very convenient and powerful tools !or programming the IdA's and investigating their computational complexity. New results are obtained, some of which improve previously known results.

1. Introduction

Although it has been quite a while since linear iterative arrays (L1A's) were intro-duced, they have recently taken on renewed significance with the advent of VLSI tech-nology. LIA's, also called cellular automata, have been studied as models of parallel .computation, primarily for parallel pattern or language recognition [2-3,6-7;10-161. The LIA's studied in the literature are of three basic types: two-way L3A's with parallel input modes (2PIA's) (e.g., [14]), two-way LIA's with serial input modes (2SIA's)(e.g., [2]) and one-way LIA's with parallel input modes (iPIA's) (e.g., [0]). There are a number, of important questions concerning the computational complexities of the LIA's as well as the relationships between the different types, some of which will be answered here. In this paper we present, for the first time, characterizations of LIA's in terms of sequential machines and also in terms of variants of systolic trellis automata. The sequen-tial machines are variations of a machine called S'i'M which was introduced in (a]. A sys-tolic trellis automaton (TA) is a simple, but powerfuhmodal of a systolic array system. M's were shown to be equivalent to TA's in (9J. We characterize the three models above as well as other variations, including, e.g., one-way LIA's with sequential input modes (ISIA's) and one-way LIA's with simultaneous space and time bound. The characterizing sequential machines are relatively easy to program, and the conversion from an LIA to a sequential device (and vice versa) is also quite direct. Thus, the sequential machines can be used as (powerful) tools for investigating LIA's. For exam-ple, using the characterizations, we are able to prove a speed-up theorem for the LIA's which is stronger than those shown in the literature. The characterizations also allow us to compare the computation power of the different types of LIA's easily. For exam-

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 17

Characterizations of Linear Iterative Arrays

ple, we show that if L Is accepted by a real-space bounded 2PiA (real-space means that the number of nodes is equal to the length of the input) in n+R(n) time, then it is accepted by a real- space bounded ASIA in 2n-rR(n) time. This is a better result than that which was previously shown in [i...