About the Lab
The TheoryX Lab is dedicated to the exploration of foundational questions in theoretical computer science. Our research spans formal languages, automata theory, computational complexity, and computable analysis. We investigate the inherent difficulty of decision problems, the limits of algorithmic reasoning, and the boundaries between decidable and undecidable problems.
Particular emphasis is placed on the computational parallels among formal grammars, cellular automata, and quantum models of computation. We are actively developing theoretical frameworks to understand quantum complexity, with emerging interest in the theoretical foundations of artificial intelligence and machine learning, including quantum machine learning. This broader direction reflects our vision: to bridge the gap between complexity theory and the science of intelligence.
Lab Director
Dr. Jingnan Xie
Associate Professor of Computer Science, Millersville University
Dr. Xie is a theoretical computer scientist whose research focuses on automata theory, formal languages, computational complexity, computable analysis, and algorithm analysis. He earned his Ph.D. in Computer Science from the University at Albany, SUNY in 2017, under the mentorship of Dr. Harry B. Hunt III, with Turing Award laureate Dr. Richard E. Stearns serving on his dissertation committee. His current work explores deep connections among classical models of computation, complexity classes, and real-valued computation, with growing interests in quantum computing and theoretical aspects of learning and intelligence.
Dr. Xie also serves as a reviewer for:
Natural Computing (Springer)
Information and Computation (Elsevier)
Mathematical Reviews (American Mathematical Society)
External Collaborators
Dr. Harry B. Hunt III
Professor, University at Albany, SUNY
Dr. Hunt is a leading figure in theoretical computer science, with extensive contributions to computational complexity, automata theory, and formal language theory. He received his Ph.D. from Cornell University in 1973 under the supervision of John Hopcroft. His work has appeared in top-tier venues including Journal of the ACM and SIAM Journal on Computing, where he has published 7 and 12 papers respectively, underscoring his international standing in the field. His research has significantly shaped our understanding of the structural properties of complexity classes and logical characterizations of computation.
Dr. Richard E. Stearns
Distinguished Professor Emeritus, University at Albany, SUNY
Distinguished Institute Professor, Biocomplexity Institute, University of Virginia
Dr. Stearns is internationally recognized for his pioneering contributions to the theory of computation. He was awarded the ACM Turing Award in 1993 for co-founding the field of computational complexity with Juris Hartmanis. At the University at Albany, he served for more than two decades, including as department chair, and continues to contribute to research through his role at the University of Virginia. His work spans a broad range of topics including automata theory, algorithm analysis, database theory, and algorithmic game theory. Dr. Stearns has also held visiting positions at prestigious institutions such as Hebrew University, MSRI Berkeley, and Rensselaer Polytechnic Institute.
Dr. Ching-Sheng Lin
Associate Professor, Master Program of Digital Innovation, Tunghai University, Taiwan
Dr. Lin holds a Ph.D. in Computer Science from the State University of New York at Albany and specializes in natural language processing, artificial intelligence, machine learning, and computational complexity. His research bridges foundational theory with applications in digital innovation, and he has authored more than 15 peer-reviewed journal articles indexed by SCI. His background in both applied mathematics and theoretical computer science supports a unique interdisciplinary perspective.
Scientific Advisors
Dr. John E. Hopcroft
Dr. John E. Hopcroft is a renowned computer scientist and Professor Emeritus at Cornell University. He is widely recognized for his foundational contributions to the theory of computation and data structures, and is co-author of the seminal textbook Introduction to Automata Theory, Languages, and Computation. In 1986, Dr. Hopcroft was awarded the ACM Turing Award, the highest distinction in computer science, for his pioneering work in algorithms and computational complexity. He has mentored many leading figures in theoretical computer science and remains one of the most influential researchers in the field.
Dr. Juris Hartmanis (1928–2022)
Dr. Juris Hartmanis (1928–2022) was a leading figure in theoretical computer science and a Distinguished Professor Emeritus at Cornell University. He is best known for co-founding the field of computational complexity theory with Dr. Richard E. Stearns, a collaboration that earned them the ACM Turing Award in 1993. Their work introduced key complexity classes and laid the groundwork for understanding the inherent difficulty of computational problems. Dr. Hartmanis was the founding chair of Cornell’s Department of Computer Science and played a central role in establishing computer science as an independent academic discipline in the United States.
Current Students and Alumni
Emily Riley
Former undergraduate researcher, TheoryX Lab
Thesis: "On Productiveness and Complexity in Real Function Analysis through Hilbert’s Tenth Problem"
Emily is currently pursuing her Ph.D. in Mathematics at North Carolina State University, where she was admitted with full assistantship support. Her undergraduate research investigated the computational boundaries of real function theory through the lens of undecidability and productiveness of Hilbert's Tenth Problem, reflecting the lab’s broader mission to connect classical computability with real-world complexity.
Funding
- PASSHE FPDC Grant (2025–2026):
Project titled "Advancing Quantum Computing: Bridging Automata Theory and Quantum Models for Next Generation Computational Breakthroughs"
Award Amount: $10,000
Role: Principal Investigator (PI)
News
Selected Publications
- [Journal Paper] J. Xie, H.B. Hunt, III, and R.E. Stearns, "On the Computational and Descriptional Complexity of Multi-Pattern Languages". Theoretical Computer Science, vol. 1030, 2025.
- [Journal Paper] J. Xie and H.B. Hunt, III, "On the Undecidability and Descriptional Complexity of Synchronized Regular Expressions". Acta Informatica, vol. 60, pp. 257–278, 2023.
- [Journal Paper] J. Xie, H.B. Hunt, III, and R.E. Stearns, "Pumping Lemmas Can Be 'Harmful'". Theory of Computing Systems, vol. 68, no. 5, pp. 1339–1352, 2024.
- [Journal Paper] J. Xie, H.B. Hunt, III, and R.E. Stearns, "On Productiveness and Complexity in Computable Analysis through Rice-style Theorems for Real Functions". Mathematics, vol. 12, no. 20, article 3248, 2024.
- [Journal Paper] J. Xie, C.S. Lin, and H.B. Hunt, III, "Parallel Communicating Finite Automata: Productiveness and Succinctness". Mathematics, vol. 13, no. 8, article 1265, 2025.
- [Under Review] J. Xie, H.B. Hunt, III, and R.E. Stearns, "Decision Problems Concerning L Systems". Submitted to Theory of Computing Systems, Springer, 2024.
- [Under Review] J. Xie, C.S. Lin, H.B. Hunt, III, and R.E. Stearns, "A Practical Extension of Computational Complexity Theory for Applications in Mathematics and Sciences". Submitted to Theoretical Computer Science, Elsevier, 2025.
- [Under Review] C.N. Tsai, J. Xie, C.M. Lai, and C.S. Lin, "Leveraging Intra- and Inter-References in Vulnerability Detection Using Multi-Agent Collaboration Based on LLMs". Submitted to Cluster Computing, Springer, 2025.
- [Under Review] J. Xie, C.S. Lin, H.B. Hunt, III, and R.E. Stearns, "On One-Way and Two-Way Cellular Automata: Bi-Productiveness, Rice-Style Theorems, and Succinctness". Submitted to Theoretical Computer Science, Elsevier, 2025.
- [Under Review] CN. Tsai, J. Xie, CM. Lai, and CS. Lin, "A Multi-Layer Cooperative Multi-Agent Framework for Time Series Forecasting with Large Language Models". Submitted to World Wide Web, Springer, 2025.
- [Ph.D. Dissertation] J. Xie, "Complexity Theoretic Parallels among Automata, Formal Languages and Real Variables including Multi-Patterns, L-Systems and Cellular Automata". Ph.D. Dissertation, University at Albany, SUNY, 2017.