Geometric Characterization of Context-Free Intersections via the Inner Segment Dichotomy Jorge Miguel Silva Abstract The intersection of two context-free languages is not generally context-free, but no geometric criterion has characterized when it remains so. The crossing gap ( max ⁡ ( i ′ − i , j ′ − j ) \max(i^{\prime}-i,\;j^{\prime}-j) for two crossing push-pop arcs) is the natural candidate. We refute this: we exhibit CFLs whose intersection is CFL despite unbounded-gap crossings. The governing quantity is the inner segment measure : for crossing arcs inducing a decomposition w = P 1 ​ P 2 ​ P 3 ​ P 4 w=P_{1}P_{2}P_{3}P_{4} , it is max ⁡ ( | P 2 | , | P 3 | ) \max(|P_{2}|,|P_{3}|) , the length of the longer inner segment between interleaved crossing endpoints. We prove a dichotomy for this measure: bounded inner segments imply context-freeness via a finite buffer construction; growing inner segments with pump-sensitive linkages imply non-context-freeness. The inner segment concept applies to all CFL intersections; the strictness of the resulting characterization depends on the language class. For block-counting CFLs (languages requiring equality among designated pairs of block lengths), the dichotomy is complete: the intersection is CFL if and only if the combined arcs are jointly well-nested. For general CFLs, the CFL direction is unconditional; the non-CFL direction requires pump-sensitive linkages whose necessity is the main open problem, reducing the general CFL intersection problem to a specific property of pump-sensitive decompositions. MSC 68Q45 , 68Q42 , 03D05 † † highlights: The crossing gap between PDA arcs does not determine context-freeness of CFL intersections. The inner segment measure, the length of the longer inner segment between interleaved crossing endpoints, is the governing quantity. Bounded inner segments yield a buffered PDA construction; growing inner segments with pump-sensitive linkages imply non-CFL. For block-counting CFLs, the dichotomy is complete: CFL if and only if arcs are jointly well-nested. The general CFL intersection problem reduces to a specific question about pump-sensitive decompositions. 1 Introduction Context-free languages are not closed under intersection. The power of a pushdown automaton lies in its stack, and the stack’s limitation is its rigidity: it provides last-in, first-out (LIFO) access, so information buried below the top is inaccessible until everything above it has been removed. When two CFLs are intersected, the question is whether two independent stack protocols, each tracking its own push-pop dependencies, can be interleaved into a single stack. If the two sets of dependency arcs nest cleanly, one stack handles both. If they do not, the intersection may leave the CFL class entirely. The language \{a^{m}b^{n}c^{m}d^{n}\} , arising from \{a^{m}b^{*}c^{m}d^{*}\}\cap\{a^{*}b^{n}c^{*}d^{n}\} , is the classic example: its a -to- c and b -to- d dependencies cross , and no single stack can process both 9 ; 6 . Bodirsky, Kuhlmann, and Möhl 3 formalized this via well-nestedness in the LCFRS hierarchy. However, not all crossings destroy context-freeness. If arcs from the two PDAs cross only at adjacent positions, as in the interleaved palindrome language of Example 2.1 , the crossing is local and a pair-alphabet encoding absorbs it. This raises a geometric question: what property of crossing dependency arcs determines whether two stack protocols can share one stack? While initially motivated by structural decomposition problems in sequence analysis and data compression, this question applies to all context-free languages and has remained open in the automata-theoretic literature. The natural conjecture, and its refutation. The crossing gap of two crossing arcs, defined formally as \max(i^{\prime}-i,\;j^{\prime}-j) (the larger of the push-endpoint distance and the pop-endpoint distance; Definition 5.1 ), is a natural candidate: if the gap grows with input size, the stack should break; bounded-gap crossings should be harmless. This conjecture is false. In Proposition 6.5 , we exhibit two CFLs whose intersection remains context-free despite having crossing arcs with crossing gap \Theta(n) . The construction is explicit: one PDA performs a single push-pop pair spanning two positions, while the other PDA’s matching arc spans \Theta(n) positions around it. Both inner segments have length exactly 1 , so the “interruption” is absorbed by a finite buffer, yet the crossing gap grows without bound. Intuitively, an arc that spans many positions but encloses no other machine’s operations creates a large gap without imposing any burden on the stack. The governing measure: inner segments. The right quantity is the inner segment measure \max(|P_{2}|,|P_{3}|) . When two arcs (i,j) and (i^{\prime},j^{\prime}) cross with ip and consider w_{n}=P_{1}P_{2}P_{3}P_{4} with |P_{i}|\geq n>p . By the pumping lemma, there exists a factorization w_{n}=uvxyz with |vxy|\leq p , |vy|\geq 1 , and uv^{i}xy^{i}z\in L for all i\geq 0 . Since |vxy|\leq pp\geq|vxy| , the start of vxy lies strictly inside P_{2} , so vxy is disjoint from P_{1} . Since |P_{3}|>p\geq|vxy| , the end of vxy lies strictly inside P_{3} , so vxy is disjoint from P_{4} . Hence vxy intersects P_{2} but not P_{4} ; by (iii), contradiction. Cases 5–7 ( vxy\subseteq P_{3} , straddling P_{3}P_{4} , vxy\subseteq P_{4} ) are symmetric. All cases yield contradictions. ∎ 3.3 Application to CFL intersection Corollary 3.4 . Let L_{1},L_{2} be context-free languages. Suppose there exist, for infinitely many n , a string w_{n}\in L_{1}\cap L_{2} and a factorization w_{n}=P_{1}P_{2}P_{3}P_{4} with |P_{i}|\geq n , such that L_{1} has a pump-sensitive linkage (P_{1},P_{3}) and L_{2} has a pump-sensitive linkage (P_{2},P_{4}) . Then L_{1}\cap L_{2} is not context-free. Proof. Since L_{1}\cap L_{2}\subseteq L_{1} , pump-sensitive linkages of L_{1} are inherited by L_{1}\cap L_{2} . Similarly for L_{2} . Apply Theorem 3.3 . ∎ 3.4 Verification on known examples Example 3.5 ( \{a^{n}b^{n}c^{n}d^{n}\} ) . Let L_{1}=\{w\in a^{*}b^{*}c^{*}d^{*}:\#_{a}(w)=\#_{c}(w)\} , L_{2}=\{w\in a^{*}b^{*}c^{*}d^{*}:\#_{b}(w)=\#_{d}(w)\} , both context-free. Set L=L_{1}\cap L_{2}=\{a^{n}b^{n}c^{n}d^{n}\} . Factor a^{n}b^{n}c^{n}d^{n} as P_{1}=a^{n} , P_{2}=b^{n} , P_{3}=c^{n} , P_{4}=d^{n} , all of size n . We verify the pump-sensitive linkages on L itself (not on L_{1} or L_{2} individually; see Remark 3.6 below). Linkage (P_{1},P_{3}) on L : any factorization w=uvxyz where vxy intersects P_{1} but is disjoint from P_{3} has vxy contained in the a - b region. Since |vy|\geq 1 , pumping changes at least one of \#_{a} or \#_{b} : if \#_{a} changes, then \#_{a}\neq\#_{c}=n violates the L_{1} -constraint; if \#_{a} is unchanged, then some b ’s were pumped, giving \#_{b}\neq n=\#_{d} , violating the L_{2} -constraint. Either way, uv^{2}xy^{2}z\notin L . Linkage (P_{2},P_{4}) on L : symmetric. By Theorem 3.3 , L is not CFL. Remark 3.6 . The linkages above hold on L=L_{1}\cap L_{2} , not on L_{1} alone. On L_{1}=\{w:\#_{a}=\#_{c}\} , the linkage (P_{1},P_{3}) fails: a cross-boundary factorization with v=\epsilon , x=a\cdot b^{s} , y=b^{t} has vxy intersecting P_{1} but disjoint from P_{3} , yet pumping just adds b ’s, preserving \#_{a}=\#_{c} . The intersection’s additional constraints ( \#_{b}=\#_{d} ) prevent this escape. This subtlety means Corollary 3.4 , which requires linkages on the ambient languages L_{1},L_{2} individually, does not apply to this example. Instead, we apply Theorem 3.3 directly to L . For block-counting CFLs, linkages on the intersection always hold: any pump modifying one block’s count, without modifying its partner’s, violates one of the intersection’s constraints. Example 3.7 ( \{a^{n}b^{n}c^{n}\} ) . Take L_{1}=\{a^{n}b^{n}w:w\in c^{*}\} and L_{2}=\{wb^{n}c^{n}:w\in a^{*}\} , both CFL. The block-counting arcs are (1,2) from L_{1} and (2,3) from L_{2} , which share endpoint 2 ; accordingly, L_{1}\cap L_{2}=\{a^{n}b^{n}c^{n}\} enforces the three-way equality |B_{1}|=|B_{2}|=|B_{3}| , which is not CFL by the standard pumping argument 5 . (This illustrates the shared-endpoint mechanism of Definition 4.3 (iv) rather than crossing arcs; the full characterization is given in Theorem 4.4 .) 3.5 What the crossing theorem covers Theorem 3.3 handles any pair of CFLs whose intersection admits strings with four linearly-growing segments and crossing pump-sensitive linkages, including all block-counting CFLs with crossing arcs. Theorem 6.1 (in Section 6 ) relaxes the requirement from all four segments to a single inner segment growing unboundedly. Theorem 3.3 does not cover bounded-gap crossings. The condition |P_{i}|\geq n ensures all four segments grow with n . Theorem 5.4 proves that bounded-gap crossings ( O(1) ) are always resolvable. 4 Complete characterization for block-counting CFLs 4.1 Block-counting CFLs Definition 4.1 . A block-counting CFL over disjoint sub-alphabets \Sigma_{1},\dots,\Sigma_{k} is a language of strings w=B_{1}B_{2}\cdots B_{k} with B_{i}\in\Sigma_{i}^{*} , subject to equality constraints C\subseteq\binom{[k]}{2} on block lengths: for each (i,j)\in C , |B_{i}|=|B_{j}| . Each constraint (i,j)\in C is called an arc from block i to block j . 4.2 Joint well-nestedness Definition 4.2 . An arc set C on \{1,\dots,k\} is well-nested if no two arcs in C cross: there are no (i,j),(i^{\prime},j^{\prime})\in C with ip . Call a block index \ell crossing-connected if it is reachable from \{i,i^{\prime},j,j^{\prime}\} via arcs in C_{1}\cup C_{2} (treating arcs as undirected edges on block indices). Let w\in L have |B_{\ell}|=n for every crossing-connected block \ell and |B_{\ell}|=0 for all other blocks. All constraints are satisfied: constraints between two crossing-connected blocks have n=n ; constraints between two non-crossing-connected blocks have 0=0 ; and no arc connects a crossing-connected block to a non-crossing-connected one (by definition of reachability). The pumping lemma gives a factorization uvxyz with |vxy|\leq p and |vy|\geq 1 . Since crossing-connected blocks have size n>p and all other blocks are empty, vxy lies within at most two adjacent crossing-connected blocks. Every such block is connected via a chain of arcs to some crossing endpoint \alpha\in\{i,i^{\prime},j,j^{\prime}\} , whose crossing partner \beta satisfies |\alpha-\beta|\geq 2 (since ip in the string. Since |vxy|\leq p , any factorization touching a crossing-connected block cannot reach that block’s crossing partner. If vxy lies entirely within a single block B_{\ell} , pumping changes |B_{\ell}| while the partner block is unreachable, violating a constraint. If vxy straddles two adjacent blocks B_{\ell} and B_{\ell+1} , pumping changes at least one block’s length; tracing that block’s arc chain to a crossing endpoint yields a distant partner whose length remains n , again violating a constraint. So L is not CFL. For (b): distinct arcs from C_{1} and C_{2} share an endpoint: say (i,j)\in C_{1} and (i,j^{\prime})\in C_{2} with j\neq j^{\prime} . Then L_{1}\cap L_{2} enforces |B_{i}|=|B_{j}| and |B_{i}|=|B_{j^{\prime}}| , i.e., |B_{i}|=|B_{j}|=|B_{j^{\prime}}| , a three-way equality over disjoint alphabets, which is not CFL by a standard pumping argument (cf. 5 ). (If C_{1} and C_{2} share an identical arc (i,j) , no new constraint is added, and the shared arc does not obstruct CFL-ness.) ∎ 4.4 Discussion Theorem 4.4 provides a complete characterization for block-counting CFLs. Theorem 6.1 (in Section 6 ) recovers this characterization as a consequence of the inner-segment-based analysis, since all crossings in the block-counting setting have growing inner segments with pump-sensitive linkages on L_{1}\cap L_{2} (cf. Remark 3.6 ). Extending to general CFLs requires two ingredients: a grammar-independent definition of “matching arcs,” and a proof that non-CFL intersections always produce pump-sensitive linkages on some crossing pair. The CFL direction of the inner segment dichotomy ( Theorem 6.7 ) is unconditional; the non-CFL direction ( Theorem 6.1 ) is conditional on the linkage assumption. The connection to well-nestedness in the LCFRS hierarchy is discussed in Section 7 . 5 Bounded-gap crossings are always resolvable 5.1 Definitions PDA normal form convention. Throughout this section and Section 6 , we assume PDAs are in a normal form where each transition reads exactly one input symbol and performs at most one stack operation (push of a single symbol, or pop). Any PDA can be converted to this form: first convert the CFG to Greibach Normal Form (GNF), then construct the standard GNF-to-PDA translation. The resulting PDA may push up to two symbols per step (from binary productions); we decompose each such step into sequential single-push transitions via auxiliary states that perform \epsilon -moves. The auxiliary states increase |Q| by a grammar-dependent constant factor but do not read input symbols, so each input position is associated with at most two pushes and one pop of a single symbol. Buffer bounds depending on arc span (measured in input positions) therefore correctly limit the number of simultaneously pending operations, up to the constant factor of 2 . Recall from Section 2 that \mu_{M}(w) denotes the push-pop matching of PDA M on string w . Definition 5.1 (Crossing gap) . For PDAs M_{1},M_{2} and string w\in L(M_{1})\cap L(M_{2}) , a crossing pair consists of arcs (i,j) and (i^{\prime},j^{\prime}) from different machines (i.e., one from \mu_{M_{1}}(w) and the other from \mu_{M_{2}}(w) ) with ij_{\mathrm{pop}} , which means ip and consider w_{n}=P_{1}P_{2}P_{3}P_{4} with \max(|P_{2}|,|P_{3}|)\geq n>p . By the pumping lemma, there exists a factorization w_{n}=uvxyz with |vxy|\leq p , |vy|\geq 1 , and uv^{i}xy^{i}z\in L for all i\geq 0 . We consider two cases. Case A: |P_{2}|\geq n>p . We enumerate all possible locations of vxy : Case 1: vxy\subseteq P_{1} . Disjoint from P_{3} (separated by P_{2} of length >p ). By (i), contradiction. Case 2: vxy straddles the P_{1}P_{2} boundary. Since |vxy|\leq p<|P_{2}| , vxy cannot reach past P_{2} , so it is disjoint from P_{3} and P_{4} . Intersects P_{1} but not P_{3} ; by (i), contradiction. Case 3: vxy\subseteq P_{2} . Disjoint from P_{4} (separated by P_{3} ). By (ii), contradiction. Case 4: vxy straddles the P_{2}P_{3} boundary. Since |vxy|\leq p<|P_{2}| , the start of vxy lies strictly inside P_{2} , so vxy is disjoint from P_{1} . Two sub-cases: if |P_{3}|\geq p , then the end of vxy lies strictly inside P_{3} , so vxy is disjoint from P_{4} ; it intersects P_{2} but not P_{4} , and (ii) gives a contradiction. If |P_{3}|

p ), so (i) gives a contradiction. Case 5: vxy\subseteq P_{3} . Disjoint from P_{1} (separated by P_{2} of length >p ). By (i), contradiction. Case 6: vxy straddles the P_{3}P_{4} boundary. Disjoint from P_{1} (since |P_{2}|>p separates P_{1} from P_{3} ). Intersects P_{3} but not P_{1} ; by (i), contradiction. Case 7: vxy\subseteq P_{4} . Disjoint from P_{2} (separated by P_{3} ). By (ii), contradiction. Case B: |P_{3}|\geq n>p (and |P_{2}| may be small). Cases 3 and 7 carry over from Case A with P_{3} (of length >p ) providing the separation between P_{2} and P_{4} . Cases 5 and 6 carry over because vxy starts inside P_{3} , hence is disjoint from P_{1} regardless of |P_{2}| ; by (i), contradiction. The cases that differ are 1, 2, and 4, where a short P_{2} may let vxy straddle across multiple segments: Case 1: vxy\subseteq P_{1} . Entirely within P_{1} , hence disjoint from P_{3} . By (i), contradiction. Case 2: vxy straddles the P_{1}P_{2} boundary. If |P_{2}|\geq p , the argument from Case A applies. If |P_{2}|

