On Properties of Kleene TDDs

1 Citations 17 References
  • IGUCHI Yukihiro
    the Department of Computer Science, Meiji University
  • SASAO Tsutomu
    the Department of Computer Science and Electronics, Kyushu Institute of Technology
  • NATSUURA Munehiro
    the Department of Computer Science and Electronics, Kyushu Institute of Technology

Search this article

Description

Three types of ternary decision diagrams(TDDs)are considered:AND_TDDs, EXOR_TDDs, and Kleene_TDDs. Kleene_TDDs are useful for logic simulation in the presence of unknown inputs. Let N(BDD:f), N(AND_TDD:f), and N(EXOR_TDD:f)be the number of non-terminal nodes in the BDD, the AND_TDD, and the EXOR_TDD for f, respectively. Let N(Kleene_TDD:F)be the number of non-terminal nodes in the Kleene_TDD for F, where F is the regular ternary function corresponding to f. Then N(BDD:f)≦N(TDD:f). For parity functions, N(BDD:f)=N(AND_TDD:f)=N(EXOR_TDD:f)=N(Kleene_TDD:F). For unate functions, N(BDD:f)=N(AND_TDD:f). The sizes of Kleene_TDDs are O(3^n/n), and O(n^3)for arbitrary functions, and symmetric functions, respectively. There exist a 2n-variable function, where Kleene_TDDs require O(n)nodes with the best order, while O(3^n)nodes in the worst order.

Journal

  • IEICE Trans. INF. & SYST

    IEICE Trans. INF. & SYST 81 (7), 716-723, 1998-07-25

    The Institute of Electronics, Information and Communication Engineers

Citations (1)*help

See more

References(17)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1570854177489035904
  • NII Article ID
    110003219785
  • NII Book ID
    AA10826272
  • ISSN
    09168532
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top