The architecture of agreement: from strings to structures

1 Introduction

The phenomena of agreement are ubiquitous in natural languages (NL). In fact, even in those languages that appear to show little to no overt agreement phenomena some operation akin to agreement, operating over abstract features, is posited to exist, especially in generative grammar (Smith et al., 2020). In contemporary syntactic theory, “agreement” covers a wide range of relations between linguistic expressions in a structure (Section 2) formalized under the operation Agree (Chomsky, 2000; Preminger, 2014; Deal, 2023a, a.o.): N-V or N-Adj co-variation of person-number-gender features (in the narrowest sense of “agreement”), Case marking, and other instances of feature-changing rules. We want to address the question of why agreement seems to be so fundamental to NLs. We take a dynamical systems perspective and offer an argument for why agreement, regardless of its manifestation, is an essential aspect of NL grammars. It is a common observation that agreement instantiates redundancy, making a signal robust against noise (e.g., Schlechtweg, 2025). The perspective adopted in much work on the importance of redundancy in language is based on communication and acquisition: languages are shaped by communicative needs. In this context, morphological agreement can be seen as a device that facilitates learning by providing redundant cues (Tal and Arnon, 2022). Deal (2023a,b) provides a functionally-informed generative approach, also focused on the communicative advantages provided by redundancy creation in addition to the elimination of LF-uninterpretable features. The challenge, in Deal's view, is for the grammar to balance redundancy against economy. Our viewpoint, while not contradictory, is different from those. Instead of an information-theoretic or communicative approach, we adopt a structural perspective. We aim to show that, in addition to its role in making a signal robust to noise by introducing redundancy, agreement has an important function as a means to restrict the set of structural descriptions that can be assigned to a linguistic string. Structure determination reduces the need for overt markers of redundant information, but definitely does not eliminate the need for them, as they play complementary roles.

Our contribution, then, is focused on the role of agreement in mediating the relation between strings and the structures assigned to these strings. Specifically, we contend that agreement provides information necessary for a parser to identify a restricted class of possible generators for a linguistic signal (and therefore to assign structural representations to sentences). We are concerned with the role of agreement in solving what Haider (1996) calls the “projection problem,” understood in our case as a general problem in signal analysis (cf. also Peters, 1972):

the projection problem for a given natural language L, [is] the function from one-dimensional expressions (= a string of terminals of L) to an at least two-dimensional expression (= the grammatical structure of the string).

A solution to this problem involves operating on signals via segmentation and labeling, extracting symbols (basic and derived expressions) that match to some internalized alphabet, and determining the structural relations that hold between those symbols in the grammatical structure.

Importantly, the problem of relating strings to underlying generators is not exclusive to linguistics. When we consider the symbolic encoding of dynamical systems (Section 2), an area where the problem of relating strings to complex processes has been pursued most fruitfully, we find that observable regularities in a string allow us to detect reliable relationships in local aspects of the dynamical system being modeled. In this way, tracking recurrent regularities in output signals provides valuable information about underlying dynamics, insofar as these regularities are determined by the system whose dynamics are being encoded. For instance, suppose that we are encoding the movement of a pendulum in 2D across two regions in terms of 1s and 0s, where if at time t the mass is in the red region, we write that down as a 1, and if it is in the green region we write that down as a 0. Time is discretised, and measurements are taken at regular intervals (Figure 1):

Given a string of 1s and 0s we can reconstruct the movement of the pendulum between some time t_*i* (which corresponds to its position as encoded by the first symbol) and some time t_*i*+*m* (which corresponds to its position as encoded by the last symbol). If the output string is a continuous sequence {10}^* (a regular language), for example, we can assert that the mass oscillated uniformly between the regions, starting from the red one. A higher density of 1s than 0s or vice versa would indicate that the mass has spent more time in one region than the other, possibly due to some external perturbation. This case is very simple, but illustrates well that the complexity of the output string depends on the complexity of the underlying dynamics and that, if we know something about the mode of encoding, we can reliably reconstruct aspects of these dynamics.

In the study of natural language acquisition linguists are faced with the problem of providing a mechanism that allows children to project an internalized grammar from primary linguistic data, a problem we will refer to as grammar inference (Wharton, 1974; Adriaans and van Zaanen, 2004). Inferring a grammar from data implies constructing a finite specification of an unbounded stringset, a specification that, minimally, allows us to determine the well-formedness of novel strings with respect to some set of constraints (de la Higuera, 2010, p. 27). When acquiring a language, humans do not develop representations of individual strings; rather, they develop finite representations of languages which can be used to determine the well-formedness and (if applicable) interpretation of known and novel strings. Given the fact that humans can use language to communicate, it seems reasonable to conjecture that individual representations of languages converge such that intuitions about sentence well-formedness are shared between speakers. This is a form of the membership or decidability problem: how to determine, given a novel string, if it belongs to a target language. Linguists impose the additional condition that a grammar must associate to each recognized string a structural description, which specifies the hierarchical relations between indexed expressions in the string (cf. Chomsky, 1965, p. 31). In computer science, these structural descriptions often take the form of a parsing tree or an annotated dependency graph. A further requirement is that structural descriptions must be appropriate (Joshi, 1985, p. 207–208): they must not assign more or less structure than necessary to characterise the relations between expressions in that string. The problem of appropriateness will become especially relevant in Section 3.1. The question arises, then, of how strings are associated to their structural descriptions, and whether information present at the string level can help restrict the space of possible structural descriptions associated with any given string. This paper is an exploration of the role of agreement in the process of humans identifying structural descriptions compatible with the input, i.e., solving the problem of grammar inference for NLs. We will contribute to the understanding of how the space of possible grammars is restricted by focusing on the role of a specific grammatical phenomenon, agreement, in solving the problem of approximate grammar identification.

The paper is structured as follows: Section 2 defines and illustrates agreement in NL, introducing the concepts of structure dependency and locality in relation to agreement. Section 3 elaborates on these notions arguing that they are in fact characteristic of a class of phenomena: complex dynamical systems. The section explores how dynamics can be compressed via symbolic encoding into languages and argues that in order to provide adequate characterisations of the systems they represent, grammars must allow for a wide range of relations between basic building blocks, up and down the Chomsky hierarchy. Dynamical systems and natural language grammars are shown to share a fundamental property called mixed computation, whereby local descriptions of structure may vary in computational complexity. The interaction between mixed computation and compression is expanded on in Section 4. We develop the idea that if one wants to reconstruct rich underlying dynamics from encoding strings, the system must deliver ways to restrict the class of structures consistent with superficial relations between symbols. This is the core of a workable approach to grammar inference. Building on examples from artificial grammars that encode dynamical systems that transition into chaotic behavior, we argue that agreement in NLs provide such restrictions in the absence of properties such as self-similarity.

Addressing the problem of grammar inference requires us to make some preliminary assumptions. We need to assume, for example, that a grammar that generates the relevant stringset is available in the solution space (Wharton, 1974). For example, if our solution space contains only context-free grammars, but we are examining a strictly context-sensitive language, there will be no solution to the grammar inference problem. This is a particularly relevant issue: for any “learner” (human or machine), we want the solution space to be rich enough so that a finite characterization of a language can be found for most cases, but also restricted enough that the problem of grammar inference is tractable. In general, exact grammar identification is rarely practical (or indeed possible). However, an easier version of the problem is to find a grammar that characterises the target language up to a certain degree of precision: this is approximate grammar identification. Approximate grammar identification is inherently noisy, with noise being proportional to the difference between the language generated by our candidate grammar G(L) and the target language L_T. Settling on a candidate grammar becomes, to an extent, the result of a cost-benefit analysis whose parameters are determined by independent constraints on the system that carries out the procedure (in the case of humans, we have cognitive and physiological factors, e.g., working memory limitations, metabolic and energetic considerations, time constraints). It should furthermore be noted that the term “inference” has different interpretations based on the reader's discipline, and plays different roles based on specific research questions. For our purposes, “inference” pertains to both the analysis of the output string and the underlying complex dynamical system, made available by the physiology, that ultimately the string is characterizing (cf. our pendulum example above, also Section 2.1). When confronted with an input, one must, among other things, “infer” the most efficient way of adequately integrating and interpreting the incoming signal, characterizing observed properties and predicting possible behavior. In Section 2.1, “efficiency” will be explored in terms of language complexity. Inference here refers to the process of delineating the space of possible grammars compatible with the input, thereby simplifying the challenge. In this context, we will argue that agreement serves to further restrict the class of adequate structures consistent with string-level information (Section 3.1). As mentioned above, the relevant notion of adequacy is based on Joshi (1985, p. 207–208):

A grammar G is weakly adequate for a (string) language L if L(G) = L. G is strongly adequate for L if L(G) = L and for each w in L, G assigns an ‘appropriate' structural description to w.

Such “appropriate” structural descriptions assign no more and no less structure to strings than what is necessary to account for observed behavior: assigning richer structure predicts the applicability of specific syntactic operations (e.g., reordering rules) and semantic interpretation rules. In imposing a condition of “appropriateness” so defined, the aim is to restrict language/grammar-theoretic complexity (in the sense of Chomsky, 1959). For example, as observed in Chomsky (1961), Chomsky and Miller (1963), Lasnik (2011), Krivochen (2015, 2021), and Lasnik and Uriagereka (2022), context-free phrase structure grammars assign “too much structure” to cases of intensive iteration (as in An old old old man arrived) or “true coordination” (as in The man was old, tired, tall …, but friendly). For these cases, a regular grammar suffices. However, regular complexity cannot appropriately characterise the structure of the sentences in which these local objects are inserted. We will see that analogous conditions on locally reducing complexity are assumed in the literature on symbolic encoding (Crutchfield and Young, 1989; Günther et al., 1994). We will argue that inference operating locally is the foundation of agreement phenomena in NL.

Above, we mentioned that, while the problem of grammar inference has been mostly studied in the context of the symbolic encoding of dynamical systems, another version of it is the well-known problem of language acquisition from limited input (de la Higuera, 2010, Section 1.1.1), which exists at the crossroads of computational grammar inference (Adriaans and van Zaanen, 2004), psycholinguistics, and cognitive neuroscience (Gold, 1967 provides an early overview of interdisciplinary implications of the study of language identification from finite inputs). Much has been made of the argument from poverty of the stimulus in generative linguistics, which essentially states that the primary linguistic data a child is exposed to is insufficient to fully account for its ability to produce and comprehend novel sentences (Chomsky, 1955, p. 61). In other words, as Lasnik and Lidz (2016) put it, “our experience far underdetermines our knowledge,” in terms of quantity of data and time available to acquire the grammar of a language. Chomsky's response to this problem (which he called Plato's problem, cf. Chomsky, 1986a) was to account for the difference by means of an articulated system of innate knowledge, the human-specific Faculty of Language. While the generative linguistic literature has remained disconnected from the literature on grammar inference in dynamical systems, they are indeed explorations of the same underlying mechanisms, when viewed at an appropriate level of abstraction. The general problem of grammar inference is not divorced from what we mean in linguistics. We contend that the reason that agreement relations seem to be a core component of all NLs is because the structural conditions that license these relations are an essential part of the evolution of a dynamical system that is constrained by cognition and physiology. In turn, by recognizing agreement relations, it is possible to approximate a reconstruction of the dynamics that generated the structural conditions that license agreement.

2 Defining agreement

Let us begin with some basic linguistic considerations about agreement. The core cases of agreement involve dependent marking, canonically on NPs, that reflect some aspect of their syntactic relation to a predicate, be it lexical (V, A) or functional (INFL, C). In general, there is a relation of value identity, for shared attributes. The examples in (1) illustrate covariation of person-number(-gender) features, so-called phi-agreement:

• 1) a. Spanish
• Las mujeres trabajadoras llegaron cansadas
• The.Fem.Pl woman.Pl hard-working.Fem.Pl
• arrive.Past.Perfective.3Pl tired.Fem.Pl
• “The hard-working women arrived tired” (Adj-N concord,
• N-INFL agreement; cf. Chomsky, 2001)
• b. West Flemish (from van Koppen, 2017)
• K peinzen da /^*****dan dienen student nen buot gekocht eet.
• I think that-3p.sg/^*that-3p.pl that student a boat bought has
• “I think that that student has bought a boat.”
• (Complementiser agreement: C agrees with the subject of
• the embedded clause)

