Abstract
Simultaneous realizations are defined as the evaluation of a boolean function on several input tuples at the same time. For the corresponding Shannon functions one can show that a relatively large number of simultaneous inputs is compatible with a small enhancement of size and depth. These realizations can be applied to various computational tasks, e.g. to the design of fault-tolerant systems, the point-inclusion problem of binary images, and the simultaneous memory access.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
5. Literature
Ajtai, M., J. Komlos, and E. Szemeredi: Sorting in c-log(n) Parallel Steps. Combinatorica 3(1983)1, 1–19.
Albrecht, A.: On Hardware Algorithms for Geometrical Computation Problems. — In: Proc. 10th IFIP Computer Congress, Dublin 1986, 989–994.
Edelsbrunner, H.: On Key Problems and Key Methods in Computational Geometry. Proc. STACS, Paris 1984.
Fischer, M.J., and F. Galbiati: On the Complexity of 2-output Boolean Networks. Theor. Comp. Science (1981), 177–185.
Haverlik, I.: On the Synthesis of Circuits for Matrices with a Defined Number of Corner Elements. Banach Centre Publ. 7(1982), 177–195 (in Russian).
Leighton, F.T.: New Lower Bound Techniques for VLSI. — In: Proc. 22nd FOCS, 1981, 1–9.
Lupanov, O.B.: On the Synthesis of some Classes of Control Systems. Probl. of Cybernetics 10(1963), 63–97 (in Russian).
Paul, W.: Realizing Boolean Functions on Disjoint Sets of Variables. Theor. Comp. Science (1976), 383–396.
Uhlig, D.: On the Synthesis of Self-Correcting Circuits with a Small Number of Reliable Elements. Mathem. Notes 15(1974)6, 937–944 (in Russian).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Albrecht, A. (1989). On simultaneous realizations of boolean functions, with applications. In: Wolf, G., Legendi, T., Schendel, U. (eds) Parcella '88. Parcella 1988. Lecture Notes in Computer Science, vol 342. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-50647-0_102
Download citation
DOI: https://doi.org/10.1007/3-540-50647-0_102
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-50647-8
Online ISBN: 978-3-540-46062-6
eBook Packages: Springer Book Archive