Introduction to Circuits, II

Yatsuka Nakamura

Shinshu University, Nagano

Piotr Rudnicki

University of Alberta, Edmonton

Andrzej Trybulec

Warsaw University, Bialystok

Pauline N. Kawamoto

Shinshu University, Nagano

Summary.

This article is the last in a series of four articles (preceded by [22], [23], [21]) about modelling circuits by many sorted algebras.\par The notion of a circuit computation is defined as a sequence of circuit states. For a state of a circuit the next state is given by executing operations at circuit vertices in the current state, according to denotations of the operations. The values at input vertices at each state of a computation are provided by an external sequence of input values. The process of how input values propagate through a circuit is described in terms of a homomorphism of the free envelope algebra of the circuit into itself. We prove that every computation of a circuit over a finite monotonic signature and with constant input values stabilizes after executing the number of steps equal to the depth of the circuit.

Partial funding for this work has been provided by: Shinshu Endowment Fund for Information Science, NSERC Grant OGP9207, JSTF award 651-93-S009.

MML Identifier: CIRCUIT2

Contents (PDF format)

1. Circuit Inputs
2. Circuit Computations

Bibliography

[1] Grzegorz Bancerek. Cardinal numbers. Journal of Formalized Mathematics, 1, 1989.

[2] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.

[3] Grzegorz Bancerek. K\"onig's theorem. Journal of Formalized Mathematics, 2, 1990.

[4] Grzegorz Bancerek. Cartesian product of functions. Journal of Formalized Mathematics, 3, 1991.

[5] Grzegorz Bancerek. K\"onig's Lemma. Journal of Formalized Mathematics, 3, 1991.

[6] Grzegorz Bancerek. Sets and functions of trees and joining operations of trees. Journal of Formalized Mathematics, 4, 1992.

[7] Grzegorz Bancerek. Joining of decorated trees. Journal of Formalized Mathematics, 5, 1993.

[8] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.

[9] Grzegorz Bancerek and Piotr Rudnicki. On defining functions on trees. Journal of Formalized Mathematics, 5, 1993.

[10] Ewa Burakowska. Subalgebras of many sorted algebra. Lattice of subalgebras. Journal of Formalized Mathematics, 6, 1994.

[11] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[12] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.

[13] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.

[14] Czeslaw Bylinski. The modification of a function by a function and the iteration of the composition of a function. Journal of Formalized Mathematics, 2, 1990.

[15] Patricia L. Carlson and Grzegorz Bancerek. Context-free grammar --- part I. Journal of Formalized Mathematics, 4, 1992.

[16] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.

[17] Malgorzata Korolkiewicz. Homomorphisms of many sorted algebras. Journal of Formalized Mathematics, 6, 1994.

[18] Jaroslaw Kotowicz. Monotone real sequences. Subsequences. Journal of Formalized Mathematics, 1, 1989.

[19] Beata Madras. Product of family of universal algebras. Journal of Formalized Mathematics, 5, 1993.

[20] Beata Madras. Products of many sorted algebras. Journal of Formalized Mathematics, 6, 1994.

[21] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Introduction to circuits, I. Journal of Formalized Mathematics, 6, 1994.

[22] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, I. Journal of Formalized Mathematics, 6, 1994.

[23] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, II. Journal of Formalized Mathematics, 6, 1994.

[24] Beata Perkowska. Free many sorted universal algebra. Journal of Formalized Mathematics, 6, 1994.

[25] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.

[26] Andrzej Trybulec. Many-sorted sets. Journal of Formalized Mathematics, 5, 1993.

[27] Andrzej Trybulec. Many sorted algebras. Journal of Formalized Mathematics, 6, 1994.

[28] Andrzej Trybulec. On the sets inhabited by numbers. Journal of Formalized Mathematics, 15, 2003.

[29] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.

[30] Wojciech A. Trybulec. Groups. Journal of Formalized Mathematics, 2, 1990.

[31] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.

[32] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.

[33] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.