Extensions of agreement would cover other aspects of morphological selection, as in causative structures (Baker, 2013): in English, a causative verb selects for an infinitival embedded clause (He made him cry, not ^*He made him crying). Agreement between two functional categories is also attested: for example, in Irish, complementiser agreement is sensitive to the tense of the embedded clause it introduces (we have a C-T Agreement relation):

• 2) Irish (from van Koppen, 2017)
• a. Deir sé go dtógfaidh sé an peann.
• Say.Pres he that take.Fut he the pen
• “He says that he will take the pen.”
• b. Deir sé gur thóg sé an peann.
• Say.Pres he that.Past take.Past he the pen
• “He says that he took the pen.”

In this paper, we adopt a broad definition of agreement: a group of non-primitive morphosyntactic relations between co-varying expressions within and across local domains.¹ By non-primitive we mean to exclude relations like grammatical functions, which have been convincingly argued to not be biunivocally tied to morphological marking or syntactic position (e.g., Perlmutter and Postal, 1983). Within local domains, we have for example nominal concord (Carstens, 2000, p. 323; Chomsky, 2001) and head marking. Across local domains we have dependent marking, where the marking head and the dependent belong to different extended projections (Grimshaw, 2000), and morphological selection from the head of an extended projection to another (as in complementation structures, and chains of auxiliary verbs, cf. García Fernández et al., 2017). For example, if DP is the extended projection of N, and IP/TP is the extended projection of V, assignment of Accusative Case to the lexical head of DP when V c-commands DP involves the heads of both extended projections. Nominative Case assignment involves a category in the extended projection of V (namely, I/T) marking the lexical head of DP. We leave out of the present discussion semantic characterisations of agreement. So defined, agreement provides to interpretative systems instructions of (at least) two kinds:

• It signals that syntactic terms are connected – at some point, they must have belonged in the domain of locality of the grammar, since by definition the domain of locality of a grammar is the domain within which all syntactic relations are established (Kallmeyer and Joshi, 2003; Abeillé, 1990)
• It specifies the nature of their connection (phi agreement, Case marking, C agreement…)

In most accounts, agreement is a fundamentally asymmetric relation. Corbett (2006) introduces this asymmetry in terms of a controller and a target: in the case of subject-verb agreement, the verb agrees with the subject, not the other way around. The subject is then the controller and the verb, the target. Corbett (2006, p. 7, ff.) distinguishes controllers, which display a copy of shared morphological marking, from governors, which dictate marking on other expressions but do not display those features themselves. Case assignment would fall under government. The asymmetry is also captured in generative grammar in terms of governors in the GB tradition (Chomsky, 1981, not to be confused with the use of government in Corbett's work), and probes and goals in Minimalism (Chomsky, 2000). As is customary in Generative grammar, Case is considered part of the agreement system. Chomsky (1986b) includes Spec-Head relations within “agreement” (specifically, between the subject and the head of INFL), and proposes that any category agrees with itself and with its own head. In late GB, the same projections (AgrS and AgrO) mediated Subject and Object agreement, respectively, as well as Nominative and Accusative case assignment (Chomsky, 1995, Chapter 2). Using Corbett's terms, AgrS would be a target for person-number agreement and a governor for Nominative Case assignment. In late GB, Case and agreement were explicitly seen as two sides of the same coin: given a feature F, if F manifests in both XP and H (XP a phrase in Spec-H), we speak of agreement. If only on XP, it is Case (Chomsky and Lasnik, 1993, p. 561).

In all cases, the systematicity of covariance in agreement is tied to specific structural conditions that must hold for the agreement relation to take place: there is a domain of agreement, the syntactic environment in which agreement occurs (Corbett, 2006, p. 4). These structural conditions have been the focus of much research in formal linguistics and psycholinguistics (Acuña-Fariña, 2009 provides a general overview). In the context of a discussion of attraction effects in psycholinguistics, Franck et al. (2006) introduce the notion of “unit of syntactic encoding” from Bock and Cutting (1992): for attraction effects to occur, the attractor and the head noun should be part of the same “unit of encoding” (Franck et al. observe that the position of an attractor in the syntactic hierarchy and the structural distance between attractor and finite verb must also be considered). In Bock and Cutting's work, the “clause” is taken as the fundamental unit of encoding, without much linguistic discussion, but syntactic theory has provided many a definition for domains of locality. Consider, for example, Chomsky and Lasnik's (1993) complete functional complexes, Dalrymple's (1993) minimal complete nuclei, Chomsky's (2000) phases, and Lexicalised Tree Adjoining Grammar's elementary trees (Frank, 1992). An elementary tree, given a lexicalised domain of locality, is the extended projection of a single lexical head, called the anchor of the elementary tree. Thus, an elementary tree anchored by a verb will contain not only the c-projection of that verb (i.e., VP), but also the extended projection of that verb (cf. Abney's, 1987 s-projection; also Grimshaw, 2000): IP, and CP. This is the syntactic domain over which syntactic dependencies governed by the V and heads in its extended projection can be defined.

3 Locality and mixed computation

The kind of rich local structural dependencies we have described is not unique to language: they appear in various systems at different scales. We propose that locality shows up in grammar because grammars are characterisations of systems whose (computational) behavior is best described locally. If we consider systems that evolve in time, and that evolution delivers changes in the system's behavior that require a change in the formal devices that characterise it, global characterisations are not useful. Rather, we could focus on periods in the evolution of the system to which a single kind of computational characterization (e.g., defined in terms of language/grammar complexity) applies as the system's “domain of locality.” Changes in the dynamics will then correspond to changes in the formal devices required to appropriately characterise the system's behavior. In this section we will see how shifts in computational complexity are characteristic not only of a certain class of dynamical systems, but also of NL syntax. Furthermore, we will argue that there are computational and empirical advantages to assigning the simplest description compatible with the local data in both dynamical systems and NLs, even if more powerful descriptions are available. The characterization of language complexity of a system, as delivered by symbolic dynamics, should always start with the simplest description, only shifting to more powerful descriptions if the behavior of the system becomes more complex as a result of phase transitions.

Locality in the characterization of dynamical behavior is a standard problem in the domain of dynamical systems theory, and is reflected in their symbolic encoding, that is, in the translation of complex dynamics into strings. Let us flesh this out. Consider a system whose evolution is dictated by recurrence relations of the general form

• 3) x_*n*+1 = f (x_*n*)

where {x_*i*, x_*j*, …x_*n*…, x_{*n* + *m*}} is the set of state variables. (3) is called a discrete map. Typically, the evolution of the system will be determined also by a (possibly unary) set of system parameters p, giving us:

• 4) x_*n*+1 = f (x_*n*, p)

For example, if we want to model the changes in a certain population, we not only need to know how many creatures exist at some time x_*n*, but also have some parameter that tells us, say, how fertile this population is. This fertility parameter will remain constant, even as the values of x vary as time goes by.

The behavior of a dynamical system of the general form (4) at a fixed point can be encoded as a string of symbols, given a discretisation of time, a partition of the phase space and a function that assigns distinct symbols to each region of this partition (Politi, 1994). Note that the partition will necessarily be coarser than the actual dynamics of the system: at the very least, the dynamics internal to each region will be “flattened” into a single symbol. Then, a trajectory through the phase space can be expressed as a string. This is a symbolic encoding of (a state of) the system: a compressed 1D representation of the dynamics for a certain value of a continuous parameter. If the behavior of the system changes drastically as a threshold value for p is reached (e.g., showing different patterns of organization), we are in the presence of a phase transition. For example, if we have water molecules and our parameter is temperature, phase transitions correspond to states of matter: solid (ice), liquid (water), and gas (steam). Looking at dynamical systems in terms of the strings that encode their dynamics is of particular interest because we can provide language-theoretic characterisations of these systems, ask questions about the grammars that can generate the relevant stringsets, and explore common properties between those grammars and the formalisms that characterise NLs.

Crutchfield and Young (1989) (also Langton, 1990) observe that phase transitions in dynamical systems may trigger computational shifts to higher levels of computation (in what Solé et al., 1996 call second order phase transitions and noise-induced phase transitions). In the relevant cases, as the value of a parameter p is modified, the system undergoes a drastic change as critical points are reached: bifurcations, catastrophes (in the physical sense), interactions between local and global conditions, etc. deliver discontinuous transitions and the behavior of the system displays properties that cannot be directly derived or predicted from the initial conditions and deterministic equations of motion or recurrence relations. Complexity and computation appear around unstable points, specifically in the transition between order and chaos, called the “edge of chaos” (Crutchfield and Young, 1989; Bertschinger and Natschläger, 2004).

The logistic map provides a relatively simple example of a system that requires computational shifts of its characterizing grammar(s), with different regions being characterized by grammars of varying complexity. Consider the discrete system defined by the following recurrence relation:

• 5) x_*n*−1 = rx_*n* (1–x_*n*)

This equation has been used as a model of population growth in computational biology (May, 1977). 0 < x_*n* < 1 is the ratio of existent population to maximum possible population, and r is an adjustable fertility parameter. The diagram below represents the behavior of the system as the value of r changes: the x-axis represents the value of r, whereas the y-axis represents the stable solution(s) that the system stabilizes around after a finite number of iterations (i.e., the fixed points of the map). If, given a certain value of r, the system stabilizes around a single value, there is going to be a single value of y for that value of r. However, if the system stabilizes around more than one value (e.g., oscillating between 2 or more as we keep iterating the map), given a single value of r there will correspond more than one value in the y-axis. Note that the value of the adjustable parameter r determines the overall behavior of the system. The change between linear behavior and bifurcations exemplifies a phase transition. Figure 2 illustrates the behavior of the logistic map for 2.4 < r < 4:

Symbolic encoding translates the dynamics into a binary string, iterating the map at fixed points and defining a threshold condition: if f (x_*n*) is greater than the threshold t, put down a 1. If smaller than t, put down a 0. Formally, with a threshold of 0.5, we write

s(xn)={1 if xn ≥ 0.50 otherwise.

As emphasized before, this procedure involves compression of information: we are partitioning the phase space into two regions, keeping track of when the trajectory defined by the dynamics falls within each region, and encoding this as either 1 or 0. This procedure “forgets” the specific values, favoring a coarse representation of the system's behavior with respect to t. We repeat this procedure for different values of r. We now have a set of strings, each of which corresponds to a specification of the system's stable value(s) for a specific value of r. The language that characterises this system is the set of all strings that are characterisations of the dynamics for all values of r within an interval of interest (Figure 3):

Each horizontal level in Figure 3 represents the dynamics of the system as r changes, and diagonal lines represent shifts in the dynamics as r increases, with the strings becoming progressively more complex as r approaches the Feigenbaum point (r ~ 3.56995). At that point, the system is said to be at the edge of chaos. As we will see in Section 4.1, the symbolic encoding of a dynamical system like the logistic map can be characterized by a class of recursive rewriting grammars known as Lindenmayer systems (L-systems). This is important, because a growing body of literature has found learning effects with a restricted class of L-systems in AGL experiments across modalities (Saddy, 2009; Vender et al., 2019, 2020; Compostella, 2024; Schmid et al., 2023, among others). The grammar that characterises the bifurcation route to chaos is the L-system called the Feigenbaum grammar (“Fig” henceforth) in the references just cited, defined as follows (cf. also Günther et al., 1994, p. 637):

• 6) 0 → 11
• 1 → 01

Developing these rules generates the language diagrammed in Figure 3. Translating dynamics into sequences of symbols is crucial to our purposes. Once symbolic encoding delivers stringsets, we are in the domain of languages and grammars. We will say, then, that a certain grammar characterises a route to chaos if, at the limit, it generates a string that characterises the behavior of a dynamical system at designated points in its transition to chaotic behavior (e.g., at the edge of chaos). In this sense, the Fig grammar characterises the bifurcating route to chaos.

