A Theorem on Boolean Matrices

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Theorem on Boolean Matrices

Full text

Pdf (124 KB)

Source

Journal of the ACM (JACM) archive
Volume 9 , Issue 1 (January 1962) table of contents

Pages: 11 - 12

Year of Publication: 1962

ISSN:0004-5411

Author

Stephen Warshall

Computer Associates, Inc., Woburn, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 34, Downloads (12 Months): 224, Citation Count: 115

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321105.321107 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	PROSSER, REESE T. Applications of Boolean matrices to the analysis of flow diagrams. Proc. Eastern Joint Comput. Conf. No. 16 (1959), 133.
	2	Rosalind B. Marimont, A New Method of Checking the Consistency of Precedence Matrices, Journal of the ACM (JACM), v.6 n.2, p.164-171, April 1959 [doi>10.1145/320964.320973]

CITED BY 115

	Kenneth G. Salter, A methodology for decomposing system requirements into data processing requirements, Proceedings of the 2nd international conference on Software engineering, p.91-101, October 13-15, 1976, San Francisco, California, United States
	Donald B. Johnson , Samuel D. Kashdan, Lower Bounds for Selection in X + Y and Other Multisets, Journal of the ACM (JACM), v.25 n.4, p.556-570, Oct. 1978
	Saul Gorn, Mechanical languages: a course specification, Communications of the ACM, v.7 n.4, p.219-222, April 1964
	K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972
	Harold E. Livings , Udo W. Pooch, A heuristic teleprocessing network design technique, ACM SIGSIM Simulation Digest, v.7 n.4, p.71-76, July 1976
	R. Agrawal , H. V. Jagadish, Multiprocessor transitive closure algorithms, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.56-66, December 05-07, 1988, Austin, Texas, United States
	Martin Tompa, Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.333-338, April 28-30, 1980, Los Angeles, California, United States
	Jacques Cohen, Computer-aided micro-analysis of programs, Proceedings of the 4th international conference on Software engineering, p.79-84, September 17-19, 1979, Munich, Germany
	Dennis M. Moyles , Gerald L. Thompson, An Algorithm for Finding a Minimum Equivalent Graph of a Digraph, Journal of the ACM (JACM), v.16 n.3, p.455-460, July 1969
	Frank Mueller , David B. Whalley, Avoiding unconditional jumps by code replication, ACM SIGPLAN Notices, v.27 n.7, p.322-330, July 1992
	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977
	J. L. Baer, A Survey of Some Theoretical Aspects of Multiprocessing, ACM Computing Surveys (CSUR), v.5 n.1, p.31-80, March 1973
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	T. V. Griffiths , S. R. Petrick, On the relative efficiencies of context-free grammar, Communications of the ACM, v.8 n.5, p.289-300, May 1965
	Dennis Shasha , Tsong-Li Wang, New techniques for best-match retrieval, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.140-158, Apr. 1990
	Jeffrey D. Oldham, Combinatorial approximation algorithms for generalized flow problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.704-714, January 17-19, 1999, Baltimore, Maryland, United States
	Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974
	D. Neel , M. Amirchahy, Removal of invariant statements from nested-loops in a single effective compiler pass, ACM SIGPLAN Notices, v.10 n.3, p.87-96, March 1975
	Yannis Ioannidis , Raghu Ramakrishnan , Linda Winger, Transitive closure algorithms based on graph traversal, ACM Transactions on Database Systems (TODS), v.18 n.3, p.512-576, Sept. 1993
	Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991
	Jeffrey D. Ullman , Mihalis Yannakakis, The input/output complexity of transitive closure, ACM SIGMOD Record, v.19 n.2, p.44-53, Jun. 1990
	Håkan Jakobsson, Mixed-approach algorithms for transitive closure (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.199-205, May 29-31, 1991, Denver, Colorado, United States
	Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981
	Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972
	Alberto Martelli, A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph, Journal of the ACM (JACM), v.23 n.1, p.58-73, Jan. 1976
	Paul B. Schneck, A survey of compiler optimization techniques, Proceedings of the annual conference, p.106-113, August 27-29, 1973, Atlanta, Georgia, United States
	Mikhail J. Atallah , S. Rao Kosaraju, Graph Problems on a Mesh-Connected Processor Array, Journal of the ACM (JACM), v.31 n.3, p.649-667, July 1984
	Jiazhen Cai , Robert A. Paige, Look ma, no hashing, and no arrays neither, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.143-154, January 21-23, 1991, Orlando, Florida, United States
	Seppo Sippu , Eljas Soisalon-Soininen, A generalized transitive closure for relational queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.325-332, March 1988, Austin, Texas, United States
	Shaul Dar , Raghu Ramakrishnan, A performance study of transitive closure algorithms, ACM SIGMOD Record, v.23 n.2, p.454-465, June 1994
	David F. Martin, A Boolean matrix method for the computation of linear precedence functions, Communications of the ACM, v.15 n.6, p.448-454, June 1972
	Robert M. Keller, Look-Ahead Processors, ACM Computing Surveys (CSUR), v.7 n.4, p.177-195, Dec. 1975
	Sharon A. Stephens , Leonard L. Tripp, Requirements expression and verification aid, Proceedings of the 3rd international conference on Software engineering, p.101-108, May 10-12, 1978, Atlanta, Georgia, United States
	Jean-Francois Bergeretti , Bernard A. Carré, Information-flow and data-flow analysis of while-programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.37-61, Jan. 1985
	Alain Colmerauer, Total Precedence Relations, Journal of the ACM (JACM), v.17 n.1, p.14-30, Jan. 1970
	Zvi Weiss , Harry J. Saal, Compile time syntax analysis of APL programs, ACM SIGAPL APL Quote Quad, v.12 n.1, p.313-320, September 1981
	David F. Martin, Programming Languages: Boolean matrix methods for the detection of simple precedence grammars, Communications of the ACM, v.11 n.10, p.685-687, Oct. 1968
	J. M. S. Simões Pereira, On the Boolean Matrix Equation M^′=∨i=1Mⁱ , Journal of the ACM (JACM), v.12 n.3, p.376-382, July 1965
	Jacques Cohen, Computer-assisted microanalysis of programs, Communications of the ACM, v.25 n.10, p.724-733, Oct 1982
	Håkan Jakobsson, On tree-based techniques for query evaluation, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.380-392, June 02-05, 1992, San Diego, California, United States
	Mikhail J. Atallah , S. Rao Kosaraju, Graph problems on a mesh-connected processor array (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.345-353, May 05-07, 1982, San Francisco, California, United States
	Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Path queries for transportation networks: dynamic reordering and sliding window paging techniques, Proceedings of the 4th ACM international workshop on Advances in geographic information systems, p.9-16, November 1996, Rockville, Maryland, United States
	Susan L. Graham , Michael A. Harrison , Walter L. Ruzzo, On line context free language recognition in less than cubic time(Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.112-120, May 03-05, 1976, Hershey, Pennsylvania, United States
	P. J. Flynn, 3-D Object Recognition with Symmetric Models: Symmetry Extraction and Encoding, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.8, p.814-818, August 1994
	James R. Bell, A new method for determining linear precedence functions for precedence grammars, Communications of the ACM, v.12 n.10, p.567-569, Oct. 1969
	H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, ACM SIGMOD Record, v.16 n.3, p.331-344, Dec. 1987
	J. Banerjee, A DAG clustering algorithm for design configurations, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.444-451, December 1987, Dallas, Texas, United States
	Henry S. Warren, Jr., A modification of Warshall's algorithm for the transitive closure of binary relations, Communications of the ACM, v.18 n.4, p.218-220, April 1975
	Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990
	C. Duong-Kien , H.-J. Hoffman , D. Muth, A improvement to Martin's algorithm for computation of linear precedence functions, Communications of the ACM, v.19 n.10, p.576-577, Oct. 1976
	M. R. Garey , D. S. Johnson, Scheduling Tasks with Nonuniform Deadlines on Two Processors, Journal of the ACM (JACM), v.23 n.3, p.461-467, July 1976
	Yugyung Lee , James Geller, Efficient transitive closure reasoning in a combined class/part/containment hierarchy, Knowledge and Information Systems, v.4 n.3, p.305-328, July 2002
	David R. Cecil, Graphs and enhancing Maple multiplication, Mathematics and Computer Education, v.36 n.1, p.62-69, September 2002
	S. Ceri , G. Gottlob , L. Tanca, What You Always Wanted to Know About Datalog (And Never Dared to Ask), IEEE Transactions on Knowledge and Data Engineering, v.1 n.1, p.146-166, March 1989
	P. Cappello , Ö. Eğecioğlu , C. Scheiman, An introduction to processor-time-optimal systolic arrays, Highly parallel computaions: algorithms and applications, WIT Press, 001
	Litong Song , Krishna Kavi, What can we gain by unfolding loops?, ACM SIGPLAN Notices, v.39 n.2, February 2004
	R. K. Shyamasundar, A note on the transitive closure of a boolean matrix, ACM SIGACT News, v.9 n.4, p.18-21, Winter 1978
	Jean Hartmann , David J. Robson, Techniques for Selective Revalidation, IEEE Software, v.7 n.1, p.31-36, January 1990
	Wen-Ran Zhang , Lulu Zhang, Yin Yang bipolar logic and bipolar fuzzy logic, Information Sciences—Informatics and Computer Science: An International Journal, v.165 n.3-4, p.265-287, 19 October 2004
	G. N. Frederickson, A new approach to all pairs shortest paths in planar graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.19-28, January 1987, New York, New York, United States
	Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Direct transitive closure algorithms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.15 n.3, p.427-458, Sept. 1990
	Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States
	Harry T. Hsu, An Algorithm for Finding a Minimal Equivalent Graph of a Digraph, Journal of the ACM (JACM), v.22 n.1, p.11-16, Jan. 1975
	Dilip Sarkar , Amar Mukherjee, Design of Optimal Systolic Algorithms for the Transitive Closure Problem, IEEE Transactions on Computers, v.41 n.4, p.508-512, April 1992
	Sergiu Rudeanu , Dragoş Vaida, Semirings in operations research and computer science: more algebra, Fundamenta Informaticae, v.61 n.1, p.61-85, May 2004
	F.-C. Lin , I.-C. Wu, Broadcast Normalization in Systolic Design, IEEE Transactions on Computers, v.37 n.11, p.1428-1434, November 1988
	Mikkel Thorup, Worst-case update times for fully-dynamic all-pairs shortest paths, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Pentti A. Honkanen, Setting the foundations of computer science in a business oriented program, ACM SIGCSE Bulletin, v.7 n.1, p.187-190, February 1975
	C. J. Scheiman , P. R. Cappello, A Processor-Time-Minimal Systolic Array for Transitive Closure, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.257-269, May 1992
	Dirk Beyer , Andreas Noack , Claus Lewerentz, Efficient Relational Calculation for Software Analysis, IEEE Transactions on Software Engineering, v.31 n.2, p.137-149, February 2005
	Björn Lisper, Computing transitive closure on systolic arrays of fixed size, Distributed Computing, v.5 n.3, p.133-144, December 1991
	Xiaoyong Tang , Hai Zhou , Prith Banerjee, Leakage power optimization with dual-V_th library in high-level synthesis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Marco Aiello , Arnold M. W. Smeulders, Thick 2D relations for document understanding, Information Sciences—Informatics and Computer Science: An International Journal, v.167 n.1-4, p.147-176, 2 December 2004
	Leonid Khachiyan , Endre Boros , Konrad Borys , Khaled Elbassioni , Vladimir Gurvich, Generating all vertices of a polyhedron is hard, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.758-765, January 22-26, 2006, Miami, Florida
	Rezaul Alam Chowdhury , Vijaya Ramachandran, Cache-oblivious dynamic programming, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.591-600, January 22-26, 2006, Miami, Florida
	Alexandre Petrenko , Sergiy Boroday , Roland Groz, Confirming Configurations in EFSM Testing, IEEE Transactions on Software Engineering, v.30 n.1, p.29-42, January 2004
	Reinhard Schwarz , Friedemann Mattern, Detecting causal relationships in distributed computations: in search of the holy grail, Distributed Computing, v.7 n.3, p.149-174, March 1994
	Neil Kettle , Andy King, An anytime symmetry detection algorithm for ROBDDs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	U. Schwiegelshohn , L. Thiele, A Systolic Array for the Assignment Problem, IEEE Transactions on Computers, v.37 n.11, p.1422-1425, November 1988
	Jean Frédéric Myoupo , Anne Cécile Fabret, A Modular Systolic Linearization of the Warshall-Floyd Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.449-455, May 1996
	Gerald Penn, Efficient transitive closure of sparse matrices over closed semirings, Theoretical Computer Science, v.354 n.1, p.72-81, 21 March 2006
	Yangjun Chen , Donovan Cooke, On the transitive closure representation and adjustable compression, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Mehryar Mohri, Semiring frameworks and algorithms for shortest-distance problems, Journal of Automata, Languages and Combinatorics, v.7 n.3, p.321-350, January 2002
	A. Quirin , O. Cordón , J. Santamaría , B. Vargas-Quesada , F. Moya-Anegón, A new variant of the Pathfinder algorithm to generate large visual science maps in cubic time, Information Processing and Management: an International Journal, v.44 n.4, p.1611-1623, July, 2008
	Leonardo Bruno de Sá , Antonio Mesquita, Evolutionary synthesis of low-sensitivity equalizers using adjacency matrix representation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Yun-Wu Huang , Ning Jing , Elkea Rundensteiner, A Hierarchical Path View Model for Path Finding in Intelligent Transportation Systems, Geoinformatica, v.1 n.2, p.125-159, August 1997
	Joaquín Bautista , Elena Fernández , Jordi Pereira, Solving an urban waste collection problem using ants heuristics, Computers and Operations Research, v.35 n.9, p.3020-3033, September, 2008
	M. Gondran , M. Minoux, Dioïds and semirings: Links to fuzzy sets and other applications, Fuzzy Sets and Systems, v.158 n.12, p.1273-1294, June, 2007
	Shahar Cohen , Lior Rokach , Oded Maimon, Decision-tree instance-space decomposition with grouped gain-ratio, Information Sciences: an International Journal, v.177 n.17, p.3592-3612, September, 2007
	E. I. Milovanović , I. Ž Milovanović , M. P. Bekakos , I. N. Tselepis, Computing all-pairs shortest paths on a linear systolic array and hardware realization on a reprogrammable FPGA platform, The Journal of Supercomputing, v.40 n.1, p.49-66, April 2007
	Sylvia L. Osborn, Towards a universal relation interface, Proceedings of the fifth international conference on Very Large Data Bases, p.52-60, October 03-05, 1979, Rio de Janeiro, Brazil
	Rezaul Alam Chowdhury , Vijaya Ramachandran, The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Benjamin Doerr , Edda Happ , Christian Klein, Crossover can provably be useful in evolutionary computation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Ian C. Parmee , Dragan C. Cvetković , Andrew H. Watson , Christopher R. Bonham, Multiobjective Satisfaction within an Interactive Evolutionary Design Environment, Evolutionary Computation, v.8 n.2, p.197-222, June 2000
	Kai-Hsiang Yang , Kun-Yan Chiou , Hahn-Ming Lee , Jan-Ming Ho, Web Appearance Disambiguation of Personal Names Based on Network Motif, Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, p.386-389, December 18-22, 2006
	Erol Gelenbe , Georgia Sakellari , Maurizio D'arienzo, Admission of QoS aware users in a smart network, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.3 n.1, p.1-28, March 2008
	Yannis E. Ioannidis , Raghu Ramakrishnan, Efficient Transitive Closure Algorithms, Proceedings of the 14th International Conference on Very Large Data Bases, p.382-394, August 29-September 01, 1988
	Rakesh Agrawal , H. V. Jagadish, Direct Algorithms for Computing the Transitive Closure of Database Relations, Proceedings of the 13th International Conference on Very Large Data Bases, p.255-266, September 01-04, 1987
	Rakesh Agrawal , H. V. Jagadish, Hybrid Transitive Closure Algorithms, Proceedings of the 16th International Conference on Very Large Data Bases, p.326-334, August 13-16, 1990
	Jason Tsong-Li Wang , Dennis Shasha, Query Processing for Distance Metrics, Proceedings of the 16th International Conference on Very Large Data Bases, p.602-613, August 13-16, 1990
	Pierre Girodias , Eduard Cerny, Interface Timing Verification with Delay Correlation Using Constraint Logic Programming, Proceedings of the 1997 European conference on Design and Test, p.12, March 17-20, 1997
	Michael Philippsen , Ernst A. Heinz , Paul Lukowicz, Compiling machine-independent parallel programs, ACM SIGPLAN Notices, v.28 n.8, p.99-108, Aug. 1993
	Sascha Häckel , Marco Fischer , David Zechel , Tobias Teich, A multi-objective ant colony approach for pareto-optimization using dynamic programming, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Paritosh Shroff , Scott F. Smith , Mark Thober, Securing information flow via dynamic capture of dependencies, Journal of Computer Security, v.16 n.5, p.637-688, November 2008
	Yangjun Chen, A new method for generating compressed representation of transitive closure, Proceedings of the 2008 C³S²E conference, May 12-13, 2008, Montreal, Quebec, Canada
	Gary J. Katz , Joseph T. Kider, Jr, All-pairs shortest-paths for large graphs on the GPU, Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, June 20-21, 2008, Sarajevo, Bosnia and Herzegovina
	Saddek Bensalem , Doron Peled , Hongyang Qu , Stavros Tripakis, Automatic generation of path conditions for concurrent timed systems, Theoretical Computer Science, v.404 n.3, p.275-292, September, 2008
	J. F. Nunamaker, Jr., A methodology for the design and optimization of information processing systems, Proceedings of the May 18-20, 1971, spring joint computer conference, May 18-20, 1971, Atlantic City, New Jersey
	E. M. Reingold, Establishing lower bounds on algorithms: a survey, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	Anders Søgaard , Martin Lange, Polyadic Dynamic Logics for HPSG Parsing, Journal of Logic, Language and Information, v.18 n.2, p.159-198, April 2009
	Shi-Ming Huang , Chih-Fong Tsai , Po-Chun Huang, Component-based software version management based on a Component-Interface Dependency Matrix, Journal of Systems and Software, v.82 n.3, p.382-399, March, 2009
	Martin Beaudry , Markus Holzer, The Complexity of Tensor Circuit Evaluation, Computational Complexity, v.16 n.1, p.60-111, May 2007
	Yangjun Chen, General spanning trees and reachability query evaluation, Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering, May 19-21, 2009, Montreal, Quebec, Canada
	Jana Koehler , Jörg Hoffmann, On reasonable and forced goal orderings and their use in an agenda-driven planning algorithm, Journal of Artificial Intelligence Research, v.12 n.1, p.339-386, February 2000
	Xiaobin Wang , Hong Qu , Zhang Yi, A modified pulse coupled neural network for shortest-path problem, Neurocomputing, v.72 n.13-15, p.3028-3033, August, 2009