一句话:提出 finite-aspect checkable 语言,并用树自动机元定理统一证明多类表达式学习问题可判定。
本文研究带语法限制的表达式学习问题,旨在刻画哪些符号语言的学习是可判定的。作者提出 finite-aspect checkable 语言类:其语义可由与表达式规模无关、但依赖固定求值结构的有界辅助信息定义。为统一处理此类语言,论文设计了一种用于编写表达式语法树求值程序的通用编程语言,并证明元定理:若某语言可由该语言中的程序定义,则它可对应到有限树自动机。由此,研究者只需编写程序,即可为多个表达式学习问题导出新的可判定性结果与判定过程。
We study expression learning problems with syntactic restrictions and introduce the class of finite-aspect checkable languages to characterize symbolic languages that admit decidable learning. The semantics of such languages can be defined using a bounded amount of auxiliary information that is independent of expression size but depends on a fixed structure over which evaluation occurs. We introduce a generic programming language for writing programs that evaluate expression syntax trees, and we give a meta-theorem that connects such programs for finite-aspect checkable languages to finite tree automata, which allows us to derive new decidable learning results and decision procedures for several expression learning problems by writing programs in the programming language.