In this context, it is crucial to note that language complexity is intrinsically related to the complexity of the underlying system (Günther et al., 1994). Moore and Lakdawala (2000) show that each of the encoding strings (0, 1, 10, 1011, …) is regular, but the language of all such strings is beyond regular capacity. Complexity arises at so-called critical points: in the logistic map, when r ≈ 3, we find the first bifurcation. This requires a change in the power of the system used to model the dynamics: regular grammars for linear convergence and context-free grammars when bifurcations appear (Binder and Ellis, 2016). Another, more drastic, change appears when r ≈ 3.5669…: a deterministic equation gives rise to chaotic dynamics. With the emergence of chaos comes yet another computational shift: the simplest generator that can produce all and only strings for values of r greater than 3.5669… is beyond context-free power. Chaos brings about a drastic change in the computational capacities of the system, that is, the capacity to store, transform, retrieve, and transmit information. Chaotic systems are too unstable and have very short transients (which means that information gets dissipated very quickly) and error signals that grow exponentially with time (Gade and Amriktar, 1992; Günther et al., 1994). The operations available at the edge of chaos, where arbitrarily longer transients (which preserve local information for arbitrarily long times) and restricted instability allow for computational behavior (cf. Wolfram, 1984; Langton, 1990) that allow us to define operations over local stable structures, are no longer possible once the system falls into full chaos.

To summarize: computational fluctuations, as driven by phase transitions, are characteristic of nonlinear dynamical systems. These fluctuations are reflected in the symbolic encoding of the system: they manifest at the level of strings, providing information about the dynamics that these strings characterise. Note, crucially, that computational fluctuations are not enough to define NL. The symbolic encoding of the logistic map does not feature anything comparable to agreement as defined for NLs. In both cases, strings compress underlying dynamics and, as we will see, in both cases there are computational fluctuations, but to get natural languages we have more ingredients: we need not only shifts in computational complexity but also a restricted set of structural relations delivered by a grammar and an alphabet of expressions that externalize these relations. Our point is that the computations needed to support language (and other higher cognitive functions) become available at the edge of chaos. Once a system moves into a fully chaotic regime, information dissipates, noise grows exponentially, and the kind of restrictiveness characteristic of NL grammar is no longer available. In chaotic regimes, representations are not stable enough to be stored, operated over, and retrieved. In contrast, and for completeness, systems that do not transition into complex behavior but rather tend to equilibrium (e.g., Class 1 cellular automata in Wolfram's, 1984 classification) do not allow for information transformation at all: the cost of having no information loss at all is that they are too rigid and incapable of adaptation.

In the process of constructing structure that represents the formal relations established between segments, it is essential to distinguish information from noise. Saddy (2024) observes that for all signals, the information-to-noise ratio is a property that needs to be managed. He distinguishes between two kinds of noise:

• - Linear-based noise: this is a core property that drives signal encoding and decoding in both language and (in our case) binary strings. It refers to “errors” that appear at the string level, possibly segments that cannot be accommodated with otherwise successful heuristics. If the noise becomes too prevalent or too strong, the heuristics must be adjusted, with extreme cases possibly requiring going back to first principles and reattempting sampling.
• - Structure-based noise: in binary strings, this refers to dependencies between different hierarchical levels (see Schmid, 2023 for an exploration of this kind of noise in L-systems). In NL syntax, an example is quantifier scope interactions. Overcoming structure-based noise requires principles of a different nature. Sloan (1991), for instance, formulates a constraint to the effect that QR paths must embed but not intersect. This is an example of structure-based noise, as QR has no effect on the linear ordering of constituents.

Both cases reflect structure preservation, an emergent property of non-linear recursive systems. The tension between structural and information-theoretic noise will be a driver for language change, and a factor in language acquisition.

Crucially, Saddy recognizes the existence of noise that combines both linear-based and structure-based; call this “complex noise.” In binary strings, complex noise arises when there is a contention between possible constituencies, in overlapping n-grams. In such cases, the parser attempts to resolve ambiguities whereby a segment could belong to more than one chunk. Each chunking hypothesis in turn delivers different factorisations of the binary string, mutually incompatible (giving rise to a dynamical frustration).

We built on these observations to claim that agreement is at the interface of structure and linear based noise, as a redundancy measure that emerges from the dynamics and makes the system robust against both. Literature exists that addresses the impact of external sources of noise in language comprehension and the role of redundancy in helping speakers successfully interpret language in noisy conditions. This is not the same kind of noise considered here: if a specific heuristic is entertained for a signal, we would call noise new information that cannot be accommodated under current heuristics. To give a very simple example, given the following string, presented one symbol at a time,

the characterization “alternating 1s and 0s” (formally, the regular expression {10}^*, where ^* is the Kleene star) is valid until the sixth symbol (a 1 following another 1): that sixth symbol is an instance of string-based noise under current assumptions, and forces us to change our characterization of the string.

If we step back, we see that there are good conceptual reasons to look at the relations and properties that appear in the study of dynamical systems when addressing the inner workings of NL grammars and the grammar inference problem. Let us consider two main points. First, and most programmatically, we are looking at language behavior, which is supported by the brain. Whichever the specific relations between those two turn out to be, it is clear that the brain is a dynamical system (Freeman, 2000; Breakspear, 2017). Looking at relations and properties that appear in dynamical systems will surely give us insight to formulate a plausible linking hypothesis. Second, and more specifically, the idea that locality effects correlate with fluctuations in computational complexity (well-established in dynamical systems theory) has also been fruitfully applied to NL syntax. In this view, the structural description assigned to a well-formed sentence may contain subunits of different computational complexity (Krivochen, 2015, 2021), with changes in complexity defining local syntactic domains (cf. also Uriagereka, 2002). Phase transitions are thus transitions between different levels of language-theoretic and grammatical complexity. The literature on symbolic encoding has explored similar ideas. Günther et al. (1994, p. 636) conjecture that an effective classification of complex behavior could be through the kind of language required to capture a system's dynamics, focusing on systems capable of storing, retrieving, transforming, and transmitting information.

3.1 Mixed computation in syntax

Let us see how the idea of computational fluctuations can be applied to NL syntax. Consider the case of adjectival iteration, as in

• 7) An old old man

Already Chomsky (1961) and Chomsky and Miller (1963, p. 297–298) recognize that a PS grammar assigns structural descriptions that are too complex for cases of iteration (see also Lasnik, 2011, p. 361). The best course of action seems to be to allow for restricted regular dependencies, such that instead of the monotonically growing (8a) we get a structural description like (8b), where [old old] is a regular expression and there is no hierarchy between old tokens (but there is between the regular expression and the N head it modifies):

• 8) a. [an [old [old [man]]]]
• b. [an [old old] [man]]

In terms of trees, we replace a structural description like (9a), corresponding to the case where each token of old is the head of its own phrase with a structural description like (9b), where the regular expression {old old} modifies the N head as a unit:

• 9)

But consider now the fact that grammars and languages are structured in an inclusive hierarchy (Chomsky, 1959), such that PS grammars can generate all regular languages. One may ask why we can't simply assume the most powerful computational mechanism possible and apply it across the board. There are two main problems with such a view. First, as emphasized throughout the paper, in the study of syntax we want adequate structural descriptions to be assigned to strings, where their adequacy is measured in terms of making predictions about other possible configurations and deriving compositional semantic interpretations. A uniform PS analysis of iteration erases all syntactic and semantic differences between (8) above and (10) and (11) below:

• 10) The UK is a big small country (i.e.: “it is big for a small
• country,” the semantic value of big applies to the semantic
• value of small country)

• 11) That's fake fake news (two interpretations available:
• intensive reduplication or recursive modification)

Additionally, under structural uniformity certain contrasts remain unexplained. For instance, in (12) below neither example allows for an intensive reading, and whereas that is fine for fake fake (since there is an alternative structure available), old old becomes much harder to interpret:

• 12) a. Fake is what the fake news was
• b. ??Old is what the old man was

This contrast is unexpected if there is a single structural template assigned to all sequences of the form Det + Adj + Adj + N (cf. Scott, 2002), but can receive an explanation if extraction from a regular expression works differently than extraction from a richer structure (Krivochen, 2021). For example, if (11) receives a structural description like (9a), each fake is a different syntactic object which can be individually targeted by reordering rules. Extraction of one old is not possible in (9b), as they both constitute a syntactic terminal. Structural uniformity compresses information too much, to the point that relevant internal dynamics for purposes of syntactic operations and semantic interpretation are eliminated.

If there are multiple available modes of information organization, where do we start looking? As Crutchfield and Young (1989) emphasize,

if one is careful to restrict the class of computational models assumed to be *the least powerful necessary to capture behavior*, then much of the abstract theory of computation and complexity can be constructively implemented (Our highlighting. cf. also Günther et al., 1994, p. 637)

We contend, following Crutchfield and Young, that the “start small” strategy (i.e., given a string, start by assuming the simplest possible computational device as a model and only depart from it given sufficient negative feedback) is at the core of a workable solution to the grammar inference problem. Reducing (language-theoretic) complexity, as highlighted by Günther et al. (1994) is a way to find the simplest description compatible with the data. When exploring the space of possible generators, the simplest compatible grammar must be assumed unless there is sufficient evidence to the contrary: in this view, formal descriptions are attractors in the space of solutions. In the linguistic case briefly analyzed above (see Krivochen, 2021 for more details), starting small allows us to capture the local dependencies of intensive iteration, pushing us to richer representations when flat structures fail to represent dependencies that matter for both syntactic and semantic purposes. Consider the case of the assignment of structure to an external signal, to which we will return with a concrete example in Section 4.1. If evidence in the signal supporting a certain kind of dependency between local units is deemed strong enough to converge on a specific formal characterization (a structural description), destabilizing the system in a way that forces a change in computational complexity requires a sufficiently large perturbation, which above we referred to as phase transitions. For NL, evidence of these perturbations come in the form of two kinds of inconsistencies between structures and signals:

• a. The current structure being entertained as a formal characterization of an input is too weak to capture behavior (perhaps because it overly compresses information and, in this process, important internal dynamics are lost). As examples, consider the limitations of FS descriptions to adequately characterise agreement across unbounded structure (Chomsky, 1957, p. 22) while assigning structure of the right complexity to account for attested syntactic behavior (i.e., constituent structure). Shieber (1985) discusses data from embedded clauses in Swiss German that shows restricted crossing dependencies between two categories (N and V). He argues that a strictly context-free analysis is linguistically and formally inadequate for these cases.
• b. The current structure being entertained as a formal characterization of an input is too powerful and predicts unattested behavior. As has been repeatedly observed throughout the history of generative grammar, there are cases to which CF grammars assign too much structure, which predicts non-existing dynamics/operations [e.g., the availability of extraction of one instance of old in (12b)].

The idea that the solution to the problem of grammar inference in NLs (just like in physical systems) explores a space populated by models of different computational complexity stands in conflict with the idea, well established in generative grammar, that syntactic structure is universally uniform. Starting from X-bar theory in Chomsky (1986b) to Merge in Chomsky (1995) and Simplest Merge in Chomsky (2021, 2024), all structure is created equal, obeying strict binarity (in branching or set formation) and relying on a conflation between selection and projection (such that if X imposes restrictions on a property of Y, then the projection of X dominates the projection of Y). Both of these aspects have been challenged in the syntactic literature on theoretical and empirical grounds. Empirical arguments against templatic monotonic syntax can be found in Borsley (2005) for coordinated structures, Uriagereka (2008), Lasnik (2011), Krivochen (2015, 2021), and Lasnik and Uriagereka (2022) for iteration (of adjectives and adverbial adjuncts), Krivochen and García Fernández (2019) for auxiliary chains in Spanish, among others (see also Borsley and Börjars, 2011). Crutchfield (1994) and Lakdawala (1996) emphasize that even though Turing Machines embed all other modes of computation, “it might be wiser to look at the entire hierarchy of machines that computation theory provides us with” (Lakdawala, 1996, p. 4477). The same can be said of NL syntax. Despite the consensus being that mildly context-sensitive grammars are enough to characterise the syntax of natural languages, the analysis of (7) and (10–11) suggests that we should consider a wider range of structures at different levels of complexity when assigning structural descriptions to NL sentences. For our current purposes, it is important to point out that, if structural uniformity was truly the norm for NL grammars, it would separate NLs from physical and biological systems: in the latter two, computational oscillations are the norm.

