Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing
Takayuki Kuriyama · 2026
Read Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing by Takayuki Kuriyama (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11644.txt.
Introduction
Takayuki Kuriyama studies finite watch in good-data learning of context-free tongues. Good data can show two tuples share a context without proving swap. Using finite built-up watches via monoid maps, he defines a watch-guarded tuple swap rule. He gives a set-driven learner getting every language in the full meaning slice for fixed fan-out. Under a fixed branching cap, building is quick. A fixed bound on unknown watch size folds into all-purpose tuning giving back ID, while the endless union stays un-ID-able.
Catalog record
| CREATOR | Takayuki Kuriyama |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 136767 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11644
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing Takayuki Kuriyama Abstract We study positive-data learning of bounded-fan-out linear multiple context-free grammars under a fixed explicit finite monoid homomorphism h h . The main obstacle beyond the context-free case is that an MCFG nonterminal derives a tuple whose components may be placed in a surrounding sentence in different orders. We introduce sentence-interface types as finite external control objects for such tuple occurrences. A type records the permutation of tuple components in the final sentence together with the h h -values of the boundary intervals between them. For reduced working binary linear nondeleting MCFG presentations whose string languages satisfy ( f , h ) (f,h) -tuple substitutability, we build a typed refinement, a finite characteristic sample, and a canonical positive-data learner. Once the sample contains this characteristic sample and remains contained in the target language, the learner reconstructs the language exactly. Consequently, for fixed fan-out bound f f and fixed explicit h h , the resulting class is identifiable in the limit from positive data. Moreover, the hypothesis associated with any given finite sample is constructible in polynomial time for fixed f f and fixed h h , including output size. Thus sentence-interface control is the finite mechanism that lifts fixed- h h distributional reconstruction from context-free grammars to bounded-fan-out linear MCFGs. Keywords. grammatical inference, multiple context-free grammars, linear multiple context-free grammars, finite monoids, sentence-interface types, identification in the limit 1 Introduction Learning grammars from positive data alone requires finite information that can eventually be observed in every complete text for the target language. Gold’s theorem rules out broad language classes in this setting [ 9 ] , while query-learning models such as Angluin’s regular-set algorithm obtain power from active information [ 3 ] . A standard positive-data strategy is therefore to restrict the distributional behavior of substrings or tuples so that finitely many observed contexts are enough to determine the whole language. This perspective underlies the Clark–Eyraud line for context-free grammars [ 4 ] , Yoshinaka’s substitutability-based work for context-free and mildly context-sensitive languages [ 16 , 17 , 18 ] , and later developments for multiple context-free grammars with Clark [ 5 , 6 ] . Kanazawa’s monograph on learnable classes of categorial grammars provides another background example in which restrictions on grammatical structure lead to positive-data learnability through finite witnessing information, compatible with the characteristic-sample viewpoint used here [ 11 ] . The present paper asks what finite local information is needed when the grammar formalism is a bounded-fan-out linear MCFG. MCFGs are a standard mildly context-sensitive formalism [ 14 , 15 , 13 , 10 ] ; their nonterminals derive tuples rather than single strings. Thus the external environment of a nonterminal occurrence is not just a two-sided context. The tuple components may be scattered through the final sentence, and their left-to-right placement can change from one occurrence to another. Componentwise information such as h(w_{1}),\ldots,h(w_{d}) is therefore not enough to describe the role of a d -tuple occurrence in a sentence. Our finite control object is the sentence-interface type . For an arity- d sentence context, it records the permutation in which the d holes appear and the h -values of the d+1 boundary intervals between and around them. Because both the fan-out bound f and the finite monoid M are fixed, the resulting interface space S_{d}\times M^{d+1} is finite for each d\leq f . The permutation component is essential for the reconstruction proof: it records how a parent rule routes a child tuple into the surrounding sentence, while the boundary entries provide the finite monoid data needed for substitutability. The semantic distributional assumption is (f,h) -tuple substitutability. It compares tuples only when they have the same componentwise h -type; under that equality, sharing one accepting sentence context forces equality of all accepting sentence contexts. Yoshinaka’s multidimensional substitutability is stronger as a distributional implication because it does not require equality of componentwise h -types. The fixed- h setting therefore gives a different reconstruction problem: the learner is not trying to infer the finite monoid, but to use the prescribed finite monoid as external control for typed reconstruction. Technically, the paper proceeds from finite interface control to exact reconstruction. Given a reduced working binary linear nondeleting MCFG presentation of fan-out at most f , we refine each nonterminal by both its componentwise output h -type and its sentence-interface type. The transport maps induced by binary rule templates determine the interface of each child occurrence from the parent interface and the sibling output type. After trimming to productive and reachable typed copies, we extract a finite characteristic sample exposing every surviving typed state and every realized typed rule. The canonical learner rebuilds rules from observed typed tuples and concrete binary witnesses. Soundness is supplied by (f,h) -tuple substitutability; completeness is supplied by the exposed typed refinement. This paper is related to the author’s fixed- h reconstruction for CFGs [ 1 , 2 ] , but the present contribution is not merely a notational lift. In the CFG case an occurrence has an ordinary two-sided context. In the MCFG case the external state must additionally control the sentence-level placement of tuple components. Sentence-interface types are introduced to isolate precisely this new finite object. The theorem should be read as a fixed-parameter positive-data reconstruction result. The fan-out bound f , the explicit finite homomorphism h\colon\Sigma^{*}\to M , and the working binary linear nondeleting presentation discipline are fixed in advance. Within this regime, the learner reconstructs the target language once a finite characteristic sample has appeared and constructs the current hypothesis in polynomial time from the finite sample at hand. The point is therefore not to infer the finite monoid or to normalize arbitrary MCFG presentations, but to show that sentence-interface types provide enough finite external control for exact reconstruction under the fixed- h discipline. The contributions are as follows. (i) We introduce sentence-interface types S_{d}\times M^{d+1} as finite external control states for tuple occurrences in bounded-fan-out linear MCFGs under fixed monoid typing. (ii) We define rule-template transport maps that propagate these types from parent occurrences to child occurrences using the sibling componentwise h -type. (iii) We construct the typed refinement and prove the associated typing invariants and language equivalence. (iv) We extract a finite characteristic sample exposing typed states and realized typed rules, and define a canonical positive-data learner. (v) We prove exact reconstruction, identification in the limit, and polynomial-time construction of the hypothesis from a given finite sample for fixed f and fixed explicit h . The paper is organized as follows. Section 2 states the main results early. Section 3 positions the paper with respect to distributional learning, fixed finite monoid control, and MCFG learning. Section 4 fixes the learning model, the working MCFG formalism, the fixed finite monoid parameter, and (f,h) -tuple substitutability. Section 5 explains why sentence-level placement must be recorded. Section 6 defines sentence-interface types and transport maps. Sections 7 and 8 construct the typed refinement, the characteristic sample, and the learner. Section 9 proves exact reconstruction and identification in the limit. Section 10 proves polynomial-time hypothesis construction from a given finite sample. Sections 11 and 12 discuss the scope and conclude. 2