The Strong, Weak, and Very Weak Finite Context and Kernel Properties

详细信息    查看全文

• 关键词：Grammatical inference and algorithmic learning ; Distributional learning ; Finite context property ; Finite kernel property ; Context ; free languages
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10168
• 期：1
• 页码：77-88
• 丛书名：Language and Automata Theory and Applications
• ISBN：978-3-319-53733-7
• 卷排序：10168

文摘

We identify the properties of context-free grammars that exactly correspond to the behavior of the dual and primal versions of Clark and Yoshinaka’s distributional learning algorithm and call them the very weak finite context/kernel property. We show that the very weak finite context property does not imply Yoshinaka’s weak finite context property, which has been assumed to hold of the target language for the dual algorithm to succeed. We also show that the weak finite context property is genuinely weaker than Clark’s strong finite context property, settling a question raised by Yoshinaka.