In addition to empirical inadequacies observed in the literature, structural uniformity makes the problem of grammar inference (and indeed, information processing) harder to solve, somewhat counterintuitively. One may think that if there is a single template available, grammar inference should be a non-issue. However, the issue is more complex than this oversimplified picture suggests. Forcing all data into a single fixed template, as noted above, may either erase internal dynamics or fail to properly represent them: we don't just want any structural description to be assigned to input sentences, but adequate structural descriptions (cf. Joshi, 1985, p. 207–208) that capture syntactic-semantic relations without assigning too much structure. Too much structure predicts the availability of dependencies and operations that may not actually obtain [cf. our remarks about (12a, b)]. Let us see another example. A strict binary-branching requirement for linguistic structures multiplies invisible structure in the form of nonterminal nodes. Jackendoff (2011) takes issue with the idea that structural uniformity in the form of binary branching simplifies acquisition. Consider:

• 13) a. [A B C]
• b. [A [B C]]
• c. [[A B] C]

Which structural description is a priori preferable? The choice is not obvious:

If UG stipulates that the branching is always binary and in a uniform direction, say [(13c)], then the learner does not have to decide which is correct. Therefore […] binary branching is simpler for the learner. However, another simple possibility is that UG stipulates minimal embedding, that is, the flat structure [(13a)], as the default in the absence of evidence, and that the learner only imputes structure where the evidence pushes in that direction. Neither stipulation requires more of the learner than the other. (Jackendoff, 2011, p. 279)

Encoding structural uniformity in the initial state of the system leads to a procrustean relation with incoming data: only data that conforms to the initial template can be recognized. The alternative is to allow for flexibility in the initial state, covering a wider solution space, and encode computational modes as attractors, which can be escaped from if necessary. This effectively puts the system in charge of solving grammar inference in a delicate equilibrium between rigidity and adaptability, an interaction between mutually incompatible requirements that is well-known in the class of complex systems based on dynamical frustration (Binder, 2008; see Gollo and Breakspear, 2014 and Saberi et al., 2022 for analyses of these conditions in neural networks) and other biological systems (e.g., cardiovascular behavior, Sharma, 2009). In previous works, we referred to a system implementing local domains of varying computational complexity as displaying mixed computation. Our focus was primarily syntactic: the idea that a structural description may contain, for instance, local FS domains embedded in a CF phrase marker; or obtain mildly-context sensitive derived structures by the combination of elementary CF structures given cyclic substitution, structure sharing, and counter-cyclic adjunction (Joshi, 1985).

We are making two related, but distinct claims: first, we endorse existing arguments against structural uniformity, linking the linguistic arguments to much research on complex dynamical systems. Second, we identify the source of oscillations in the computational complexity of structural descriptions with the search for local solutions to the grammar inference problem. The complexity of structures assigned to incoming data (linguistic or otherwise) should optimally be local minima. This is for two reasons: first, structures that are “too rich” predict unattested (grammatical) behavior. Second, minimizing local complexity better satisfies working memory/channel capacity limitations and optimizes information processing, transmission, storage, and retrieval (Dehaene et al., 2015; Radulescu et al., 2020) as well as neurophysiological constraints derived from the finiteness of available resources. In this context, computational fluctuations in a structural description arise from the dynamics of the underlying computation as they represent changes in the input. This would not happen if the starting assumption was that the most powerful available device should be the first thing to try. The grammar makes available structures of varying complexity, which a parser assigns to an external signal. Computational fluctuations are also ubiquitous in the analysis of computational behavior in physical systems:

*Physical systems have been found that match the lowest three classes in the Chomsky hierarchy*, which gives a coarse classification of computational power. *Regular languages* (those that require no memory—just a directed graph of nodes representing states) *is exemplified in certain regimes of the quadratic map[…]. Context-free languages can be found exactly at the order-chaos transition of the same logistic map[…]. Context-sensitive languages describe the orbits visiting islands within islands in the standard map* […], which describes, among others, a kicked rotor. While dynamical systems in one and two-dimensions […] can also implement Turing computation, the latter have no physical counterpart […]. (Binder and Ellis, 2016, p. 4. Our highlighting)

So, as a first step, we can have an idea of what a solution for the grammar inference problem looks like for NL: the space of possible NL grammars is restricted (upper-bound by mild context-sensitivity), yes, but also considerably richer than traditionally assumed, since structural descriptions of regular, context-free, and mildly context-sensitive complexity are all locally available. Furthermore, the role of domains of locality and their interaction with information compression and mixed computation comes to the forefront. In the next section we will describe the dynamics between strings and structures in NLs, and explore how and why the formal characterization of a complex dynamical system that features local computational oscillations would implement agreement.

4 Strings and structures: the role of agreement

The role of agreement in grammar inference depends largely on how the question is formulated. Pollack (1991), for example, looking at neural networks, states his question as follows:

How could a neural computational system, with its slowly-changing structure, numeric calculations, and iterative processes, ever come to possess linguistic generative capacity, which seems to require dynamic representations, symbolic computation, and recursive processes?

This fragment highlights the hiatus that exists between computation and physiology: grammars are discrete closed systems, which in the case of procedural theories work in proof-theoretic time. In the purest generative formulation, a grammar is simply a membership-determining mechanism: given any string, a generative grammar can determine whether it belongs to the set of well-formed sentences or not. Set membership is a discrete property, and all syntactic theories (transformational or not) work with discrete productions/constraints (see especially Haider, 2019): there is no such thing as “half-violating the Case Filter” or “75% crossing a wh-island.” Impacts of these violations on human behavior are an entirely different matter, and indeed there is evidence that humans produce gradient responses even when recognizing the discrete nature of categories (Armstrong et al., 1982; cf. Schütze and Sprouse, 2014 for discussion). Physiology and cognitive systems, unlike formal grammars and cellular automata (CA), are neither discrete nor tied to proof-theoretic time. They are continuous, complex systems changing in real time. Part of the problem of grammar inference, then, takes the form of a problem of signal analysis, which requires chopping a continuous signal into what eventually will become members of the alphabet of the grammar. This is the problem of segmentation. In the literature on symbolic encoding of dynamical systems, this problem is often expressed in terms of a discrete parametrisation of the phase space, followed by the assignment of a symbol from a finite alphabet to each discrete region (Badii et al., 1991). This procedure, conceptually, is familiar to linguists in the form of Harrisian heuristics (e.g., Harris, 1957). In the field of Natural Language Processing, the terms chunking and tagging are often used.

When formulating the problem of segmentation, issues of resolution and scale arise: in the DS literature, the “size” of partitions are included as a term in equations to determine the dimension of a dynamical system (Günther et al., 1994, p. 640; Crutchfield, 1991, p. 46). In complex systems, properties at different resolutions vary such that properties of coarser scales cannot always be used to predict properties of finer scales.² In other words, global properties do not always emerge linearly from the additive combination of local properties. At any given scale, emergent behavior is understood as structures that cannot be directly described in terms of the constraints or operations that apply at that scale, or by initial or boundary conditions (Crutchfield, 1994). Furthermore, once identified at any given resolution, the segments (which are signal tokens) are assigned to abstract categories (which are types). How to do this constitutes the problem of labeling. In dynamical systems, indexing partitions by means of an alphabet allows states to be encoded as strings, each of whose symbols corresponds to a region in the space.³ Mappings between states can then be encoded in terms of mappings between strings: a transformation marker (Chomsky, 1965, p. 129) or a derivation tree (Kallmeyer and Joshi, 2003), which encode information about the derivational history of a structure, thus correspond to the characterization of a system evolving in (discrete) time. At the core of labeling and encoding lies compression: some properties of individual symbol-tokens are “forgotten,” and only a subset of properties, those common to a set of tokens, are retained. Compression is an unavoidable fact of information processing given any system with finite resources: in humans, these “finite resources” include working memory, the finite encoding capacity of the brain (what Radulescu et al., 2020 call “channel capacity”), and energetic and metabolic requirements. This simplification makes it possible to make predictions (see also Crutchfield, 1991, p. 45–46):

The idea is that understanding means reduction of the complexity to a level where predictions can be made. Reduction is a necessary condition for structuring. If there is no level of observation at which a system's behavior admits reduction of information for its description, then understanding in the usual sense will not be possible: such systems or processes will always surprise the observer and escape attempts of categorization. (Günther et al., 1994, p. 636)

A foundational question in this area is how to decide what can be ignored when reducing complexity without sacrificing a proper characterization of the target system. We will see that for aperiodic signals (including languages) it is necessary that “reduction of complexity” takes the form of a higher-order representation of allowed relations between indexed expressions (i.e., hierarchy and structure). In turn, structure can only be characterised for any system once we have a solution to the segmentation and labeling problems.

4.1 Compression in artificial grammars

Optimally, the problem of grammar inference aims to converge to a minimum description: we want the simplest grammar, according to some measure of complexity. Indeed, as Crutchfield (1991) observes, “the task of estimating optimal models becomes more difficult as the class capability increases.” If this measure is given by the Chomsky Hierarchy, the simplest possible grammar will be a strictly local grammar (SLG, see Hunter, 2020; Rogers and Pullum, 2011), subsumed under a finite state recogniser, with the most powerful available class being Turing machines (Chomsky, 1959). Let us start at the most restrictive model, then. Deterministic transition probabilities between adjacent symbols can be captured by means of a strictly 2-local grammar, which lists allowed 2-grams. If instead we are interested in excluding 3-grams, we are dealing with a 3-local grammar. These transition probabilities are regularities that, once identified, can be compiled into distributional statements that give rise to categories (for linguistic discussion, see Harris, 1957). In an immediate constituent grammar, categories are precisely distributional statements.

Consider now the deterministic L-grammar defined by the alphabet Σ = {0, 1} and the following rules, which apply simultaneously to all symbols in a string:

• 14) 0 → 1
• 1 → 01

-

Because at every generation in the development of this grammar the number of 0s, 1s, and symbol total is a number in the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, …), let's call the rules in (14) the Fibonacci grammar (“Fib” henceforth). The Fib grammar is a deterministic recursive grammar that generates aperiodic and self-similar binary sequences. Just as we saw for the logistic map, we are dealing with the symbolic encoding of a dynamical system. These sequences, at the limit, correspond to the symbolic encoding of quasiperiodic rotations in the unit circle, defined by the map:

• 15) θ_*n*+1 = θ_*n* + 1/φ mod 1

