- PrevMobile Networking 23.09.19
- NextCombinatorial Optimization 23.09.19
Research
Lab
Theory of ComputationLab
Prof. Yo-Sub Han
Engineering Building 4, Room 709
Lab Introduction
The Theory of Computation lab understands the limitations of computers and conducts research on computational complexity and efficient algorithm design in consideration of the limitations. In particular, we study efficient problem solving methods based on computation theory, such as computational models represented by Turing machines and various algorithm design techniques. Currently, our main areas of interest are 1) study on computational theory such as measuring the similarity between formal languages, efficient search algorithms, and learning/inferring formal grammars, and 2) study of applications using formal language theory such as extracting features of text data including natural language based on automata theory, and designing a learning feramework that uses both neural models and formal grammars.
Research field
Theory of computation Automata theory Algorithm design Information retrieval Natural language processing Neural-symbolic modelRepresentative Papers
- Han, Y. S., Ko, S. K., Ng, T., & Salomaa, K. (2021). Consensus string problem for multiple regular languages. Information and Computation, 279, 104615.
- Kim, H., Woo, D., Oh, S. J., Cha, J. W., & Han, Y. S. (2021). ALP: Data Augmentation using Lexicalized PCFGs for Few-Shot Text Classification. arXiv preprint arXiv:2112.11916. To appear in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI-22)
- Cognetta, M., Han, Y. S., & Kwon, S. C. (2018). Incremental computation of infix probabilities for probabilistic finite automata. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (pp. 2732-2741).