Zhe Dang


Associate Professor
School of Electrical Engineering and Computer Science
Washington State University
Pullman, WA 99164
Email: zdang@eecs.wsu.edu
Phone: 509-335-7238


Research Interests

  • Model-checking and testing for infinite-state and/or real-time systems
  • Automata theory and Membrane computing systems (P systems)

  • [PDF]

    Education

    PhD Dissertation: Debugging and Verification of Infinite State Real-time Systems
    Department of Computer Science
    University of California at Santa Barbara
    June, 2000
    Committee: Richard A. Kemmerer (Advisor), Tevfik Bultan (Co-advisor), Oscar H. Ibarra (Member)


    MS Thesis: Using the ASTRAL Model Checker for Cryptographic Protocol Analysis
    Department of Computer Science
    University of California at Santa Barbara
    January, 1998
    Committee: Richard A. Kemmerer (Advisor), Divyakant Agrawal (Member), Alan G. Konheim (Member)


    Teaching


    Cpt S 260: Introduction to computer architecture (Spring 2014)
    Cpt S 516: Algorithmics (Spring 2014)




    Grant

    NSF grant, Oscar Ibarra (CCF-0430945) and Zhe Dang (CCF-0430531), Collaborative Research: New automata theories for analyzing infinite state and membrane computing systems ($250K, Aug. 1, 2004 -- July 31, 2007)


    Award

    ``CEA Young Faculty Recognition", College of Engineering and Architecture (CEA), Washington State University, 2005.


    Program Committee

    Eighth International Conference on Implementation and Application of Automata (CIAA 2003)

    Tenth International Conference on Development in Language Theory (DLT 2006)

    PhD Students

  • Gaoyan Xie (January 2002 to July 2005). Current position: Tenure-track Assistant Professor of Computer Science, University of Massachusetts at Dartmouth.

    PhD Dissertation: Fundamental Studies on Automatic Verification of Component-based Systems -- A Decompositional and Hybrid Approach, July, 2005
    Committee: Zhe Dang (Advisor), Anneliese Andrews (Member), Curtis Dyreson (Member)


  • Cheng Li (MS since 2001, PhD since January 2003). Currently with Motorola.


  • Yong Wang Currently with Google.
    PhD Dissertation: Clustering, Grouping and Processes over Networks, December, 2007
    Committee: Zhe Dang (co-Advisor), Min Sik Kim (co-Advisor), K C Wang (Member)


  • Linmin Yang Currently with Amazon.
    PhD Dissertation: Entropy and Software Systems -- towards an Information-theoretic Foundation of Software Testing, April, 2011
    Committee: Zhe Dang (co-Advisor), Tom Fischer (co-Advisor), Min Sik Kim (Member)


  • Eric Wang (since August 2009). Continuing.


  • Cewei Cui (MS since 2010, PhD since August 2011). Continuing.




  • Dmitry Dementyev (PhD since August 2011). Continuing.




  • William Hutton (PhD since August 2013). Continuing.




  • Publications


      **********Papers in Review*********





    1. Cewei Cui, Zhe Dang, Thomas R. Fischer, and Oscar H. Ibarra
    2. [PDF]
      Information rate of some classes of nonregular languages: an automata-theoretic approach
      submitted.



    3. Zhe Dang, Oscar Ibarra and Qin Li.
    4. [PDF]
      Sampling a Two-way Finite Automaton,
      submitted.



    5. Qin Li, Qin-Kai Zeng and Zhe Dang.
    6. [PDF]
      A path sensitive type system for information flow,
      submitted.



    7. Oscar H. Ibarra, Cewei Cui, Zhe Dang, and Thomas R. Fischer
    8. [PDF]
      Lossiness of .communication channels modeled by transducers,
      CiE (Computability in Europe), Lecture Notes in Computer Science, Springer, 2014 (to appear).



    9. Qin Li and Zhe Dang
    10. [PDF]
      Sampling Automata and Programs.
      submitted (minor revision sent).



    11. Cewei Cui, Zhe Dang, Thomas R. Fischer, and Oscar H. Ibarra
    12. [PDF]
      Execution Information Rate for Some Classes of Automata.
      (journal version of the LATA 2013 paper), submitted.



    13. Cewei Cui, Zhe Dang, and Thomas R. Fischer
    14. [PDF]
      Bit rate of programs.
      submitted.



    15. Cewei Cui, Zhe Dang, Thomas R. Fischer, and Oscar H. Ibarra
    16. [PDF]
      Similarity in Languages and Programs.
      Theoretical Computer Science, 498: 58--75 (2013).



    17. Cewei Cui, Zhe Dang, Thomas R. Fischer, and Oscar H. Ibarra
    18. [PDF]
      Execution Information Rate for Some Classes of Automata.
      LATA 2013, Lecture Notes in Computer Science vol 7810, pp. 226--237, Springer.



    19. Eric Wang, Cewei Cui, Zhe Dang, Thomas R. Fischer, and Linmin Yang.
    20. [PDF]
      Zero-knowledge blackbox testing: where are the faults?
      International Journal of Foundations of Computer Science (to appear).



    21. Linmin Yang, Cewei Cui, Zhe Dang, and Thomas R. Fischer
    22. [PDF]
      An Information-theoretic Complexity Metric
      submitted.

      **********Edited Book (Proceedings)*********


    23. Oscar H. Ibarra and Zhe Dang (Eds.).
    24. Developments in Language Theory
      Lecture Notes in Computer Science Vol. 4036, Springer 2006.



    25. Oscar H. Ibarra and Zhe Dang (Eds.).
    26. [Springer Link]
      Implementation and Application of Automata.
      Lecture Notes in Computer Science Vol. 2759, Springer 2003.


      **********Journal Papers*********


    27. Cewei Cui, Zhe Dang, and Thomas R. Fischer
    28. [PDF]
      Typical Paths of a Graph
      Fundamenta Informaticae (accepted), 2011.



    29. Linmin Yang, Zhe Dang, and Thomas R. Fischer
    30. [PDF]
      Information Gain of Blackbox Testing
      Formal Aspects of Computing (accepted), 2011



    31. Linmin Yang, Yong Wang, and Zhe Dang
    32. [PDF]
      Automata and Processes on Multisets of Communicating Objects
      Natural Computing 9(4):865 - 887 (2010)



    33. Linmin Yang, Zhe Dang, and Oscar Ibarra.
    34. [PDF]
      Bond computing systems: a biologically inspired and high-level dynamics model for pervasive computing
      Natural Computing, 9(2): 347-364 (2010)



    35. Linmin Yang, Zhe Dang, and Oscar Ibarra.
    36. [PDF]
      On stateless automata and P systems
      International Journal of Foundations of Computer Science, 19(5): 1259-1276 (2008)



    37. Oscar Ibarra, Zhe Dang, and Linmin Yang.
    38. [PDF]
      On Counter Machines, Reachability Problems, and Diophantine Equations
      International Journal of Foundations of Computer Science, 19(4): 919-934 (2008)



    39. Zhe Dang, Oscar Ibarra, Cheng Li, Gaoyan Xie
    40. [PDF]
      On the Decidability of Model-checking of P Systems
      Journal of Automata, Languages, and Combintorics, 11(3): 279 - 298 (2006).



    41. Oscar Ibarra, Sara Woodworth, Hsu-Chun Yen and Zhe Dang
    42. [PDF]
      On the Computational Power of 1-Deterministic and Sequential P Systems
      Fundamenta Informaticae,73(1-2): 133-152 (2006)



    43. Oscar Ibarra and Zhe Dang
    44. [PDF]
      On the Solvability of a Class of Diophantine Equations and Applications
      Theoretical Computer Science, 352(1-3): 342-346 (2006)



    45. Zhe Dang and Oscar Ibarra
    46. [PDF]
      On P Systems Operating in Sequential Mode
      International Journal of Foundations of Computer Science, 16(5): 867-881 (2005)



    47. Oscar Ibarra, Hsu-Chen Yen and Zhe Dang
    48. [PDF]
      On various notions of parallelism in P systems
      International Journal of Foundations of Computer Science, 16(4): 683-705 (2005).



    49. Zhe Dang, Oscar Ibarra and Jianwen Su
    50. [PDF]
      On Composition and Lookahead Delegation of e-Services Modeled by Automata
      Theoretical Computer Science, 341(1-3): 344-363 (2005)


    51. Zhe Dang, Oscar Ibarra and Zhi-wei Sun
    52. [PDF]
      On Two-Way Nondeterministic Finite Automata with One Reversal-Bounded Counter
      Theoretical Computer Science 330(1): 59-79 (2005).


    53. Gaoyan Xie, Cheng Li and Zhe Dang.
    54. [Postscript] [PDF]
      Linear Reachability Problems and Minimal Solutions to Linear Diophantine Equation Systems.
      Theoretical Computer Science 328:203-219 (2004).


    55. O. H. Ibarra and Zhe Dang.
    56. [Postscript] [PDF]
      On Two-Way FA with Monotonic Counters and Quadratic Diophantine Equations.
      Theoretical Computer Science 312(2-3): 359-378 (2004).


    57. O. H. Ibarra, Zhe Dang, and O. Egecioglu.
    58. [Postscript] [PDF]
      Catalystic systems, semilinear sets, and vector addition systems.
      Theoretical Computer Science 312(2-3): 379-399 (2004).


    59. Zhe Dang, T. Bultan, O. H. Ibarra, and R. A. Kemmerer.
    60. [Postscript] [PDF]
      Past timed automata and safety verification.
      Theoretical Computer Science 313(1): 57-71 (2004).


    61. Zhe Dang.
    62. [PDF]
      Pushdown time automata: a binary reachability characterization and safety verification.
      Theoretical Computer Science, Vol 302, Issues 1-3, pp 93 - 121, 2003.


    63. Oscar H. Ibarra and Zhe Dang.
    64. [Postscript] [PDF]
      Eliminating the Storage Tape in Reachability Constructions.
      Theoretical Computer Science 299(1-3): 687-706 (2003).


    65. Zhe Dang, Pierluigi San Pietro, and Richard A. Kemmerer.
    66. [Postscript] [PDF]
      Presburger liveness verification for discrete timed automata.
      Theoretical Computer Science, vol 299, pp. 413-438, 2003.


    67. Zhe Dang, Oscar H. Ibarra, and Richard A. Kemmerer.
    68. [Postscript] [PDF]
      Generalized discrete timed automata: dcidable approximations for safety verification.
      Theoretical Computer Science, vol 296 (1), February 2003, pp. 59-74.



    69. Oscar H. Ibarra, Zhe Dang and Pierluigi San Pietro.
    70. [Postscript] [PDF]
      Verification in loosely synchronous queue-connected discrete timed automata.
      Theoretical Computer Science, vol. 290 (3), January 2003, pp. 1713-1735.


    71. Zhe Dang and Oscar H. Ibarra.
    72. [Postscript] [PDF]
      The Existence of Omega-Chains for Transitive Mixed Linear Relations and Its Applications.
      International Journal of Foundations of Computer Science, Vol. 13, No. 6 (2002) 911-936.


    73. Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan and Richard A. Kemmerer.
    74. [Postscript] [PDF]
      Counter Machines and Verification Problems.
      Theoretical Computer Science, vol. 289 (1), October 2002, pp. 165-189.


    75. Paul Z. Kolano, Zhe Dang, and Richard A. Kemmerer.
    76. [Postscript] [PDF]
      The Design and Analysis of Real-Time Systems Using the ASTRAL
      Software Development Environment.

      Annals of Software Engineering 7: 177-210 (1999)




      **********Conference and Workshop Papers*********


    77. Linmin Yang, Zhe Dang, Thomas R. Fischer, Min Sik Kim, and Li Tan.
    78. [PDF]
      Entropy and Software Systems -- towards an Information-theoretic Foundation of Software Testing
      Proceedings of FSE/SDP workshop on the future of software engineering research, November 2010


    79. Linmin Yang, Zhe Dang, and Thomas R. Fischer.
    80. [PDF]
      A syntax-independent complexity metric
      TMFCS'10, 127-134, 2010


    81. Linmin Yang, Zhe Dang, and Thomas R. Fischer.
    82. [PDF]
      Optimal Software Testing - A Cooling Down Process
      FCS'09, 162-168, 2009


    83. Linmin Yang, Yong Wang, and Zhe Dang.
    84. [PDF]
      Service Automata on Multisets of Communicating Objects
      Proceedings of the 7th International Conference on Unconventional Computation (UC'08),
      Lecture Notes in Computer Science, Vol. 5204, pp. 242-257, Springer, 2008.


    85. Linmin Yang, Zhe Dang, and Oscar Ibarra.
    86. [PDF]
      Bond computing systems: a biologically inspired and high-level dynamics model for pervasive computing
      Proceedings of the 6th International Conference on Unconventional Computation (UC'07)
      Lecture Notes in Computer Science, Vol. 4618, pp. 226-241, Springer, 2007.


    87. Linmin Yang, Zhe Dang, and Oscar Ibarra.
    88. [PDF]
      On stateless automata and P systems
      ACM'07, Budapest, Hungary, August, 2007, pp. 144-157.


    89. Cheng Li and Zhe Dang.
    90. [PDF]
      Decompositional Algorithms for Safety Verification and Testing of Aspect-Oriented Systems
      FATES'06.
      Lecture Notes in Computer Science, Vol. 4262, pp. 100-114, Springer, 2006.


    91. Shuohao Zhang, Curtis E. Dyreson and Zhe Dang.
    92. [PDF]
      Compacting XML Data
      Proceedings of the 11th International Conference on Database Systems for Advanced Applications (DASFAA'06).
      Lecture Notes in Computer Science, Vol. 3882, pp. 767-776, Springer, 2006.


    93. Cheng Li, Zhe Dang, Oscar Ibarra, and Hsu-Chen Yen.
    94. [PDF] (final version)
      [PDF] (long version)
      Signaling P Systems and Verification Problems
      Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05),
      Lecture Notes in Computer Science, Vol. 3580, pp. 1462--1473, Springer. 2005.



    95. Zhe Dang, O. Ibarra, S. Woodworth and H. Yen.
    96. [PDF]
      On Symport/Antiport Systems and Semilinear Sets.
      Proceedings of the 6th International Workshop on Membrane Computing (WMC6).
      Lecture Notes in Computer Science, Vol. 3850, pp. 253-271, Springer, 2005.



    97. Zhe Dang, Oscar Ibarra, Cheng Li and Gaoyan Xie.
    98. [PDF] (final version)
      [PDF] (originally submitted long version, with SPIN and Omega code)
      Model-checking of P systems
      Proceedings of the 4th International Conference on Unconventional Computation (UC'05),
      Lecture Notes in Computer Science, Vol. 3699, pp. 82-93, Springer, 2005.



    99. Gaoyan Xie and Zhe Dang.
    100. [PDF]
      Testing Systems of Concurrent Black-boxes---an Automata-Theoretic Approach
      Proceedings of the 5th Workshop on Formal Approaches to Testing Software (FATES'05),
      Lecture Notes in Computer Science, Vol. 3997, pp. 170-186, Springer, 2005.



    101. Oscar Ibarra, Sara Woodworth, Hsu-Chen Yen, and Zhe Dang.
    102. [PDF] (originally submitted version)
      On Sequential and 1-Deterministic P Systems
      Proceedings of the 11th International Computing and Combinatorics Conference (COCOON'05),
      Lecture Notes in Computer Science, Vol. 3595, pp. 905-914, Springer, 2005.



    103. Gaoyan Xie and and Zhe Dang.
    104. [PDF]
      CTL model-checking for systems with unspecified finite state components
      Proceedings of the 3rd workshop on specification and verification of component-based systems (SAVCBS'04), affiliated with ACM SIGSOFT 2004/FSE-12, ISU TR \#04-09, pp. 32-38, 2004.



    105. Oscar Ibarra, Hsu-Chen Yen, and Zhe Dang.
    106. [PDF]
      The Power of Maximal Parallelism in P Systems
      Proceedings of the 8th International Conference on Developments in Language Theory (DLT'04),
      Lecture Notes in Computer Science, Vol. 3340, pp. 212-224, Springer, 2004.



    107. Zhe Dang, Oscar Ibarra, Pierluigi San Pietro and Gaoyan Xie
    108. [PDF]
      Real-Counter Automata And Their Decision Problems
      Proceedings of the 24th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'04),
      Lecture Notes in Computer Science, Vol. 3328, pp. 198-210, Springer, 2004.



    109. Gaoyan Xie and Zhe Dang
    110. [PDF]
      An Automata-theoretic Approach for Model-checking Systems with Unspecified Components
      Proceedings of the 4th International Workshop on Formal Approaches to Software Testing (FATES'04),
      Lecture Notes in Computer Science, Vol. 3395, pp. 155-169, Springer, 2004.



    111. Zhe Dang, Oscar H. Ibarra and Jianwen Su
    112. [PDF]
      Composability of Infinite-State Activity Automata
      Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC'04),
      Lecture Notes in Computer Science, Vol. 3341, pp. 377-388, Springer, 2004.



    113. Zhe Dang and Oscar H. Ibarra
    114. [Postscript] [PDF]
      On P Systems Operating in Sequential Mode
      Preproceedings of the 6th Workshop on Descriptional Complexity of Formal Systems (DCFS'04), (L. Ilie, D. Wotschke, eds.), Report No. 619, Univ. of Western Ontario, London, Canada (2004), 164-177.



    115. Gaoyan Xie, Cheng Li, and Zhe Dang.
    116. [Postscript] [PDF] (long version)
      Testability of Oracle Automata
      Proceedings of the 9th International Conference on Implementation and Application of Automata (CIAA'04),
      Lecture Notes in Computer Science, Vol. 3317, pp. 331-332, Springer, 2004.



    117. Oscar H. Ibarra, Zhe Dang, Omer Egecioglu and Gaurav Saxena.
    118. [Postscript] [PDF]
      Characterizations of Catalytic Membrane Computing Systems.
      Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'03),
      Lecture Notes in Computer Science Vol. 2747, pp. 480--489, Springer. 2003.



    119. Gaoyan Xie, Cheng Li, and Zhe Dang.
    120. [Postscript] [PDF]
      New Complexity Results for Some Linear Counting Problems Using Minimal Solutions to Linear Diophantine Equations.
      Proceedings of the 8th International Conference on Implementation and Application of Automata (CIAA'03),
      Lecture Notes in Computer Science Vol. 2759, pp. 163--175, Springer. 2003.



    121. Gaoyan Xie, Zhe Dang, Oscar H. Ibarra and Pierluigi San Pietro.
    122. [PDF]
      Dense counter machines and verification problems.
      Proceedings of the 15th International Conference on Computer Aided Verification (CAV'03),
      Lecture Notes in Computer Science Vol. 2725, pp. 93--105, Springer. 2003.



    123. Gaoyan Xie, Zhe Dang and Oscar H. Ibarra.
    124. [PDF]
      A solvable class of quadratic Diophantine equations with applications to verification of infinite state systems.
      Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP'03),
      Lecture Notes in Computer Science Vol. 2719, pp. 668--680, Springer. 2003.



    125. Pierluigi San Pietro and Zhe Dang.
    126. [Postscript] [PDF]
      Automatic verification of multi-queue discrete timed automata
      Proceedings of the 9th Annual International Conference on Computing and Combinatorics (COCOON'03),
      Lecture Notes in Computer Science Vol. 2697, pp. 159--171, Springer. 2003.



    127. Oscar H. Ibarra, Zhe Dang and Zhi-wei Sun.
    128. [Postscript] [PDF]
      Safety Verification for Two-Way Finite Automata with Monotonic Counters
      Proceedings of the 6th International Conference on Developments in Language Theory (DLT'02),
      Lecture Notes in Computer Science Vol. 2450, pp. 326--338, Springer. 2002.



    129. Zhe Dang, Oscar H. Ibarra and Zhi-wei Sun.
    130. [Postscript] [PDF]
      On the Emptiness Problem for Two-way NFA with One Reversal-Bounded Counter
      Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC'02),
      Lecture Notes in Computer Science vol 2518, pp. 103--114, Springer. 2002.



    131. Zhe Dang, Oscar H. Ibarra and Pierluigi San Pietro.
    132. [Postscript] [PDF]
      Liveness Verification of Reversal-bounded Multicounter Machines
      with a Free Counter.

      Proceedings of the 20th International Conference on Foundations of
      Software Technology and Theoretical Computer Science (FSTTCS 2001)
      Lecture Notes in Computer Science vol 2245, pp. 132-143, Springer. 2001.



    133. Oscar H. Ibarra and Zhe Dang.
    134. [Postscript] [PDF]
      On removing the stack from reachability constructions
      with applications to Presburger LTL satisfiability-checking.

      Proceedings of the International Symposium on
      Algorithms and Computation (ISAAC 2001),
      Lecture Notes in Computer Science vol 2223, pp. 244-256, Springer. 2001.



    135. Zhe Dang, Tevfik Bultan, Oscar H. Ibarra and Richard A. Kemmerer.
    136. [Postscript] [PDF]
      Past Pushdown Timed Automata.
      Proceedings of the 6th International Conference on Implementation and
      Application of Automata (CIAA 2001)
      Lecture Notes in Computer Science 2494, pp. 74--86, Springer. 2002.



    137. Zhe Dang, Oscar H. Ibarra and Richard A. Kemmerer.
    138. [Postscript] [PDF]
      Decidable Approximations on Generalized and Parameterized Discrete Timed Automata.
      Proceedings of the 7th Annual International Computing and
      Combinatorics Conference (COCOON 2001),
      Lecture Notes in Computer Science 2108, pp. 529-539, Springer.



    139. Zhe Dang.
    140. [Postscript] [PDF]
      Binary reachability analysis of pushdown timed automata with dense clocks.
      Proceedings of the 13th International Conference on
      Computer Aided Verification (CAV 2001),
      Lecture Notes in Computer Science 2102, pp. 506 - 517, Springer.



    141. Zhe Dang, Pierluigi San Pietro and R. A. Kemmerer.
    142. [Postscript] [PDF]
      On Presburger Liveness of Discrete Timed Automata.
      Proceedings of the 18th International Symposium on
      Theoretical Aspects of Computer Science (STACS 2001)
      Lecture Notes in Computer Science 2010, pp. 132-143, Springer.



    143. Oscar H. Ibarra, Jianwen Su, Zhe Dang, T. Bultan and R. A. Kemmerer.
    144. [Postscript] [PDF]
      Counter Machines: Decidable Properties and Applications to Verification Problems.
      Proceedings of the 25th International Symposium on
      Mathematical Foundations of Computer Science (MFCS 2000),
      Lecture Notes in Computer Science 1893, pp. 426-435, Springer.



    145. Zhe Dang and R. A. Kemmerer.
    146. [Postscript] [PDF]
      Using the ASTRAL Symbolic Model Checker as a Specification Debugger:
      Three Approximation Techniques.

      Proceedings of the 22nd International Conference on
      Software Engineering (ICSE 2000),
      pp. 345-354, IEEE Press.



    147. Zhe Dang, Oscar H. Ibarra, Tevfik Bultan, Richard A. Kemmerer, and Jianwen Su.
    148. [Postscript] [PDF]
      Binary Reachability Analysis of Discrete Pushdown Timed Automata.
      Proceedings of the 12th International Conference on
      Computer Aided Verification (CAV 2000),
      Lecture Notes in Computer Science 1855, pp. 69-84, Springer.



    149. Zhe Dang and R. A. Kemmerer.
    150. [Postscript] [PDF]
      Using the ASTRAL Model Checker to Analyze Mobile IP.
      Proceedings of the 21st International Conference on
      Software Engineering (ICSE 99),
      pp. 132-141, IEEE Press.



    151. Zhe Dang and R. A. Kemmerer.
    152. [Postscript] [PDF]
      A symbolic model checker for testing ASTRAL real-time specifications.
      Proceedings of the 6th International Conference on
      Real-Time Computing Systems and Applications (RTCSA'99),
      pp. 174-181, IEEE Press.



    153. Zhe Dang and R. A. Kemmerer.
    154. [Postscript][PDF]
      Using the ASTRAL Model Checker for Cryptographic Protocol Analysis.
      DIMACS Workshop on Design and Formal Verification of Security Protocols, 1997.