The Fig grammar (6) (Section 3.1) characterises the logistic map at the edge of chaos, after period doubling bifurcations. The Fibonacci grammar does the same with a system of rotations. Let us briefly see how. In this system, we keep track of the position of an arbitrary point after n rotations. The position of this point is denoted by θ: each point in the circumference of the unit circle will correspond to an angle θ, which can be mapped to a position x in the unit segment. Then we choose a threshold (1−(1φ) mod 1≈0.38197, and define a function s(θ_*n*) that encodes the position of a point in the circumference of the unit circle (mapped as the unit segment) as a 1 or a 0 depending on its position:

s(θn)={0 if θn∈[0,0.38197)1 if θn∈[0.38197,1)

In this way, we are dividing the unit circle into two regions and asking whether a rotation lands our point in one or the other region. The sizes of the regions are known values to us: they are the relative frequencies of 0 and 1 in the infinite Fibonacci word: ~0.382 and ~0.618 for 0 and 1 respectively. As before, iterating the mapping and applying the encoding s(θ_*n*) delivers a set of strings that characterise (and compress) the behavior of the system. Thus, the infinite Fib word describes how a point moves in the circumference of the unit circle: the Fib grammar provides a characterization of a dynamical system of quasiperiodic rotations.⁴

As with Fig, Fib generations are strings of 1s and 0s which feature transitional regularities between symbols. Vender et al. (2020, 2019) refer to these regularities in Fib strings as “the Three Laws”:

• First Law: if symbol i in generation g_*n* is a 0, then i + 1 in g_*n* is a 1 (i.e., we exclude the bigram ^*00)
• Second Law: if symbol i in g_*n* is a 1 and i + 1 is a 1, then i + 2 is a 0 (i.e., we exclude the trigram ^*111)
• Third Law: if i in g_*n* is a 1, i + 1 may be either a 0 or a 1

Of these transitional regularities, only the First and Second Laws are both deterministic and strictly 2-local. The Fib and Fig grammars are of particular interest because they have been used in creating experimental protocols to probe for human sensitivity to hierarchical structure, beyond low-level transitional regularities. In the Fib task as implemented in Vender et al. (2019, 2020) and Schmid (2023), sequences of 1s and 0s obtained by developing the rules in (14) are converted into sequences of distinct stimuli. For example, 0s become blue circles and 1s become red circles which appear sequentially on a screen. Upon seeing a circle, participants must press different buttons corresponding to whether the circle they see is red or blue.⁵ The basic idea is that, if the subject is learning as they carry out the task, they will get increasingly better (meaning, faster and more accurate) as they implicitly learn the hidden regularities. This includes performing above-chance in cases where the sequence is ambiguous: for instance, the case 0101?, where the First, Second, and Third Laws provide no information as to what the next symbol could be. Successful performance on the task requires a reliable mechanism to transition between superficial regularities and hierarchical structure. Because the outputs of the grammars are aperiodic, there is no “pattern” to memorize. Successful performance in the task requires participants to create internalized solutions to the segmentation and labeling problems: recognize units, formulate hypotheses about legitimate transitions, and build on those to construct higher-order abstract representations of the string which contain enough information to make reliable predictions in linearly ambiguous conditions. Note that in this case, unlike in decision problems in computer science, there is not a set of strings that participants are exposed to, but a single continuous string, and it is not required of them that they determine whether novel strings belong to the same language.

What form do the aforementioned internal representations of the Fib string take? Let's begin by considering the simplest possible device that can capture the distribution of symbols: as anticipated above, a strictly local grammar (SLG). These are even less powerful than finite-state devices: an SLG is a set of allowed n-grams (for some value of n). For Fib we need a 3-local SLG, since the Second Law refers to a banned 3-gram: we must exclude ^*111. There is a sense in which the following set of allowable 3-grams (note, an extensional, declarative specification) is adequate for Fib:

• 16) #01
• #10
• 011
• 110
• 101
• 010
• 01#

Such representations have been used in the literature on CA (cf. Wolfram, 1984). In a sense, identification at the limit is possible with this specification, since every possible 3-gram in the infinite Fib string is present in (16). However, this SLG is not sufficient to represent a human's representation of Fib. For starters, we know that some of those 3-grams do not correspond to constituents of the grammar (i.e., subtrees delivered by the rules), and there is behavioral evidence that constituency makes a difference in human performance. Simply having a list of allowable 3-grams is not good enough to make consistent reliable predictions (cf. de la Higuera, 2010, p. 2): for that, we need to have some representation of the distribution of these 3-grams. If the distribution of 3-grams is aperiodic, as it is in Fib, we need a higher-order representation that instead of keeping track of distributions can predict them as they follow from structural (derivational) conditions. Experimental results (Vender et al., 2019, 2020; Schmid et al., 2023; Sibsey, 2025, among others) show that human performance is consistent with they having developed a higher-order internal representation of the hierarchical structure underlying the sequences of trials they are exposed to, including being able to accurately disambiguate trials. Specifically, the fact that a [0] is always followed by a [1] allows “grouping” of [01] bi-grams into “chunks” when reading an output string from left-to-right. After this grouping, we are left with two kinds of chunks: [01] chunks and [1] chunks:

Note that every [1] chunk is followed by a [01] chunk, so by the same token we can revise the segmentation and build a [101] chunk. As a result, we obtain a partitioning of the string into [101] chunks and [01] chunks, where every [01] chunk is followed by a [101] chunk

… and so on. The distribution of these growing chunks is scale free, as Fib derivations are self-similar: the distribution of any two distinct constituents of the grammar always recapitulates the Three Laws (see Schmid, 2023 for extensive discussion). Note that one of the constituents always contains the other as a substring: [01] contains [1], [101] contains [01]. These subconstituents can be used as string “ancestrals,” in other words, labels. The irreducible labels end up being [0] and [1]: [0] for the “weak” term (the one contained in the other) and [1] for the “strong” term (the one that contains the other). In this way, the distribution of these labels follows the Three Laws. This allows the learner to construct a compressed version of the grammar based on the Three Laws. As observed above, approximating a generating function through compression of information about transitional probabilities is a requirement for a cognitively satisfactory solution to the grammar identification problem.

A model will always reduce complexity: it is neither possible nor useful to represent every feature of an object when creating a representation of it. For processing of an aperiodic signal, compression is the only way to go. Scale-free properties become crucial as we can in principle depend on these to be always scalable and thus focusing on scale-dependent properties may help at specific levels. Given finite resources, increasing input complexity (measured in terms of entropy) and constant channel capacity drives the system toward compression and generalization (Radulescu et al., 2020; Radulescu, 2021). If complexity exceeds channel capacity, some individually characterizing features must be ignored, yielding higher-level encodings.

rule induction is an encoding mechanism gradually driven as a natural automatic reaction by the brain's sensitivity to the input complexity (entropy) interacting with the finite encoding power of the human brain (channel capacity). (Radulescu et al., 2020)

Rule induction involves information compression – lose resolution, free memory. This is a delicate balancing act: how much information can the learner “forget” while still creating reliable representations? As we compress, there is information that is lost, retained, reorganized (and thus made harder to access). Human cognition seems to be particularly flexible when it comes to compression and retrieval. In her study of working memory and representations of quantity, Feigenson (2011, p. 13) argues that “although working memory is limited in the number of items it can store, it is also flexible in what counts as an item.” In her view, it is important to distinguish between objects, sets, and ensembles as compressed representations that can serve as “items.” Objects erase internal structure and representations of numerosity. Sets bind together individual representations into a representation that maintains access to individual components (e.g., phone numbers). Ensembles are approximate representations of collections for which individual access would be impractical (e.g., “there were about a hundred people at the talk”). Schmid (2023) provides evidence that internal representations of Fib preserve information about component chunks, up to a certain level of recursive chunking. It is important to determine what information is retained, and, if possible, why.

In the case of NL, the problems of segmentation and labeling that arise with L-systems and other aperiodic signals, and which result in the creation of local structural units, are accompanied by what we will call the gluing problem: once a signal has been segmented and a higher-order representation of it has been created, how can chunks be put back together for purposes of evaluation of global well-formedness conditions and compositional semantic interpretation? In Fib and other L-systems the gluing problem does not arise in the same form, since every local neighborhood is token-identical to any other:

• 17)

Structure-preservation (Emonds, 1970) ensures that an optimal solution to the gluing problem can be found as soon as the local neighborhoods are identified. The basic toolbox to address the gluing problem is delivered by dynamical systems: in Fib, movement and deletion rules always deliver structures that fall within the space delimited by the dynamics, because the grammar is self-similar. This means that any structure-sensitive pattern found in the derivation can be mapped to an earlier stage of the derivation, at every scale. The most basic illustration of self-similarity in Fib builds on the recurrence relation Fib_n = Fib_{n − 1} + Fib_{n − 2} for any nth term of the sequence that defines the Fibonacci series, and is shown in (18):

• 18)

Local neighborhoods as in (17) (called “Fibonachos” in Krivochen et al., 2018) mediate between strings and structure, based on labeling structurally salient 1s (called k-points in the aforementioned work) and identifying their local neighborhoods as the basic building block of the derivation. In NL, however, we need additional information to aid in structure composition given a richer range of interactions between properties of computational atoms (lexical items) and derivational properties as well as more varied sources of noise. In what remains of the paper, we will explore the possibility that agreement provides some of that information, both in terms of which expressions should be considered co-dependent and in terms of the structural relations that hold between them.

4.2 Compression and categorization in natural languages

Recall that given a stringset we may require either exact grammar identification or approximate grammar identification. The former, however, is not in general possible to achieve (Wharton, 1974; de la Higuera, 2010). It is important to remember that grammars are formal systems that make it so we don't have to actually simulate a system to predict its behavior. Therefore, it is in general not possible to know whether the original generator of a stringset is what humans construct in their minds after sufficient exposure to well-formed strings. The representation that humans construct must be “good enough,” where success is measured in terms of high accuracy and low reaction times in the Fib task. What we can do is control the properties of those strings so that the space of possible grammars is at least restricted, and we know its boundaries. In this context, we may ask what the relation is between properties inferred at a local level and global properties of the system we are analyzing. A usual assumption in generative linguistics and cognitive science is that we must find a unique generator that accounts for both, an assumption that delivers structural uniformity as a guiding principle (cf. Culicover and Jackendoff, 2005 for discussion).

The study of grammar inference in complex dynamical systems has a related but different lesson to teach us: systems may contain local units each best described in terms of a different computational device. Crutchfield and Young (1989) anticipate the basic tenets of mixed computation:

The basic result is that if one is careful to restrict the class of computational models assumed to be the least powerful necessary to capture behavior, then much of the abstract theory of computation and complexity can be constructively implemented. From this viewpoint, phase transitions in physical systems are seen to support high levels of computation. And conversely, computers are seen to be physical systems designed with a subset of “critical” degrees of freedom that support computational fluctuations.

The problem of exact grammar inference is NP hard (de la Higuera, 2010). Approximate inference is more tractable, depending on properties of the signal and the relation between those properties and properties of the (family of) generators. For Fib, the procedure characterized in Vender et al. (2019, 2020) and Schmid et al. (2023) is based on chunking+grouping+categorization. Deterministic transitions are identified, mapped onto constituents, and labels are assigned to those chunks. Because terminal symbols can be used as labels, this process delivers a representation of the grammar that is expressed in terms of the grammar itself. So, [101] is an “ancestral string” of [01101] (since the string [01101] follows from [101] by applying the rules 0 → 1, 1 → 01) but at the same time a legitimate terminal string of the grammar. In Fib, aperiodicity and self-similarity conspire to deliver a uniquely convenient relation between item-based and category-based generalizations. Furthermore, Fib also displays a balance between nondeterministic aperiodic and deterministic behavior: the First and Second Laws are deterministic, but the Third Law is not.

In dynamical systems, approximate grammar inference is made possible by encoding states as strings. Then, a set of strings is a set of states of a system (for the case of CA, see Wolfram, 1984). In the simplest cases (Class 1 and Class 2 CA), finite-state devices are enough to capture all possible transitions, and the number of states required to keep track of possible continuations of present trajectories remains either bounded or growing linearly. NL grammars present an additional difficulty: not all symbols in structural descriptions correspond to observable terminal symbols. Constituent structure analyses are based on abstraction from token-properties, resulting in a higher-order representation of strings (P-markers). There is a sense in which the grammar does not care about the internal structure of XPs. Consider:

• 19) [_NP John] is easy to convince
• 20) [_NP A man who is easy to please] is easy to convince

The analysis of (19) in Chomsky (1981) involved inserting the NP [John] not at D-Structure like all other lexical arguments, but at S-Structure: the position where it appears is not thematically marked (cf. *it*is easy to convince John, with an expletive subject) and thus not licensed by the Projection Principle. Chomsky's (1955) argument to bring back generalized transformations generalized the solution proposed in Chomsky (1981), dismissing all that differentiates the two NPs internally. Generalized transformations must be able to insert an XP at S-Structure, regardless of its internal structure (which may feature a generalized transformation itself as in (18), where the subject NP also features tough-movement internally). What matters for purposes of further operations, then, is the outermost label, not the internal properties of the constituent parts of the NPs or, most importantly, their derivational history. Once a syntactic object has been constructed -here, an NP-, the dynamics underlying its construction are lost to future computations. Chomsky (2001, p. 16) refers to the Markovian character of computations as an important condition on derivational economy: operations do not have access to previous states of the derivation. This is a form of compression, since in this manner, the derivational information that distinguishes the NPs in (19) and (20) is lost.

