Scholarlink

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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Query Learning of Context-Deterministic and Congruential Context-Free Languages over Infinite Alphabets

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Yutaro Numaya,
  • Yoshito Kawasaki,
  • Ryo Yoshinaka,
  • Ayumi Shinohara

摘要

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.