Research Topics

Computational Complexity

Computational complexity theory focuses on classifying computational problems as 'easy' or 'hard' according to their resource usage. One of the roles of computational complexity theory is to determine the practical limits on what computers (and human beings) can and cannot do. For example, you may learn an undecidable problem named the Halting Problem in CSCI340. This means, no matter how smart a person is, one cannot find an algorithm to solve the Halting Problem.

Formal Languages

Formal languages provide the theoretical underpinnings for the study of programming languages as well as the foundations for compiler design. They are important in such areas as the study of biological systems, data transmission and compression, computer networks, etc. In computational complexity theory, decision problems are typically defined as formal languages and complexity classes are defined as the sets of formal languages. In logic and foundations of mathematics, formal languages are used to represent the syntax of axiomatic systems.


The development and analysis of algorithms is fundamental to all aspects of computer science. It is the engine at the core of the computerized solution of any mathematical model. Research in algorithms involves the best ways to formulate computational problems as well as solve them in various serial, parallel, streaming, and distributed environments.

Selected Publications

  • [JOURNAL PAPER]J. Xie and H.B. Hunt, III, "On the Undecidability and Descriptional Complexity of Synchronized Regular Expressions". Acta Informatica 60, 257-278 (2023). [PDF]
  • [PHD DISS] J. Xie, "Complexity Theoretic Parallels among Automata, Formal Languages and Real Variables including Multi-Patterns, L-Systems and Cellular Automata". University at Albany, SUNY, Albany, NY, 2017. [PDF]
  • [JOURNAL PAPER UNDER REVIEW] J. Xie and H.B. Hunt, III, "On the Computational and Descriptional Complexity of Multi-Pattern Languages". Submitted to Theoretical Computer Science (2023) (Under Review). [PDF]
  • [JOURNAL PAPER UNDER REVIEW] J. Xie and H.B. Hunt, III, "Pumping Lemmas Could be 'Harmful'". Submitted to Theory of Computing Systems (2023) (Under Review). [PDF]