Natural language offers different tools to organize and convey information. Bresnan et al. (2016, p. 5), when considering the ways in which a grammar expresses grammatical relations between words, put it in a particularly illustrative way: morphology competes with syntax. In the present context, the competition pertains to the fact that languages resort to different ways to signal (i) the size of local domains, and (ii) the relations between elements within and across domains. These ways range from strict linear ordering of constituents (syntactic configurationality, where grammatical functions can be essentially read off order, being directly associated to specific structural positions; Dalrymple et al., 2019, p. 40) to very rich systems of head and dependent marking (which make available freer constituent orders). In dynamical systems, structure emerges at the interface of structure and uncertainty (Crutchfield, 1991): complexity emerges as the result of a tension. We find uncertainty at different levels of linguistic description. The absence of morphological marking is an example of string-based uncertainty:

• 21) a. Brutus killed Caesar
• b. Caesar killed Brutus

Given no head or dependent marking, the only way to determine who did what to whom is to rely on constituency, a property derivative of derivational structure, and linear order. When morphological marking (or “flagging,” following Haspelmath, 2019) allows for identification of grammatical functions (within reasonable error margins⁶), constituency and linear order have a much more peripheral role:

• 22) a. Brutus Caesarem occidit
• b. Caesarem Brutus occidit
• c. Occidit Caesarem Brutus
• …

Given variations in constituent orders, the assignment of structural descriptions to NL sentences cannot be looked at simply in terms of a time series. It is true that, given the linear character of the spoken chain (a property highlighted by Saussure, Tesnière, and many others), the results of the segmentation procedure are a sequence of discrete symbolic points ordered in time. However, and crucially, the position of a segment in a time series provides no information about its position in the structure that characterises the underlying dynamics being represented. As a comparison point, consider for instance:

• 23) Caesar, Brutus killed

where the canonical word order has been altered, yet it is possible to construct a structural description where Caesar forms a constituent with killed. Here is where agreement comes into play. Agreement and inflection give us information about category (consider in this respect the role of agreement and inflection in assigning category to nonwords in jabberwocky) and the relations between arguments and the predicates that subcategorise them within the grammar's domain of locality. Given structure preservation, knowing the category of an identified segment entails knowing possible base generation sites for a constituent. This greatly restricts the space of possible structural analyses once segmentation and labeling have applied. This space can be even further restricted by considering the structural relations that must hold between syntactic objects so that dependent marking or co-variation can take place (Section 4.3). Anticipating discussion, we can say that labeling that a chunk is an N(P) tells us something about its distributional properties at the syntagmatic level (as per Harrisian heuristics). Knowing that the target chunk is, say, an Accusative-marked N(P), tells us something about the nature of its structural relation to other, co-occurring expressions, in particular, a governor that assigns Accusative Case. All structural descriptions in which that chunk is not in an appropriate structural relation to an Accusative-governing predicate (in the sense of Corbett, 2006) must be excluded. Under generative assumptions about structural Case, adequate structural descriptions must impose hierarchy between the Case-assigning head and the Case-marked NP (in the form of c-command relations) within a local domain such that no intervening NP appears between the Case-assigning head and the NP under consideration. But our approach to agreement is not tied to Minimalist assumptions, where Case is an uninterpretable feature valued under specific structural conditions (Chomsky, 2000; Deal, 2023a,b). Consider, for instance, Nordlinger's (1998) theory of constructive case: in Nordlinger's view, Case is primarily a lexical property which specifies the syntactic environment within which the Case-marked phrase must appear. Case imposes an existential constraint, requiring a specific f-structure to exist. For example, the specification of ergative Case would be as follows (Sells, 2013, p. 187):

• 24) Ergative Case marker:
• (↑CASE) = ERG(ative) [read: the Case feature of
• the current node's mother at f-structure (2 below) has
• an ERG value]
• (SUBJ↑)OBJ [read: the f-structure of which I am a SUBJ (1
• below) must also have an OBJ]

Constructive Case imposes existential constraints that must be satisfied at the level of local f-structures, the domain of locality in LFG. The information conveyed by ergative Case, under constructive case, require the f-structure in which an ergative-marked NP appears to be minimally (25):

• 25)

Constituent structures (c-structures) assigned to strings are mapped to f-structures by a function φ, given certain regularities described in Dalrymple et al. (2019, Chapter 4). As Andrews (2021, p. 15) observes, an f-structure is “a representation of a set of proofs that the equational annotations to an LFG-annotated PS structure (c-structure) are consistent.” In a parallel declarative framework such as LFG, parallel levels of representation constrain each other: given the set of phrase structure rules that license local structures in a particular language (PSRs being interpreted as node admissibility conditions in declarative grammars, cf. Dalrymple et al., 2019, p. 140), constructive Case restricts the c-structures by imposing direct requirements on f-structures. The function of agreement in mediating between strings and (families of) structural descriptions is the same, despite different implementations (derivational vs. constraint-based in Minimalism and LFG respectively).

We mentioned in the introduction works that view the role of agreement as a string-level device to counter noise. Our perspective complements that, by analyzing the role of agreement in dispelling structural uncertainty. Much work in early generative grammar aimed at making sure that the set of structures that could be assigned to a string was finite: thus we get conditions such as recoverability of deletion that were intended to ensure that a finite number of Deep Structures could correspond to a Surface Structure (cf. Chomsky, 1965, p. 144–145; Ross, 1970, p. 841) and that derivations themselves had a finite number of steps. These conditions, however, are disconnected from the dynamics the grammar characterises. In our view, the set of adequate available structures is restricted by the interplay between internal properties of the grammar (e.g., through structure preservation, argument structure, and agreement) and properties of the signal delivered by the system that the grammar characterises. All signals must manage the ratio between information and noise. In this area, formal and natural languages differ greatly. Consider the case of Fib: due to self-similarity, the information-to-noise ratio remains constant across scales. Natural languages work differently, since the extent to which they display self-similarity is very restricted, and pertains perhaps only to properties of syntactic structure at the limit (cf. for instance the analysis of Fib patterns in X-bar phrase structure in Medeiros, 2008), unavailable in the analysis of finite samples. Natural languages use redundancy to counter string-based and structure-based noise in creative ways: in some cases, redundancy (by which we mean the multiple expression of a single information-conveying term) helps rescue a structure:

• 26) a. That's the guy_*i* who_*i* they don't know whether ^*(he_*i*)
• wants to come or not
• b. Which picture_*i* did they all blush when John saw ^*(it_*i*)?

In English, as Frank and Kotek (2022, p. 8) put it, “the availability of a resumptive pronoun correlates with the presence of an island.” The fact that island boundaries have been crossed can be evaluated representationally (if the entire structure is available for probing) or derivationally (by tracking the derivational history of the wh-phrase). In either case, there is a dependency that cannot be established due to structural conditions. The derivation of (26a-b) involves feature valuation, therefore the operation Agree. Recall that in classical Minimalism overt displacement (Move) has Agree as a suboperation (Chomsky, 2000): for C to attract a wh-phrase to its Spec, an unvalued feature in C must find a corresponding valued feature in DP (cf. Pesetsky and Torrego, 2007). This establishes a link between two expressions and allows for the value of the relevant feature in DP to be copied to C. Overt displacement is then a consequence of a different requirement, usually formalized as an EPP-style feature in the relevant probing head (Chomsky, 2000, 2001). The structure is illegitimate, as it contains an island violation (formalisable in a variety of ways), but the presence of the resumptive pronoun spelling out the variable bound by the wh-operator makes it possible to construct a structure in which, as intended, there is a syntactic long-distance relation across local domains that should be opaque. The island introduces structure-based noise, and the resumptive pronoun introduces an element of redundancy (spelling-out two links in a chain) that restricts the structures compatible with the input.

A grammar that defines a restricted domain of locality needs some information to glue “cycles” together: local domains are composed to obtain derived structures (e.g., compose elementary trees to obtain a derived tree and read off compositional semantics from the derivation tree in a TAG). The gluing role of agreement, and its importance in the mapping from hierarchy to linearity, are noted already in Tesnière (1959, Chapter 6, Section 9):

The transformation of structural order to linear order is often facilitated by grammatical agreement, which involves marking connected words with the signs that convey agreement. Agreement greatly aids comprehension of the sentence by facilitating the establishment of connections.

Agreement is determined structurally but expressed at the string level. It mediates between high-dimensional and low-dimensional representations, and in that role it directly expresses how compression works in natural language syntax. In other words: the expression of agreement is low-dimensional, but its licensing conditions refer to higher-dimensional structures. Again, Tesnière anticipates the issue with admirable clarity:

Syntactically, the true sentence is the structural sentence, for which the linear sentence is only an image projected onto the spoken chain. (Chapter 6, Section 10)

In reestablishing the structural connections that are not expressed by the sequences, the role of grammatical agreement […] is crucial. (Chapter 7, Section 6)

Agreement's mediating role between high- and low-dimensional structures is rather unique in NL, and has no equivalent in classical symbolic encoding. Other frequently assumed relations and operations are only expressed at one of these levels, providing no aid to grammar inference. A clear case is so-called Quantifier Raising, a movement rule that affects quantified phrases at the level of LF. Purely structurally determined, it has no impact on the low-dimensional expression of structure.

4.3 The architectural role of agreement

