Query Learning of Context-Deterministic and Congruential Context-Free Languages over Infinite Alphabets
The 50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM2025),
Lecture Notes in Computer Science Vol.15539, pp.211-224
(2025), [peer-reviewed]
Event Date:
January 20-23, 2025
Abstract / 概要
This paper is concerned with learning some context-free languages (CFLS) over infinite alphabets from membership and equivalence queries. Argyros and D’Antoni (2018) proposed a query learning algorithm for regular languages over infinite alphabets using deterministic symbolic automata. Our algorithms learn context-deterministic CFLS and congruential CFLS over infinite alphabets. We enhance the existing algorithms for learning those CFL classes over finite alphabets by adapting Argyros and D’Antoni’s technique. Our result shows that their technique can be extended to learn richer classes beyond regular languages.