A sub-quadratic algorithm for conjunctive and disjunctive BESs

J.F. Groote, M.K. Keinänen

Research output: Book/ReportReportAcademic

33 Downloads (Pure)

Abstract

We present an algorithm for conjunctive and disjunctive Boolean equation systems (BESs), which arise frequently in the verification and analysis of finite state concurrent systems. In contrast to the previously best known O(e^2) time solutions, our algorithm computes the solution of such a fixpoint equation system with size e and alternation depth d in O(e log d) time.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages8
Publication statusPublished - 2004

Publication series

NameComputer science reports
Volume0413
ISSN (Print)0926-4515

Cite this