Because of its structural licensing conditions, agreement restricts the space of legitimate structural descriptions for any given string: only those structures that made available relations between terms that satisfy the conditions that make agreement possible are in the solution space. In the context of the problem of grammar inference, one cannot stress enough the importance of any factor that limits the space of possible solutions. In our view, allowed agreement configurations in the grammar restricts the syntactic distribution of agreeing categories, in addition to providing clues to the assignment of expressions to categories themselves. This is how it provides information that allows for “reestablishing structural connections” (in Tesnière's terms), or more specifically restricts the space of possible structural connections (since, recall, the best we can hope for is approximate grammar inference). Conceptually, this is orthogonal to the dispute between agreement as the result of Spec-Head relations vs. Probe-Goal relations (both of which can still be found in generative works), or some other formal condition. In both cases, saying that A agrees with B provides information about the category of A and B as well as their relative syntactic position. The specific implementation of the mechanism whereby expressions enter agreement is a matter of specific syntactic theories (cf. our brief discussion of derivational and constraint-based approaches to Case in Section 4.2). For concreteness, consider the generative analysis of Case. Canonically, for example, in SVO Indo-European languages, Nominative Case is licensed in a local relation (Government, Probe-Goal, Spec-Head) with finite Tense (which, following Chomsky, 2000, also serves to determine Subject-Verb agreement), Accusative Case is licensed in a local relation with a transitive verb, and Oblique Case is licensed in a local relation with a predicative preposition (or is expressed by the preposition itself). The basic idea has remained consistent since the early days of GB:

• (i) NP is nominative if governed by AGR
• (ii) NP is objective if governed by V with the subcategorization feature: [_ NP] (i.e., transitive)
• (iii) NP is oblique if governed by P
• (iv) NP is genitive in [_*NP* _ X']
• (v) NP is inherently Case-marked as determined by properties of its [-N] governor (Chomsky, 1981, p. 170)

The canonical configurations for structural Case licensing (valuation, under Agree) are illustrated in (27), which illustrates the two basic structural conditions for the operation Agree to take place: locality and asymmetry (qua c-command) (see also Deal, 2023a).

• 27)

In this configuration, finite T, which bears unvalued Person and Number features (“phi-features”), probes its c-command domain, copies the value of the matching Person and Number features in DP_*i* and, as a by-product, values the Case feature in DP_*i* as Nominative (Chomsky, 2000). Both categories have all its attributes valued, as required by external legibility conditions on syntactic objects. Mutatis mutandis, the same relation holds between the light verb v and the object DP: v phi-agrees with DP_*j* and values the Case feature in DP_*j* as Accusative. In contrast to the earlier checking mechanism, whereby features are “certified as appropriate” in a Spec-Head configuration (thus motivating DP raising to Spec-T, cf. Chomsky, 1995), under Probe-Goal Agree, DP_*i* raises to Spec-T as required by a property of T, an “EPP feature” (Chomsky, 2000, p. 109). The notion of locality that is relevant here is twofold: first, both syntactic expressions in an Agree relation must be contained in the domain of locality of the grammar (in contemporary Minimalism, for example, the phase, see Bobaljik and Wurmbrand, 2005 for discussion). Second, the Goal must be the closest suitable object for the Probe to agree with. This condition, which following Rizzi (1990) we refer to as a (relativised) Minimality requirement, prevents T from entering a syntactic relation with DP_*j*, since DP_*i* intervenes in this relation. If we have a sequence with two case-marked NPs, and as suggested in Uriagereka (2008), Case information helps “sorting out” the positions of flagged arguments in the structural description assigned to a string. Uriagereka goes as far as proposing that this is the reason why multiple Case values exist. As for nominal concord, there are two general accounts in contemporary generative grammar: either, as proposed by Bruening (2020, p. 9), it reduces to Probe-Goal, or it is determined as pure feature-copy between Mergemates (Carstens, 2000; Chomsky, 2001, p. 42, fn. 6). In either case, however, the result is the same: token-identity between exponents [e.g., mujeres trabajadoras in (1a)].

The more restricted the configurations that license agreement, the more information is conveyed by agreement for purposes of reconstructing hierarchy from information at the string level. Crucially, since generative grammar allows structures to remain constant while strings can vary (through reordering transformations in the syntax or at LF), the linear order of constituents does not provide reliable information about syntactic position. Languages with relatively free word order and rich dependent marking systems, such as Latin, attest to this fact [(cf. 22)]. Formally, this is simply a statement of the fact that strings do not uniquely specify derivations (and thus, as tree diagrams are diagrams of derivations, strings do not uniquely specify trees). The role of agreement, in this view, would be to flag configurational relations that hold between expressions in a signal, assuming -crucially- that the set of relevant relations is cross-linguistically stable, if not universal.

Segmentation and labeling, as explained above, deliver a set of expressions indexed by a set of categories. As the segmentation and labeling problems are solved, we need to sort these indexed expressions in a structural description, where the hierarchical relations between them are specified. In Section 3 we explored the idea that structural descriptions are assigned locally, with the computationally simplest structure being the first candidate. The “start small” heuristic helps us restrict language/computational complexity, but NLs allow for a far richer array of meaningful relations than binary encodings, partly due to the contribution of lexical information. The structural positions that are available for categories to fill, following agreement-licensing relations, are further restricted by properties of the lexical heads that anchor the grammar's domains of locality. Let us flesh this out. As noted in Section 2, syntactic theories frequently work with a minimal unit composed of a lexical predicate and all its required functions. In Lexicalised Tree Adjoining Grammars, this unit is called an elementary tree, and the predicative expression is the anchor of the tree (Frank, 1992). In a lexicalist theory, predicates specify the number, category, and semantic properties of the arguments they subcategorise: these are a predicate's c-and s-selectional properties, grouped under the study of argument structure (Harley, 2011). Argument structure restricts fundamental aspects of tree geometry at the level of elementary trees: how many positions are there available to be filled? If we know the properties of the predicate, we know what the syntactic unit it anchors “looks like,” geometrically. Note that in this sense argument structure also restricts the space of possible structural descriptions: argument-taking expressions specify their valency as part of their lexical entry, as well as their thematic properties. Hale and Keyser (2002, p. 1) define argument structure in a way representative of so-called endoskeletal models of the lexicon-syntax interaction, and very germane to our own view:

Our concern is “argument structure,” by which we mean the syntactic configuration projected by a lexical item. Argument structure is the system of structural relations holding between heads (nuclei) and the arguments linked to them, as part of their entries in the lexicon. Although a lexical entry is much more than this, of course, argument structure in the sense intended here is precisely this and nothing more.

This view does not need syntactic structure to exist in the lexicon or indeed to pre-exist lexical insertion if argument structure is interpreted to contain information that is used to check, declaratively, the structures within which LIs appear. In other words: if a verb V has a subcategorisation frame [+ __ NP], a tree T containing V will be well-formed iff V is a sister of NP in T. In this sense, Hale and Keyser's view is not unlike Abeillé's (1990, p. 295), who writes (from the perspective of lexicalised TAGs):

What lexical heads select is in fact a set of such elementary trees called a “Tree Family” […], each tree corresponding to a certain constituent structure […]. This is the level at which syntactic generalizations can be stated, since each elementary tree may bear specific constraints independently of any lexical items. A Tree Family consists in fact of all the constituent structures trees which are possibly allowed for a given predicate.

The role of agreement is somewhat more subtle than that of argument structure, allowing the parser to fill these positions with appropriately flagged segments. Summarizing, the dynamics of the (cognitive, formal) system that underpins NLs puts hard limits to the spaces that grammars can define: argument structure restricts tree geometry, agreement both restricts and flags dependencies between objects within and across the grammar's domain of locality. Agreement, insofar as it indicates systematic covariance between grammatical features of expressions (Corbett, 2006, p. 5), allows us to detect structural relations between the expressions involved. The fact that agreement can only occur in specified structural configurations provides information about how expressions are to be understood in relation to one another. It helps with relations at the string level as well as at the hierarchical level, thus providing a bridge between low-dimensional and high-dimensional representations of linguistic input. Agreement, then, has a strong architectural function, as well as providing considerable aid to solve the problem of grammar inference. Therefore, we would expect it to be ubiquitous in the world's languages, and that expectation is borne out. According to Baker (2013, p. 610), 89% of sampled languages in the WALS have either Case or (phi-)agreement (or both). Subject agreement is more common than object agreement (75 vs. 50%), and there seems to be an implicative relation: object agreement appears if a language has subject agreement (but not the other way around) (Croft, 1990, cited in Baker, 2013). Interestingly, Corbett (2006, p. xv) suggests we would not include agreement in the design of an artificial language. We contend that, if we expect humans or similarly equipped parsers to be able to assign structure to strings in that artificial language, and its alphabet and allowed formal relations are complex enough, agreement is a necessary ingredient. As a matter of fact, and to reinforce this last point, Franck et al. (2016) found that adults can learn agreement dependencies in an artificial context-free phrase structure language with a complex alphabet and agreement markers (cued by prosodic and semantic cues), even from minimal training and limited input.

4.4 Agreement at the edge of chaos

Let us now turn our attention to a bigger picture: where NLs lie in the context of complex dynamical systems. In NLs morphology competes with syntax, and in formal grammars redundancy competes with self-similarity.⁷ The interpretation of “competition” is close to “division of labour”: by means of which system are structural relations encoded? A formal system that is self-similar needs no redundancy in its alphabet to keep track of previous states, and thus of non-local relations. In an extreme case, as in the Fib L-grammar (Section 4.1), the fact that all regularities recapitulate the Three Laws at all levels of abstraction makes it possible to either solve with complete certainty or leave as unsolvable any string-level ambiguity (with 0101? and 01101? as the crucial cases, respectively. See Vender et al., 2020 for discussion). In NLs, the picture is more complex. Agreement shows different exponents: dependent marking for Case (an asymmetric relation where only one expression is marked) and token identity in concord and predication [cf. (1), where all relevant expressions show inflection]. These relations, defined over structural configurations that go well beyond the power of SLGs, reinforce properties of the signal and act as “glue” between elementary structures. They therefore limit entropy and provide robustness against noise in combination with argument structure. This means that perturbations in the system will not completely derail processing: complex systems have their own way to control “damage spread.”

Dynamical systems at the edge of chaos, those that support computation, show long-distance correlations: information is stored in the system's configuration and through the deterministic equations of motion (or transition rules) that govern the behavior of the system, that information can be transformed and transmitted. These systems are also more robust against perturbations than chaotic systems, as we can see in the analysis of damage spread in CA. In the simplest case, a 1D cellular automaton where “damage” is a single flipped bit compared to a CA where no such flip has taken place, we can measure how fast the “damage” spreads from that flipped bit and how fast the two CAs diverge. “Information,” in this case, is encoded in the initial spatial arrangement of cells. In complex, yet not chaotic, systems there is something in the dynamics that limits damage spread, slowing it down with respect to their chaotic counterparts. In chaotic systems, in contrast, errors get amplified exponentially, and information is lost quickly, making them unsuitable for computation. Computation requires the dynamics of the underlying physical system to support the storage, transmission, transformation, and retrieval of information, which chaotic dynamics cannot do. It is important to note that these chaotic systems do not necessarily display “complex” surface patterns. For example, consider the following grammar, which we call XOR since it defines an exclusive-OR logical gate⁸:

• 28) 0 → 10
• 1 → 01

The first five generations of the XOR grammar are:

0(Axiom)10011010010110011010011001011010010110011010010110100110010110…

The superficial pattern of this grammar's outputs is simple: each generation n is made of the bitwise complement of n-1 concatenated with n-1. At the string level, the number of symbols in each string is a power of 2, there is an equal number of 1s and 0s in each generation, and the grammar displays axial symmetry through the bitwise complement transformation. As shown in Krivochen (2025), this grammar corresponds to the symbolic encoding of the dyadic map:

• 29) y_*n*+1 = 2y_*n* mod 1 (for y in the interval [0, 1])

This map is chaotic across its entire domain: there is no “transition” into chaos (as there is in the logistic map, cf. Section 3.1⁹). Interestingly, while there is extensive evidence of implicit learning with Fib in multiple modalities (Saddy, 2009; Vender et al., 2019, 2020; Schmid, 2023; Compostella, 2024), humans appear incapable of learning XOR (Saddy, 2009; Shirley, 2014). Krivochen (2025) speculates that human signal analysis capabilities are especially sensitive to systems at the edge of chaos, but fully chaotic regimes are unlearnable. Part of the reason why could reside precisely in how perturbations affect the dynamics in each kind of system: one that transitions into deterministic chaos and one that is inherently chaotic.

A crucial observation is that in complex non-chaotic systems (e.g., the circle map whose symbolic encoding is given by Fib) the rate of information loss as a function of time is diminished when compared to chaotic systems. This allows information about the initial conditions to persist throughout the development of the system in the form of stable local arrangements (e.g., gliders in universal CA such as Conway's Game of Life, cf. Gardner, 1970), and makes computation (which depends on storage, transformation, and transmission of information) possible. In contrast, in chaotic systems information gets “diluted” by the dynamics, which makes it impossible to reconstruct initial conditions given any arbitrary iterate (Gade and Amriktar, 1992). In a way, then, we should talk about information recoverability. Suppose now that the initial state contained designated cells that provide information not only about their immediate environment (i.e., their neighbors), but also about long-distance correlations: the most basic form of this problem is to determine how likely it is that two cells in an elementary CA are in the same state. In CAs, correlation matrices provide exactly this information: for every pair of cells c_*i*, c_*j* at distance d, a correlation matrix specifies how likely they are to be in the same state at time t (i.e., how they covary). In chaotic (Class 3) CAs, correlations decay quickly, as expected given the fast spread of perturbations. In complex (Class 4) CAs, correlations remain more stable, allowing for persistence of local structures, storage, and transmission of information, and thus computation (cf. Langton, 1990, p. 16). NLs offer an inventory of expressions that encode these relations within and (in extreme conditions) across the domain of locality of the grammar: agreement morphology and dependent marking are examples of the former, and pronominal agreement through resumption of the latter. Note that, just as in dynamical systems, correlations span arbitrarily long portions of structure, although they are in practice not infinite. In Langton's terms, “the propagation of information must be unbounded in principle but boundable in practice.” This is consistent with the classical view of agreement as a means to reinforce the signal by reduplicating information available in the structure as string-level covariation, and thus make it more resistant to perturbations. As highlighted throughout the paper, however, we argue that to provide an adequate characterization of the role of agreement in NLs it is necessary to consider the “vertical” dimension alongside the “horizontal” one. In CAs, as in L-systems, there is no representational stability in the form of labeled constituents; in fact, L-systems make no distinction between terminal and nonterminal symbols. The role of agreement in flagging string-level correlations is complemented by its role restricting the structural descriptions compatible with the target strings.

To exemplify damage spread in NL processing, consider an example of agreement attraction:

• 30) ^*The key_Singular to the cabinets_Plural are_Plural on the table