p\geq|vxy| , vxy cannot reach P_{4} . Hence vxy intersects P_{2} but is disjoint from P_{4} ; by (ii), contradiction. Case 4: vxy straddles the P_{2}P_{3} boundary. Since |P_{3}|>p\geq|vxy| , vxy is disjoint from P_{4} . If vxy is also disjoint from P_{1} , it intersects P_{2} but not P_{4} ; by (ii), contradiction. If |P_{2}|

2D ), they do not cross. By Lemma 5.3 , the long arcs from both machines form a jointly well-nested set. Stage 2: PDA construction. M ’s finite control comprises the state pairs (q_{1},q_{2})\in Q_{1}\times Q_{2} and a buffer B holding at most 8D pending entries, each recording a stack symbol from \Gamma_{1}\cup\Gamma_{2} and a countdown timer in \{1,\dots,2D\} . The buffer contributes a finite factor to the state count: at most (1+(|\Gamma_{1}|{+}|\Gamma_{2}|)\cdot 2D)^{8D} , since each of the 8D slots is either empty or holds a symbol-timer pair. M ’s stack alphabet consists of tagged pairs (\gamma,\mathrm{owner}) with \gamma\in\Gamma_{1}\cup\Gamma_{2} and \mathrm{owner}\in\{1,2\} . At each input position, M simulates both M_{1} and M_{2} on their respective state components. When a simulated machine performs a push, M nondeterministically guesses whether the arc is short or long: 1. Long guess: push the symbol onto M ’s stack, tagged with its owner. 2. Short guess: place the symbol in the buffer with countdown 2D . At each step, all countdown timers decrement. A buffer entry whose timer reaches 0 without being popped causes this computation path to reject. When a simulated machine performs a pop: if the expected symbol is in the buffer, resolve it there; if the top of stack has the correct tag and symbol, pop it; otherwise, reject this path. Completeness (correct guesses accept). Given w\in L(M_{1})\cap L(M_{2}) , the oracle classification from Stage 1 defines a specific guess sequence. On this path: 1. Every short arc (span \leq 2D ) is buffered and resolves before its timer expires. 2. Every long arc is pushed to the stack. By Claim B, long arcs from different machines are jointly well-nested, so the LIFO discipline handles them correctly: nested arcs are pushed after and popped before the enclosing arc, maintaining stack order. Owner tags resolve which machine each symbol belongs to. 3. At most 4D short arcs per machine are simultaneously pending (each spans \leq 2D positions, at most two pushes per position per machine), so the buffer never exceeds 8D entries. Both simulated machines reach accepting states and the buffer empties, so M accepts. Soundness. If M accepts w on any nondeterministic path, both simulated machines accepted w , so w\in L(M_{1})\cap L(M_{2}) . Therefore L(M_{1})\cap L(M_{2})=L(M) is context-free. ∎ Combining Theorem 6.1 and Theorem 6.7 : Corollary 6.8 (Inner segment dichotomy) . Let M_{1},M_{2} be PDAs. Let L=L(M_{1})\cap L(M_{2}) . (a) If there exists a constant D such that every crossing pair on every w\in L has inner segment measure \max(|P_{2}|,|P_{3}|)\leq D , then L is context-free ( Theorem 6.7 ) . (b) If for infinitely many n , some w_{n}\in L has a crossing pair with pump-sensitive linkages and \max(|P_{2}|,|P_{3}|)\geq n , then L is not context-free ( Theorem 6.1 ) . We call this a “dichotomy” in the sense that the two directions identify the governing quantity (inner segment measure rather than crossing gap). The term is exact for block-counting CFLs, where conditions (a) and (b) are exhaustive. For general CFLs, it is conditional: the gap between (a) and (b) concerns whether growing inner segments always carry pump-sensitive linkages (see Remark 6.9 ). Remark 6.9 (Exhaustiveness) . For block-counting CFLs, conditions (a) and (b) are exhaustive: the rigid block structure guarantees that every crossing pair with growing inner segments carries pump-sensitive linkages ( Section 6.6 ), so the dichotomy is complete, recovering Theorem 4.4 . For general CFLs, exhaustiveness is open. The gap is the case where inner segments grow but no crossing pair has pump-sensitive linkages; alternative accepting computations in L_{1} or L_{2} might absorb pumps that would otherwise exit L . Direction (a) is unconditional and requires no linkage assumptions. Direction (b) requires that the specific segment decomposition induced by M_{1},M_{2} ’s matchings produces linkages on L=L_{1}\cap L_{2} . Whether a non-CFL intersection always admits such a decomposition, equivalently, whether there exist PDAs whose crossing structure witnesses the non-CFL-ness via pump-sensitive linkages, remains open ( Section 9 ). We note that no example of a non-CFL intersection lacking pump-sensitive linkages is currently known. Every non-CFL intersection in the literature (block-counting languages, Shieber’s Swiss German construction, positional matching languages) exhibits pump-sensitive linkages on its crossing segments. A counterexample would require two CFLs whose intersection is non-CFL, yet where for every crossing pair with growing inner segments, some factorization touching one linked segment alone still pumps within L_{1}\cap L_{2} . This would mean the crossing segments have enough “slack” that local modifications can be absorbed, despite the global language being non-CFL. Constructing such an example appears difficult: most natural CFL intersection constructions use equality constraints that create tight segment coupling. 6.8 Comparison with the bounded-gap construction The bounded-gap construction ( Theorem 5.4 ) pushes all symbols directly to the stack and displaces at most 2k entries at pop time. When the crossing gap is bounded, the displacement count stays bounded. When the crossing gap is unbounded, displacement may grow without bound, exceeding any finite buffer. Theorem 6.7 succeeds by a different strategy: instead of displacing at pop time, it classifies each arc as short (span \leq 2D ) or long at push time. Short arcs (which include the left-starting arc of every crossing pair, by Claim A) are buffered entirely in finite control; long arcs are pushed to the stack. Claim B guarantees the stacked long arcs are jointly well-nested, since any crossing pair forces at least one arc to be short. The nondeterministic PDA guesses the short/long classification without needing to see the future. 7 Related work 7.1 State complexity of automata intersection Yu, Zhuang, and Salomaa 12 establish that the intersection of two DFAs with m and n states requires at most mn states, tight in the worst case. For unary alphabets, the state complexity is \operatorname{lcm}(m,n) when m and n are coprime, which connects to the Chinese Remainder Theorem. Dutta and Saikia 4 have also connected the CRT to finite automata product constructions. Our Theorem 6.7 extends this line of work to the pushdown case, where the intersection may leave the CFL class entirely. 7.2 Intersection of pushdown automata The intersection non-emptiness problem for two CFLs is undecidable 5 . Swernofsky and Wehar 10 establish tight complexity bounds for deciding non-emptiness of intersections involving regular and context-free languages, connecting these problems to graph-theoretic hardness. Our results complement these decidability and complexity bounds by characterizing the language class of two-CFL intersections: we identify geometric conditions on the crossing arcs that determine whether the intersection remains context-free. 7.3 Mildly context-sensitive languages and LCFRS Vijay-Shanker, Weir, and Joshi 11 introduced linear context-free rewriting systems (LCFRS), which generalize CFGs by allowing nonterminals to derive tuples of strings. An LCFRS of fan-out k generates exactly the k -multiple context-free languages ( k -MCFL); fan-out 1 gives the CFLs. Seki, Matsumura, Fujii, and Kasami 8 independently developed multiple context-free grammars (MCFGs), equivalent to LCFRS. Many non-CFL intersections of two CFLs land in LCFRS(2). For instance, \{a^{n}b^{n}c^{n}d^{n}\} is LCFRS(2) but not CFL; it arises as the intersection of two CFLs with crossing arcs. Whether two-CFL intersections with a bounded number of independent crossing families always lie in LCFRS( k ) for bounded k is an open problem ( Section 9 , Question 7). Our inner segment measure connects naturally to LCFRS fan-out. When \max(|P_{2}|,|P_{3}|)\leq D , the left-starting arc in each crossing pair has bounded span ( \leq 2D ), and the buffer construction ( Theorem 6.7 ) shows the intersection is CFL (fan-out 1). When inner segments grow, each crossing pair contributes an additional “thread” of dependency, suggesting the non-CFL intersection has fan-out 2. 7.4 Crossing dependencies and well-nestedness Shieber 9 proved Swiss German is not context-free via cross-serial dependencies reducible to \{a^{m}b^{n}c^{m}d^{n}\} . Joshi 6 showed crossing dependencies require mildly context-sensitive formalisms. Bodirsky, Kuhlmann, and Möhl 3 formalized well-nestedness , and Kuhlmann 7 established a hierarchy in the LCFRS framework. Our Theorem 4.4 can be seen as an intersection-theoretic analogue: where their work characterizes which single grammars stay within CFL, our result characterizes which pairs of CFL constraints stay within CFL under intersection. 8 Discussion 8.1 Position in the Chomsky hierarchy The inner segment dichotomy places CFL intersection within a graded hierarchy. For finite automata, the intersection of two regular languages is always regular, with mn product states in the worst case 12 . For pushdown automata, our results show the intersection may leave the CFL class entirely. Combined with the LCFRS framework 11 ; 8 : Fan-out Class Intersection behavior Reference – Regular Always closed; mn product states (unary: \operatorname{lcm} ) 12 1 CFL Closed if bounded gap, bounded inner seg., or jointly well-nested ‡ Theorems 5.4 , 6.7 and 4.4 2 LCFRS(2) Non-CFL with crossing arcs (conjectured upper bound) Theorem 6.1 ; Q. 7 ‡ “Iff” for block-counting CFLs ( Theorem 4.4 ); “if” for general CFLs (non-CFL direction requires pump-sensitive linkages; see Remark 6.9 ). For k\geq 3 CFLs, the situation is qualitatively different. The intersection of any finite number of CFLs remains context-sensitive (hence decidable), but every recursively enumerable language is the homomorphic image of the intersection of two linear CFLs 2 : the homomorphism, not the intersection itself, introduces full Turing power. The inner segment dichotomy ( Corollary 6.8 ) characterizes a sufficient condition for crossing the CFL/LCFRS(2) boundary: growing inner segments (with pump-sensitive linkages) push the intersection to LCFRS(2) or beyond, where a single stack no longer suffices and multiple threads of dependency are required. 8.2 Geometry vs. complexity The non-CFL results concern memory access discipline , not memory amount. For the block-counting CFLs central to our examples, both the individual languages and their non-CFL intersection (e.g., \{a^{n}b^{n}c^{n}d^{n}\} ) can be verified in O(\log n) space on a Turing machine by counting and comparing block lengths. The distinction is that individual CFL regularities fit on a stack (LIFO access), while the joint regularity requires non-LIFO access. The inner segment measure captures precisely this: when some inner segment grows unboundedly, the two machines’ stack operations interleave in a way that no single stack can simulate. 9 Open questions 1. Necessity of pump-sensitive linkages. The inner segment dichotomy ( Corollary 6.8 ) is complete for block-counting CFLs but conditional for general CFLs: direction (b) requires pump-sensitive linkages on the crossing segments. If L_{1}\cap L_{2} is not context-free and has crossing arcs with growing inner segments, must some PDA pair (M_{1},M_{2}) for (L_{1},L_{2}) produce crossing segments that carry pump-sensitive linkages on L_{1}\cap L_{2} ? A positive answer would make the dichotomy unconditionally complete. A negative answer would exhibit a non-CFL intersection where no machine-induced decomposition yields the linkage condition, requiring a fundamentally different proof technique (e.g., Ogden’s lemma or the interchange lemma) for the non-CFL direction. 2. Grammar-independent matching arcs. The matching arcs \mu_{M}(w) depend on the specific PDA M and its accepting computation, not on the language alone. Two PDAs for the same CFL can produce different matchings and different crossing structures. Visibly pushdown languages (VPLs) provide a natural grammar-independent notion of matching arcs via a fixed partition \Sigma=\Sigma_{c}\cup\Sigma_{r}\cup\Sigma_{\ell} . What is the intersection theory of VPLs over different partitions (\Sigma_{c},\Sigma_{r},\Sigma_{\ell}) and (\Sigma^{\prime}_{c},\Sigma^{\prime}_{r},\Sigma^{\prime}_{\ell}) ? This may be the most tractable path to a fully grammar-independent characterization, and would also resolve question 1 in the VPL setting (since VPL matchings are determined by the input string). 3. Invariance of crossing measures under PDA conversion. The inner segment bound D in Theorem 6.7 depends on the specific PDAs M_{1},M_{2} and their GNF normal forms, not just on L_{1} and L_{2} . Is the property “there exist PDAs M_{1} for L_{1} and M_{2} for L_{2} such that all crossing pairs have \max(|P_{2}|,|P_{3}|)\leq D ” equivalent to “ L_{1}\cap L_{2} is context-free”? More generally, does every PDA pair for (L_{1},L_{2}) yield the same bounded/unbounded classification of inner segments, or can a different PDA choice change the crossing structure qualitatively? 4. State complexity of the buffer construction. Theorem 6.7 constructs a PDA with (1{+}(|\Gamma_{1}|{+}|\Gamma_{2}|)\cdot 2D)^{8D}\cdot|Q_{1}|\cdot|Q_{2}| states, exponential in D . Is this blowup necessary, or can a polynomial-state PDA be found? More specifically, is the bound tight for any family of PDAs, and can the base or exponent be reduced? 5. Descriptive complexity of CFL intersections. Are there cases where two CFLs have a CFL intersection that requires a strictly larger grammar (more nonterminals or rules) than either component? This would provide a quantitative complexity measure within the CFL class. 6. Indexed languages. Some PDA intersection problems may produce languages at the indexed level 1 rather than at the CFL or LCFRS level. Characterizing which crossing structures produce indexed languages vs. LCFRS languages is open. 7. LCFRS fan-out of CFL intersections. When L_{1}\cap L_{2} is not CFL, it is often recognizable by an LCFRS of fan-out 2 8 ; 11 . Is this always the case for two-CFL intersections? More precisely, does the number of independent crossing families in the matching graphs determine the LCFRS fan-out, and is it always bounded for the intersection of exactly two CFLs? 8. Decidability of bounded inner segments. Given two context-free grammars G_{1},G_{2} , is it decidable whether there exist PDAs M_{1},M_{2} for L(G_{1}),L(G_{2}) such that all crossing pairs have bounded inner segment measure? Since CFL intersection emptiness is undecidable in general, the answer is likely negative, but a proof or a reduction would clarify the computational boundary of the inner segment dichotomy. Declaration of generative AI use During the preparation of this work, the author used Claude (Anthropic) to assist with drafting the text and refining the structure of the mathematical arguments. The author verified all proofs manually and takes full responsibility for the content of the publication. Credit authorship contribution statement Jorge Miguel Silva: Conceptualization, Methodology, Formal analysis, Writing – original draft, Writing – review & editing. Declaration of competing interest The author declares no competing interests. Data availability No data were used for the research described in this article. All results are of a theoretical nature.