Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-19T10:19:19.495Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Influence of the State Encoding on OBDD-Representations of Finite State Machines

Published online by Cambridge University Press:  15 August 2002

Christoph Meinel  and
Thorsten Theobald
Christoph Meinel
Affiliation:
FB IV – Informatik, Universität Trier, 54286 Trier, Germany; [email protected].
Thorsten Theobald
Affiliation:
Zentrum Mathematik, TU München, 80290 München, Germany; [email protected].
Get access

Abstract

Ordered binary decision diagrams are an important data structure for the representation of Boolean functions. Typically, the underlying variable ordering is used as an optimization parameter. When finite state machines are represented by OBDDs the state encoding can be used as an additional optimization parameter. In this paper, we analyze the influence of the state encoding on the OBDD-representations of counter-type finite state machines. In particular, we prove lower bounds, derive exact sizes for important encodings and construct a worst-case encoding which leads to exponential-size OBDDs.

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 33 , Issue 1 , January 1999 , pp. 21 - 31
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A. Aziz, S. Taziran and R.K. Brayton, BDD variable ordering for interacting finite state machines, in Proc. 31st ACM/IEEE Design Automation Conference (San Diego, CA, 1994) 283-288.
J. Bern, Ch. Meinel and A. Slobodová, Global rebuilding of OBDDs - avoiding memory requirement maxima, in Proc. Computer-Aided Verification, Springer, Berlin, Lecture Notes in Computer Science 939 (1995) 4-15.
Bollig, B. and Wegener, I., Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Comput. 45 (1996) 993-1002. CrossRef
R.E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35 (1986) 677-691.
Bryant, R.E., Symbolic Boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys 24 (1992) 293-318. CrossRef
Burch, J.R., Clarke, E.M., Long, D.E., McMillan, K.L. and Dill, D.L., Symbolic model checking for sequential circuit verification. IEEE Trans. Computer-Aided Design of Integrated Circuits 13 (1994) 401-424. CrossRef
Coudert, O., Berthet, C. and Madre, J. C., Verification of synchronous sequential machines using symbolic execution, in Proc. Workshop on Automatic Verification Methods for Finite State Machines, Springer, Berlin, Lecture Notes in Computer Science 407 (1989) 365-373. CrossRef
Coudert, O. and Madre, J. C., The implicit set paradigm: a new approach to finite state system verification. Formal Methods in System Design 6 (1995) 133-145. CrossRef
A. Ghosh, S. Devadas and A. R. Newton, Sequential logic testing and verification, Kluwer Academic Publishers, Boston, MA (1992).
R.W. Hamming, Coding and information theory, Prentice-Hall, Englewood Cliffs, NJ (1980).
Ch. Meinel, A. Slobodová, On the complexity of constructing optimal ordered binary decision diagrams, in Proc. Mathematical Foundations in Computer Science, Springer, Berlin, Lecture Notes in Computer Science 841 (1994) 515-524. CrossRef
Ch. Meinel, F. Somenzi and T. Theobald, Linear sifting of decision diagrams, in Proc. 34th ACM/IEEE Design Automation Conference (Anaheim, CA, 1997) 202-207.
Ch. Meinel, T. Theobald, Local encoding transformations for optimizing OBDD-representations of finite state machines, in Proc. International Conference on Formal Methods in Computer-Aided Design (Palo Alto, CA), Springer, Berlin, Lecture Notes in Computer Science 1166 (1996) 404-418. CrossRef
R. Rudell, Dynamic variable ordering for ordered binary decision diagrams, in Proc. IEEE International Conference on Computer-Aided Design (Santa Clara, CA, 1993) 42-47.
Tani, S., Hamaguchi, K. and Yajima, S., The complexity of the optimal variable ordering problems of shared binary decision diagrams, in Proc. International Symposium on Algorithms and Computation, Springer, Berlin, Lecture Notes in Computer Science 762 (1993) 389-398. CrossRef
Wegener, I., Efficient data structures for Boolean functions. Discrete Math. 136 (1994) 347-372. CrossRef