The extent to which information damage, understood here as agreement error, can spread in the structure is limited: even though we have an agreement attraction effect in (30) such that the finite verb does not agree with the head of the subject NP but with the embedded NP, it is possible to reconstruct “what happened” (see Wagers et al., 2009; Franck et al., 2006 for discussion).¹⁰ In a sufficiently complex open dynamical system, noise and perturbations are unavoidable. In this context, phenomena like agreement attraction are expected given the systems' dynamics rather than a “malfunction”: computation at the edge of chaos supports robust representations and is error-tolerant unless error signals accumulate and require a revision of representations to capture the properties of the input. In this context, where perturbations and noise are an integral part of the system's behavior, it is to be expected that “damage” appears, and also that damage is structurally bound, not spreading freely through the low-dimensional string. This is precisely what we see in Class 4 (complex) CA and in natural language. Going back to the Franck et al.'s (2016) AGL study mentioned in Section 4.3, it is important to note that the input used by these researchers included structures analogous to those that are known to generate agreement attraction effects (both modifier attraction and object attraction). These did not impair learning of grammars with hierarchically modulated long-distance dependencies. The Franck et al. results show that these configurations do not impede the development and generalization of structural descriptions to characterise the inputs. This is consistent with the present view of the grammar as the formal characterization of a system at the edge of chaos, capable of keeping perturbations under control.

The notion of local domain provides a limit for damage spread: Bock and Cutting (1992) observed that an NP embedded in a relative clause (31b) does not generate attraction effects, but an NP that appears in the same clause as the finite verb does (31a):

• 31) a. ^*The editor_Singular of the history books_Plural
• were_Plural (…)
• b. ^*The editor_Singular who rejected the books_Plural
• were_Plural (…)

While there are issues with the definition of “clause” as the “unit of encoding,” and later studies have found weaker (but existing) attraction effects from NPs within relative clauses (Franck et al., 2010 for discussion based on French data), the point is well-taken. Attraction, defined as a type of damage spread in processing, is structurally bounded. Franck et al. (2016, p. 87), discussing and summarizing previous literature on agreement attraction effects, say

Interference was found to be structure-dependent, and best characterized in terms of the hierarchical structure of the sentence

Structural considerations, enriched with mixed computation, provide insights into Bock and Cutting's results. If adjuncts correspond to separate derivational units from the objects they attach to (cf. Uriagereka, 2002; Krivochen, 2021) due to the shift in computational complexity their introduction requires (which goes beyond regular sub-derivations), their (relative) opacity can receive a formal explanation. Furthermore, when more than one attractor is present, structural height makes a difference: a higher attraction rate was reported by Franck et al. (2002) for the NP that is structurally higher (though linearly more distant from the verb), programs in (32):

• 32) ^*The computer_Singular with the programs_Plural of the
• experiments_Plural are_Plural broken

In addition to strictly configurational properties, we must consider the place of lexical information in processing. The properties of individual expressions are more relevant to restricting allowable configurations in NL than in the formal systems we have looked at. In elementary CA, for instance, cells can have two states: alive or dead (Wolfram, 1984). This allows for bit-based computation. Any cell can appear in any position, however, because all alive cells are functionally equivalent and so are all dead cells. The same is essentially true of L-systems: any 0 is functionally equivalent to any other 0 and any 1 to any other 1. This extends to the subtrees they dominate. Lexical properties set NLs apart from formal systems: statements about the distribution of categories compress properties specific to certain lexical items, but these can be important to determine the scope of damage spread. As emphasized by Ross (1972), categories are squishes, with more or less peripheral members. Therefore, alongside (30) we find pseudopartitive cases like (33), where attraction effects are harder to diagnose:

• 33) A variety of paintings hang/hangs on the museum's walls

“Variety” is not a prototypical noun (compare, for instance, ^*A variety hangs on the museum's walls with The key is on the table), but it is also not purely quantificational and as such part of the extended projection of another expression. Smith et al. (2018) classify it as a “Measure Phrase”: these are “similar in meaning” to quantifiers but which differ from them in for example accepting adjectival modification (e.g., a huge variety). Compare in this respect variety with a Quantifier like bunch, which is higher in the scale of notional plurality:

• 34) A bunch of paintings hang/^*hangs on the museum's walls

Judgments on (33) are much more evenly spread than on (30) and (34). Ryda (2024) reports patterns of symmetric judgments with variety, such that alongside the illusion of acceptability of a variety of paintings hang on the wall some speakers have illusions of unacceptability with a variety of paintings hangs on the wall, unexpected if variety of paintings was analyzed as an NP with head variety.¹¹ (31) and (32) aptly illustrate the relevance of lexical properties interacting with a restricted space for possible interpretations as made available by the dynamics. The analysis of attraction effects in pseudopartitives in Smith et al. (2018) is based on a system where lexically anchored treelets are linked to one another in the process of comprehension. These links are weighted, and compete with each other based on feature matching between substitution sites and attached treelets. Their system also models noise in the links, which delivers probability distributions over final structural descriptions for cases where, for instance, more than one N can be read as the target of agreement due to competition. In this view, structural descriptions are the result of a dynamical self-organizing process whereby treelets form complex structures via attachment links and compete with other treelets in real time as the input is perceived. Derived structures, then, are the result of complex dynamics internal to the grammar.

5 Conclusions

We have examined the role of agreement in solving the problem of grammar inference; that is, how to use information present in a signal to construct a model which accounts for the characteristics of the observed signals. The model for a string is a structural description, and for a language, a grammar. As we have emphasized, this is a problem in symbolic encoding of dynamical systems as much as in language acquisition and processing. Of the different versions of the problem, exact grammar identification is, as has been repeatedly observed in the literature, rarely tractable if in principle even possible. From a linguistic perspective, it is well-known that strings do not uniquely specify derivations (and thus structural descriptions). Additional constraints are necessary on the set of possible structures to make (approximate) grammar inference tractable. At the same time, for linguistic purposes is it not enough to formulate “shortcuts” in the sense of Wolfram (1984): statistical approximations of outputs that do not simulate the computation. In NL syntax, the computation itself is informative alongside configurational information stored within lexical items in the form of subcategorisation frames. Strongly derivational systems, such as the early Standard Theory and Tree Adjoining Grammars, keep track of the computations in so-called transformation-markers and derivation trees, respectively. In TAGs, for instance, semantic interpretation operates over derivation trees, not derived constituent structures (see Kallmeyer and Joshi, 2003 for TAGs, and Katz and Postal, 1964, p. 54, ff. for ST). It is also not sufficient to consider robustness to noise at the level of strings alone: syntactic constraints and operations are formulated over structures, not strings.

We explored the relation between grammars as finite specifications for languages and the underlying systems whose behavior these languages compress. The operations formalized by grammars are available in restricted dynamical regimes: systems that fall into equilibrium are computationally too simple and inflexible in the face of perturbations (the symbolic encoding of their dynamics corresponding to regular languages), and in fully chaotic regime, system transients are too short and information dissipates too quickly. Agreement then can be seen as the means whereby a system may avoid chaos but stay within the phase space of the route. Note there are many routes to chaos (the logistic map, for instance, exemplifies a bifurcation route to chaos, since the transition between order and chaos takes the form of multiplying bifurcations), and the class of agreement phenomena may also serve to keep a system constrained to a particular route. The reason that persistent covariance is common in dynamical systems, then, is that it allows us to preserve information about relations in local structure and the history of the system evolving through different modes.

Summarizing our argument, agreement gives us a way to overtly connect state A to state B, such that a parser can keep track of the internal dynamics of the computation. In representing these dynamics, many computational regimes are in principle available. In assigning structural descriptions to signals, we may apply the “start small” strategy (assign the simplest available structural description, with the measure of complexity being provided by the Chomsky hierarchy), but we still need a way to determine (i) if the structure we have assigned is adequate and (ii) how a local structure interacts with the wider structural context in which it occurs. Given these requirements, agreement phenomena in NL are ubiquitous because they express core aspects of system dynamics: the tension between computations and signals. The core idea is that hierarchical inference is strongest when the system operates in a multiscale dynamical regime near the edge of chaos: stable enough to support compression and the emergence of categories, and flexible enough to switch levels of computational complexity as needed. Covariation appears in elementary dynamical systems (as measured by “correlation matrices/arrays” in CA) linked to computational capacity, but NLs exploit various components of the dynamics -aspects that arise because of scale dependence and time- using a richer set of expressions and structural relations. Agreement is not an arbitrary device to solve the problem of linking strings to structures, but in fact is part of operations and dependencies inherent in the dynamics at the edge of chaos. Informally, we may say that NLs did not build a new set of operations to wrestle with the dynamics. Rather, NLs' expressive power is built from harnessing constraints inherent in system dynamics. “Agreement” names a set of emergent dependencies between different levels of computation, determined at the level of structure but expressed at the level of sequences.

Generative AI statement

The author(s) declared that generative AI was not used in the creation of this manuscript.

Any alternative text (alt text) provided alongside figures in this article has been generated by Frontiers with the support of artificial intelligence and reasonable efforts have been made to ensure accuracy, including review by the authors wherever possible. If you identify any issues, please contact us.

Publisher's note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

Footnotes

Edited by: Francesca Franzon, Pompeu Fabra University, Spain

Reviewed by: Jana Willer-Gold, University College London, United Kingdom

Germán Kruszewski, Pompeu Fabra University, Spain

Footnotes

In this paper we focus on what Corbett (2006: 9) calls canonical instances of agreement.

In physics, the idea that large scale phenomena can be described without a full specification of smaller scales is known as scale decoupling (Burgess, 2020).

In theories such as Categorial Grammar, it is usual to refer to a set of expressions as being indexed by a set of categories (cf. Montague, 1973).

We must note that grammars cannot exactly reproduce the inner workings of complex dynamical systems (i.e., their capacity for simulation is very limited; see Saddy, 2019), but they can provide precise characterisations of symbolic encodings of different stages in the transition between deterministic behavior and chaos.

The protocol is, in this respect, close to Gold's (1967: 449–450) theoretical setup for language presentation via text, where time is discrete and at each time increment the learner is exposed to a unit of information from the target language. Gold's learner is a function from input strings to “names” of languages (or “grammars”).

This caveat is necessary due to the fact that associations between dependent marking and grammatical function are not causal: not all Accusative NPs are objects across the board, for example (Latin arguably did not have Raising to Object. Rather, Case was likely assigned internally to the embedded clause, because Accusativus-cum-Infinitivo clauses could appear in passive and unaccusative contexts, cf. Cecchetto and Oniga, 2002).

To the extent that self-similarity is a property of NLs, it is a property of structural descriptions only at the limit (cf. Medeiros, 2008).

This grammar is sometimes also called the Thue-Morse grammar, because it generates the Thue-Morse sequence.

As a matter of fact, the dyadic map is conjugate to the logistic map when r = 4, at the point of “full turbulence” (Ford, 1986: 4). This means, essentially, that both systems have the same dynamics and can be transformed into one another. If f is a map X → X and g is a map Y → Y, then hX → Y is topologically conjugate if (a) h is a homeomorphism from X to Y (a continuous bijection with a continuous inverse), and (b) h(f) = g(h).

Here we remain agnostic about the mechanism that underpins attraction effects, misrepresentation or misretrieval.

Perhaps anecdotally, the OED classifies variety as a noun.