Arc pair grammar
In linguistics, arc pair grammar (APG) is a theory of syntax that aims to formalize and expand upon relational grammar. It primarily builds upon the relational grammar concept of an arc, but also makes use of more formally stated ideas from model theory and graph theory. It was developed in the late 1970s by David E. Johnson and Paul Postal, and formalized in 1980 in the eponymous book "Arc Pair Grammar." History. Early syntactic theory concerned itself primarily with grammatical relations. This trend was abandoned by proponents of transformational grammar, except in semantic interpretation. In the early  1970s, some linguists, such as Edward Keenan, began to challenge this notion from the transformationalist perspective, noting for instance the formation of relative clauses in Malagasy and English passivization (see chômeur). Relational grammar (RG) itself was never formalized in one place; instead, Keenan, Johnson, and others began writing aspects of the framework in a series of dissertations around this time. Dissatisfied with the results and lack of formalization in RG, David Johnson and Paul Postal attempted to lay down a version of it using mathematical logic. This attempt swelled into a new theory, now known as APG. APG itself was  developed by Johnson and Postal in the late 1970s, but was not published until 1980. APG takes grammatical relations, the graph theory notion of an arc, and two operations (SPONSOR and ERASE) as primitives, with all other rules being derived (many of them mathematically, rather than empirically). Postulates. In contrast to the generative-enumerative (proof-theoretic) approach to syntax assumed by transformational grammar, arc pair grammar takes a model-theoretic approach. In arc pair grammar, linguistic laws and language-specific rules of grammar are formalized as axiomatic logical statements. Sentences of a language, understood as structures of a certain type , follow the set of linguistic laws and language-specific statements. This reduces grammaticality to the logically satisfiable notion of model-theoretic satisfaction. Pair Network and RLS-graphs. The pair network (PN) is the main method of representing sentences in APG. It is a mathematical model consisting of nodes (for each word and the clause as a whole) and arc connecting them, with operations acting on arcs rather than nodes. This is somewhat analogous to the TG idea of a tree, but with a few major differences. First, PNs are formal mathematical objects, while trees in TG are mathematical objects that  are not formally defined. Second, the idea of branches in trees does not carry over; while branches attach nodes at varying levels of structure, with the overall web of branches determining grammatical roles, arcs encode grammatical roles to their heads with their only structural role being attaching words to their clause. Third, operations between arcs (i.e. intra-structural operations) create word order, whereas TG structure encodes word order at all levels. A pair network consists of four components: the 'relational-graph,' the 'logical-graph,' the 'surface-graph' (R-, L-, S-graphs), and the two operations and . The R-graph is  simply the set of all items in the pair network, i.e., the structure as a whole of all arcs, labels (R-signs), and operations between them. The S-graph consists of those members of the R-graph which are actually spoken. Single phrasal element and word are treated as having a single root for the purpose of the S-graph, although the APG framework is theoretically applicable to lexical entries. The L-graph represents the semantics of a pair network and the logical relations between its elements. L-graphs also contain the notion of "logical arcs," which are precisely those  arcs in the R-graph that terminate in nodes labeled with the logical and semantic relations of an arc. Sponsor and Erase. operations are used between levels in the R-graph to establish different linguistic states (that is, a particular set of grammatical relations). Generally speaking, lower levels sponsor higher levels, and higher levels erase lower levels. can be broken into two cases: Replace and Succeed. Succeed is the more basic of the two, in that an arc A is the successor of another arc B if and only if B sponsors A, A and B overlap, and B≠A. That  is, every arc that is sponsored by an arc other than itself is the successor of that arc. Replace, meanwhile, occurs exclusively between arcs that are neighbors (arcs that share a head, but have distinct tails). As a consequence, Replace can only occur between arcs with an identical R-sign. Arcs that are part of Replace operations cannot also be part of Succeed operations. Thus, Replace is significantly more restricted than Succeed. Although they ultimately have the same effect of establishing sponsorship, Replace and Succeed are subject to different rules and laws than each other. The distinction helps define  when exactly sponsorship can occur, and so while not technically necessary, it is useful for the purpose of brevity. Limitations. There are very few syntacticians who would consider themselves to be practitioners of APG or its descendants. There are a few reasons for this. First, although it attempts to handle all aspects of language using pair networks and arc pairs, there is not a suitable APG account of phonology. Second, the complexity of an APG structure in general increases exponentially with sentence complexity. For instance, in sentences with "to"-complements, nodes in the complement have arc relations with nodes outside of  it, making for mathematically-represented though difficult-to-follow structures.