Distributional Learning of Graph Languages Generated by Fixed-Interface Clause Systems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910176525680640 |
|---|---|
| author | Shoudai, Takayoshi Matsumoto, Satoshi Suzuki, Yusuke Uchida, Tomoyuki |
| author_facet | Shoudai, Takayoshi Matsumoto, Satoshi Suzuki, Yusuke Uchida, Tomoyuki |
| contents | Distributional learning provides a framework for studying the learnability of structured languages from positive data. In this paper, we extend this framework to graph languages generated by fixed-interface clause systems.
We formulate fixed-interface graph pattern clause systems and define a learning model based on positive presentations and membership queries. We consider a bounded class of graph languages satisfying the finite context property under a bounded-degree assumption. The bounds are expressed by a parameter tuple $(Δ,m,s,t,w,d)$, which controls both the generated graph class and the structural complexity of the clause systems.
We give an oracle-guided learning algorithm that constructs hypotheses from boundary representations induced by observed positive examples. The proof shows that target contexts eventually appear in the sample, target clauses are reconstructed over the corresponding predicate representatives, and spurious clauses are excluded by membership queries. Hence, for every fixed parameter tuple $(Δ,m,s,t,w,d)$, the target language is identifiable in the limit from positive data and membership queries.
We also prove that the learner has polynomial-time update on $\mathcal{FICSL}^{\mathrm{FCP}}_Δ(m,s,t,w,d)$. Thus, the paper gives a parameterized reformulation of distributional learning for regular FGS-style graph languages in a fixed-interface setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_26333 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distributional Learning of Graph Languages Generated by Fixed-Interface Clause Systems Shoudai, Takayoshi Matsumoto, Satoshi Suzuki, Yusuke Uchida, Tomoyuki Formal Languages and Automata Theory Distributional learning provides a framework for studying the learnability of structured languages from positive data. In this paper, we extend this framework to graph languages generated by fixed-interface clause systems. We formulate fixed-interface graph pattern clause systems and define a learning model based on positive presentations and membership queries. We consider a bounded class of graph languages satisfying the finite context property under a bounded-degree assumption. The bounds are expressed by a parameter tuple $(Δ,m,s,t,w,d)$, which controls both the generated graph class and the structural complexity of the clause systems. We give an oracle-guided learning algorithm that constructs hypotheses from boundary representations induced by observed positive examples. The proof shows that target contexts eventually appear in the sample, target clauses are reconstructed over the corresponding predicate representatives, and spurious clauses are excluded by membership queries. Hence, for every fixed parameter tuple $(Δ,m,s,t,w,d)$, the target language is identifiable in the limit from positive data and membership queries. We also prove that the learner has polynomial-time update on $\mathcal{FICSL}^{\mathrm{FCP}}_Δ(m,s,t,w,d)$. Thus, the paper gives a parameterized reformulation of distributional learning for regular FGS-style graph languages in a fixed-interface setting. |
| title | Distributional Learning of Graph Languages Generated by Fixed-Interface Clause Systems |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2604.26333 |