Presentation

Introduction

Abstract categorial grammars (ACGs) were introduced by de Groote (2001)⊕de Groote, Philippe. 2001. “Towards abstract categorial grammars.” In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, 148–55. Toulouse, France, France. doi: 10.3115/1073012.1073045.. They derive from type-theoretic grammars in the tradition of (Lambek 1958; Curry 1961)⊕Lambek, Joachim. 1958. “The Mathematics of Sentence Structure.” American Mathematical Monthly 65 (3): 154–70. doi: 10.2307/2310058.⊕Curry, Haskell Brooks. 1961. “Some Logical Aspects of Grammatical Structure.” In Structure of Language and Its Mathematical Aspects: Proceedings of the Twelfth Symposium in Applied Mathematics, edited by Roman Jakobson, 56–68. American Mathematical Society. http://www.ams.org/books/psapm/012/., and (Montague 1973)⊕Montague, Richard. 1973. “The Proper Treatment of Quantification in Ordinary English.” In Approaches to Natural Language: Proceedings of the 1970 Stanford Workshop on Grammar and Semantics, edited by Jaakko Hintikka, Julius Moravcsik, and Patrick Suppes, 221–42. Dordrecht: Springer Netherlands. doi: 10.1007/978-94-010-2506-5_10.. They can be considered as a framework in which several grammatical formalisms may be encoded. The definition of an ACG is based on a small set of mathematical primitives from type-theory, λ-calculus, and linear logic. These primitives combine via simple composition rules, offering ACGs a good flexibility. In particular, ACGs generate languages of linear λ-terms, which generalize both string and tree languages.

But ACGs are not restricted to languages of λ-terms encoding strings or trees. They can express logic-based semantic representation languages. And moving from one kind to another kind of language is realized by composing ACGs.

An ACG actually defines two languages: an abstract one and an object one which are defined on an abstract and an object vocabulary, respectively. The former can generally be seen as the set of admissible parse structures, while the latter can be seen as the set of corresponding surface structures in a broad sense: strings, for instance, but also logical formulas.

The relation between the abstract and the object language is defined by a morphism, called a lexicon, that interprets abstract structures into object ones.

Composition of ACGs happens:

either when the object vocabulary of an ACG \mathcal{G}_1 also is the abstract vocabulary of some ACG \mathcal{G}_2,
or when two ACGs \mathcal{G}_1 and \mathcal{G}_2 share the same abstract vocabulary.

For instance, the next figure shows the first composition mode for \mathcal{G}_{\text{derived trees}} and \mathcal{G}_{\text{yield}}, while the second composition mode occurs with \mathcal{G}_{\text{derived trees}} and \mathcal{G}_{\text{sem}}. This architecture is used by Pogodalla (2017)⊕Pogodalla, Sylvain. 2017. “A syntax-semantics interface for Tree-Adjoining Grammars through Abstract Categorial Grammars.” Journal of Language Modelling 5 (3). Institute of Computer Science, Polish Academy of Sciences, Poland: 527–605. doi: 10.15398/jlm.v5i3.193. to encode Tree-Adjoinging Grammars (Joshi, Levy, and Takahashi 1975; Joshi and Schabes 1997)⊕Joshi, Aravind K., Leon S. Levy, and Masako Takahashi. 1975. “Tree Adjunct Grammars.” Journal of Computer and System Sciences 10 (1): 136–63. doi: 10.1016/S0022-0000(75)80019-5.⊕Joshi, Aravind K., and Yves Schabes. 1997. “Tree-Adjoining Grammars.” In Handbook of Formal Languages, edited by Grzegorz Rozenberg and Arto K. Salomaa. Vol. 3. Springer. doi: 10.1007/978-3-642-59126-6_2..

Composing ACGs to encode Tree-Adjoing Grammars

Parsing with ACGs

ACG Hierarchy and Expressive Power

Two scales are useful to characterize the expressive power of ACGs.

The order of an ACG is the maximum order of the type of its constants.
The complexity of an ACG is the maximum order of the interpretation of its atomic types.

\textit{ACG}_{(n,m)} is the class of ACGs whose order is less than n and whose complexity is less than m.

The class of second-order ACGs is of particular interest because of its polynomial parsing property (Salvati 2005)⊕Salvati, Sylvain. 2005. “Matching problem and parsing problem for abstract categorial grammars.” Theses, Institut National Polytechnique de Lorraine. https://hal.univ-lorraine.fr/tel-01750002.. When considering strings as the object language, the generated languages coincide with multiple context-free languages (Salvati 2006)⊕Salvati, Sylvain. 2006. “Encoding second order string ACG with Deterministic Tree Walking Transducers.” In The 11th conference on Formal Grammar, edited by Shuly Wintner, 143–56. FG Online Proceedings. Malaga, Spain: Paola Monachesi; Gerald Penn; Giorgio Satta; Shuly Wintner; CSLI Publications. https://hal.inria.fr/inria-00333886.. When considering trees, the generated languages coincide with the tree languages generated by hyperedge replacement grammars (Kanazawa 2010)⊕Kanazawa, Makoto. 2010. “Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars.” Journal of Logic, Language and Information 19 (2): 137–61. doi: 10.1007/s10849-009-9109-6.. A further refinement on the ACG hierarchy provides a fine-grained correspondence with regular (string or tree) languages, context-free string and linear context-free tree languages, or well-nested multiple context-free languages (string), in particular tree-adjoining languages. The following table sums up some of the formal properties of second-order ACGs (de Groote and Pogodalla 2004; Kanazawa and Salvati 2007)⊕de Groote, Philippe, and Sylvain Pogodalla. 2004. “On the expressive power of Abstract Categorial Grammars: Representing context-free formalisms.” Journal of Logic, Language and Information 13 (4). Springer Verlag: 421–38. doi: 10.1007/s10849-004-2114-x.⊕Kanazawa, Makoto, and Sylvain Salvati. 2007. “Generating control languages with Abstract Categorial Grammars.” In Formal Grammar FG 2007. Ireland: Laura Kallmeyer and Paola Monachesi and Gerald Penn. https://hal.archives-ouvertes.fr/hal-00306222..

	String language	Tree language
\textit{ACG}_{(1,n)}	finite	finete
\textit{ACG}_{(2,1)}	regular	regular
\textit{ACG}_{(2,2)}	context-free	context-free
\textit{ACG}_{(2,3)}	well-nested multiple context-free	\subset 1-visit attribute grammar
\textit{ACG}_{(2,4)}	mildly context-sensitive (multiple context-free)	tree generating hyperedge replacement grammars
\textit{ACG}_{(2,4+n)}	\textit{ACG}_{(2,4)}	\textit{ACG}_{(2,4)}

Reversibility

A crucial property of ACGs is that polynomial parsing does not apply only to string or tree generating grammars, but to any second-order ACG, such as the ones that generate first-order or higher-order logical formulas. Consequently, any second-order ACG generating a logical formula can be used to parse a logical formula and provide the admissible parse structure (if any) that generates this logical formula. The ACG framework is inherently reversible (Dymetman 1994)⊕Dymetman, Marc. 1994. “Inherently Reversible Grammars.” In Reversible Grammars in Natural Language Processing, edited by Tomek Strzalkowski, 33–57. Kluwer Academic Publishers. doi: 10.1007/978-1-4615-2722-0_2., and parsing and generation with second-order ACGs are performed in polynomial time.

For second-order ACGs, parsing algorithms and optimization techniques are grounded on well established fields such as type-theory and Datalog. Kanazawa (2007)⊕Kanazawa, Makoto. 2007. “Parsing and Generation as Datalog Queries.” In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics (Acl 2007), 176–83. Prague, Czech Republic: Association for Computational Linguistics. https://aclanthology.org/P07-1023. showed how parsing of second-order ACGs reduces to Datalog querying, offering a general method for getting efficient tabular parsing algorithms (Kanazawa 2017)⊕Kanazawa, Makoto. 2017. “Parsing and Generation as Datalog Query Evaluation.” IfCoLog Journal of Logics and Their Applications 4 (4): 1103–1211. http://www.collegepublications.co.uk/downloads/ifcolog00013.pdf#page=307.. This parsing method applies whatever the object language: representing strings, trees, and also any kind of (almost linear) \lambda-terms. When the object language consists of logical formulas, the latter can then be parsed as well, and the resulting parse structures can further be interpreted (e.g., as strings) to implement surface realization.

Software

ACGs can be used and tested using the ACG toolkit being developed by the Sémagramme team. A quick start description is available, as well as installation instructions (we recommand using opam). A full user documentation is also available.

The ACG toolkit comes with two binaries. The first one, acgc, compiles grammars declaration (as exemplified in the next code block).

signature strings =
    s : type ;
    string = s → s : type;
    infix + = λ⁰ g f x.g(f x) : string → string → string;
    (*  string : type;
       infix + : string → string → string; *)
    epsilon = λ⁰ x.x : string;
    a, b, c : string;
end

signature CFG1 =
    S : type;
    r1 : S → S → S;
    r2 : S;
end

(* L1 is the Dyck language of well-nested brackets *)
lexicon L1 (CFG1): strings =
    S := string;
    r1 := λ⁰ s s'.a+s+b+s';
    r2 := epsilon
end

Encoding of a context-free grammar

The second one, acg, allows one to load grammars and use them to parse terms, as shown below:

$acg
ACGtk> "a + b + a + a + b + b : string" | parse lexicon=L1 type=S "a + b + a + a + b + b : string"
Parsing time:               285μs
Parse forest building time: 20.4μs
Term (depth = 4, size = 7): r1 r2 (r1 (r1 r2 r2) r2) : S

Example of parsing the term a + b + a + a + b + b with the lexicon L1

ACG Bibliography

Here is a list (sorted by descending publication date) of ACG related publications (by our group or not) we are aware of. Please let us know if you think some relevant publication is missing.

Guillaume, Maxime, Sylvain Pogodalla, and Vincent Tourneur. 2024. “ACGtk: A Toolkit for Developing and Running Abstract Categorial Grammars.” In Functional and Logic Programming. 17th International Symposium, FLOPS 2024, Proceedings, edited by Jeremy Gibbons and Dale Miller, Lecture Notes in Computer Science:13–30. Functional and Logic Programming. 17th International Symposium, Flops 2024, LNCS 14659. Kumamoto, Japan: Springer. doi: 10.1007/978-981-97-2300-3_2.

de Groote, Philippe, Maxime Guillaume, Agathe Helman, Sylvain Pogodalla, and Raphaël Salmon. 2023. “Extending Abstract Categorial Grammars with Feature Structures: Theory and Practice.” In Logic and Engineering of Natural Language Semantics 20 (LENLS20). Osaka, Japan. https://inria.hal.science/hal-04328753.

Cousin, Marie. 2023a. “Meaning-Text Theory within Abstract Categorial Grammars: Towards Paraphrase and Lexical Function Modeling for Text Generation.” In IWCS 2023 - The 15th International Conference on Computational Semantics, edited by Maxime Amblard and Helen Breitholtz. Nancy, France. https://inria.hal.science/hal-04104453.

de Groote, Philippe. 2023. “On the Semantics of Dependencies: Relative Clauses and Open Clausal Complements.” In Logic and Engineering of Natural Language Semantics 20th International Conference, LENLS20, Osaka, Japan, November 18–20, 2023, Revised Selected Papers, edited by Daisuke Bekki, Koji Mineshima, and Elin McCready. Vol. 14569. Osaka, Japan: Springer. https://inria.hal.science/hal-04582203.

Cousin, Marie. 2023b. “Vers une implémentation de la théorie sens-texte avec les grammaires catégorielles abstraites.” In RECITAL/RJCRI 2023, edited by Marie Candito and Thomas Gerald. Paris, France. https://inria.hal.science/hal-04100197.

Ludmann, Pierre, Sylvain Pogodalla, and Philippe de Groote. 2022. “Multityped Abstract Categorial Grammars and Their Composition.” In WoLLIC 2022 - 28th International Workshop on Logic, Language, Information, and Computation, 13468:105–22. Lecture Notes in Computer Science. Iaşi, Romania: Springer International Publishing. doi: 10.1007/978-3-031-15298-6_7.

Richard, Valentin D. 2022. “Simulating Feature Structures with Simple Types.” In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Student Research Workshop, 113–22. Hybrid: Seattle, United States: Association for Computational Linguistics. doi: 10.18653/v1/2022.naacl-srw.15.

Amblard, Maxime, Maria Boritchev, and Philippe de Groote. 2021. “An inquisitive account of wh-questions through event semantics.” In LACL 2021 - Logical Aspects of Computational Linguistics. Montpellier (online), France. https://inria.hal.science/hal-03541222.

Boritchev, Maria. 2021. “Dialogue Modeling in a Dynamic Framework.” PhD thesis, Université de Lorraine ; École doctorale IAEM Lorraine - Informatique, Automatique, Électronique - Électrotechnique, Mathématiques de Lorraine. https://hal.science/tel-03541628.

Kiselyov, Oleg, and Yuya Hoshino. 2020. “Lambek Grammars as Second-Order Abstract Categorial Grammars.” In New Frontiers in Artificial Intelligence, edited by Maki Sakamoto, Naoaki Okazaki, Koji Mineshima, and Ken Satoh, 231–43. Springer International Publishing. doi: 10.1007/978-3-030-58790-1_15.

Pogodalla, Sylvain. 2017a. “Abstract Categorial Grammars as a Model of the Syntax-Semantics Interface for TAG.” In FSMNLP 2017 and TAG+13 conference. Umeå, Sweden. https://inria.hal.science/hal-01583962.

Kiselyov, Oleg. 2017. “Applicative Abstract Categorial Grammars in Full Swing.” In New Frontiers in Artificial Intelligence, edited by Mihoko Otake, Setsuya Kurahashi, Yuiko Ota, Ken Satoh, and Daisuke Bekki, 66–78. Cham: Springer International Publishing. doi: 10.1007/978-3-319-50953-2_6.

Pogodalla, Sylvain. 2017b. “A syntax-semantics interface for Tree-Adjoining Grammars through Abstract Categorial Grammars.” Journal of Language Modelling 5 (3). Institute of Computer Science, Polish Academy of Sciences, Poland: 527–605. doi: 10.15398/jlm.v5i3.193.

Kanazawa, Makoto. 2017. “Parsing and Generation as Datalog Query Evaluation.” IfCoLog Journal of Logics and Their Applications 4 (4): 1103–1211. http://www.collegepublications.co.uk/downloads/ifcolog00013.pdf#page=307.

Kallmeyer, Laura, Rainer Osswald, and Sylvain Pogodalla. 2017. “Quantification in Frame Semantics with Binders and Nominals of Hybrid Logic.” Journal of Language Modelling 5 (2). Institute of Computer Science, Polish Academy of Sciences, Poland. doi: 10.15398/jlm.v5i2.147.

Pogodalla, Sylvain. 2016a. “ACGTK: un outil de développement et de test pour les grammaires catégorielles abstraites.” In Actes de la 23ème Conférence sur le Traitement Automatique des Langues Naturelles, 31ème Journées d’Études sur la Parole, 18ème Rencontre des Étudiants Chercheurs en Informatique pour le Traitement Automatique des Langues (JEP-TALN-RECITAL 2016), edited by Laurence Danlos and Thierry Hamon, 1–2. Paris, France: Association pour le Traitement Automatique des Langues. https://aclanthology.org/2016.jeptalnrecital-demo.1/.

Maskharashvili, Aleksandre. 2016. “Discourse Modeling with Abstract Categorial Grammars.” PhD thesis, Université de Lorraine. https://inria.hal.science/tel-01412765.

Danlos, Laurence, Aleksandre Maskharashvili, and Sylvain Pogodalla. 2016. “Interfacing Sentential and Discourse TAG-based Grammars.” In Proceedings of the 12th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+12), edited by David Chiang and Alexander Koller. Düsseldorf, Germany. https://aclanthology.org/W16-3303.

de Groote, Philippe. 2016. “Lambek Categorial Grammars as Abstract Categorial Grammars.” In LENLS 13. Logic and Engineering of Natural Language Semantics 13. Tokyo, Japan. https://inria.hal.science/hal-01412795.

Pogodalla, Sylvain. 2016b. “Parsing and Generation with Abstract Categorial Grammars : From Lexicon to Discourse.” Les rencontres du numérique de l’ANR. https://inria.hal.science/hal-01417895.

de Groote, Philippe. 2015a. “Abstract Categorial Parsing as Linear Logic Programming.” In Proceedings of the 14th Meeting on the Mathematics of Language (MoL 2015), 15–25. Chicago, United States: Association for Computational Linguistics. https://hal.science/hal-01188632.

Clément, Lionel, Jérôme Kirman, and Sylvain Salvati. 2015. “A logical approach to grammar description.” Journal of Language Modelling, Special issue on high-level methodologies for grammar engineering, 3 (1). Institute of Computer Science, Polish Academy of Sciences, Poland: 87–143. doi: 10.15398/jlm.v3i1.94.

Kiselyov, Oleg. 2015. “Applicative Abstract Categorial Grammar.” In NLCS’15. Third Workshop on Natural Language and Computer Science, edited by Makoto Kanazawa, Lawrence S. Moss, and Valeria de Paiva, 32:29–38. EPiC Series in Computing. EasyChair. doi: 10.29007/s2m4.

Danlos, Laurence, Aleksandre Maskharashvili, and Sylvain Pogodalla. 2015. “Grammaires phrastiques et discursives fondées sur les TAG : une approche de D-STAG avec les ACG.” In Actes de la 22e conférence sur le Traitement Automatique des Langues Naturelles (TALN 2015), edited by Pierre Zweigenbaum, Emmanuel Morin, and Pascale Sébillot, 158–69. Caen, France: Association pour le Traitement Automatique des Langues. https://aclanthology.org/2015.jeptalnrecital-long.14/.

Salvati, Sylvain. 2015a. “Lambda-calculus and formal language theory.” Habilitation à diriger des recherches, Université de Bordeaux. https://hal.archives-ouvertes.fr/tel-01253426.

Kirman, Jerome. 2015. “Mise au point d’un formalisme syntaxique de haut niveau pour le traitement automatique des langues.” PhD thesis, Université de Bordeaux. https://theses.hal.science/tel-01267716.

Salvati, Sylvain. 2015b. “Non-linear Second order Abstract Categorial Grammars and deletion.” In NLCS 2015: Natural Language and Computer Science. Kyoto, Japan: Makoto Kanazawa. https://hal.archives-ouvertes.fr/hal-01251127.

de Groote, Philippe. 2015b. “On Logical Relations and Conservativity.” In NLCS’15. Third Workshop on Natural Language and Computer Science, edited by Makoto Kanazawa, Lawrence S. Moss, and Valeria de Paiva, 32:1–11. EasyChair Proceedings in Computing. Kyoto, Japan. doi: 10.29007/gwlt.

Kanazawa, Makoto. 2015. “Syntactic Features for Regular Constraints and an Approximation of Directional Slashes in Abstract Categorial Grammars.” In Proceedings of Empirical Advances in Categorial Grammars (Cg 2015), Esslli 2015 Workshop, edited by Yusuke Kubota and Robert Levine, 34–70. https://makotokanazawa.ws.hosei.ac.jp/publications/approx_proc.pdf.

Danlos, Laurence, Aleksandre Maskharashvili, and Sylvain Pogodalla. 2014a. “An ACG Analysis of the G-TAG Generation Process.” In Proceedings of the 8th International Natural Language Generation Conference (INLG 2014), edited by Margaret Mitchell, Kathleen McCoy, David McDonald, and Aoife Cahill, 35–44. Philadelphia, PA, United States: Association for Computational Linguistics. https://aclanthology.org/W14-4406.

Danlos, Laurence, Aleksandre Maskharashvili, and Sylvain Pogodalla. 2014b. “An ACG View on G-TAG and Its g-Derivation.” In Logical Aspects of Computational Linguistics: 8th International Conference, LACL 2014, Toulouse, France, June 18-20, 2014. Proceedings, edited by Nicholas Asher and Sergei Soloviev, 8535:70–82. Lecture Notes in Computer Science. Toulouse, France: Springer. doi: 10.1007/978-3-662-43742-1_6.

de Groote, Philippe, and Yoad Winter. 2014. “A type-logical account of quantification in event semantics.” In Logic and Engineering of Natural Language Semantics 11. Tokyo, Japan. https://inria.hal.science/hal-01102261.

Danlos, Laurence, Philippe de Groote, and Sylvain Pogodalla. 2014. “A Type-Theoretic Account of Neg-Raising Predicates in Tree Adjoining Grammars.” In New Frontiers in Artificial Intelligence: JSAI-isAI 2013 Workshops, LENLS, JURISIN, MiMI, AAA, and DDS, Kanagawa, Japan, October 27-28, 2013, Revised Selected Papers, edited by Yukiko Nakano, Ken Satoh, and Daisuke Bekki, 8417:3–16. Lecture Notes in Computer Science. Springer International Publishing. doi: 10.1007/978-3-319-10061-6_1.

Danlos, Laurence, Aleksandre Maskharashvili, and Sylvain Pogodalla. 2014c. “Génération de textes : G-TAG revisité avec les Grammaires Catégorielles Abstraites.” In Actes de la 21e conférence sur le Traitement Automatique des Langues Naturelles (TALN 2014), 1:161–72. Marseille, France: Association pour le Traitement Automatique des Langues. https://aclanthology.org/F14-1015.

Maskharashvili, Aleksandre, and Sylvain Pogodalla. 2013. “Constituency and Dependency Relationship from a Tree Adjoining Grammar and Abstract Categorial Grammar Perspective.” In Proceedings of the Sixth International Joint Conference on Natural Language Processing (IJCNLP 2013), edited by Ruslan Mitkov and Jong C. Park, 1257–63. Nagoya, Japan: The Asian Federation of Natural Language Processing. https://aclanthology.org/I13-1179.

Maršík, Jiří, and Maxime Amblard. 2013. “Integration of Multiple Constraints in ACG.” In Logic and Engineering of Natural Language Semantics 10, 1–14. Kanagawa, Japan. https://hal.science/hal-00869748.

Pogodalla, Sylvain, and Florent Pompigne. 2012. “Controlling Extraction in Abstract Categorial Grammars.” In Formal Grammar: 15th and 16th International Conferences, FG 2010, Copenhagen, Denmark, August 2010, FG 2011, Ljubljana, Slovenia, August 2011, Revised Selected Papers, edited by Philippe de Groote and Mark-Jan Nederhof, 7395:162–77. Lecture Notes in Computer Science. Springer Berlin Heidelberg. doi: 10.1007/978-3-642-32024-8_11.

Bourreau, Pierre. 2012. “Jeux de typage et analyse de lambda-grammaires non-contextuelles.” PhD thesis, Université Sciences et Technologies - Bordeaux I. https://theses.hal.science/tel-00733964.

de Groote, Philippe, Sylvain Pogodalla, and Carl Pollard. 2011. “About Parallel and Syntactocentric Formalisms: A Perspective from the Encoding of Convergent Grammar into Abstract Categorial Grammar.” Fundamenta Informaticae 106 (2-4). Polskie Towarzystwo Matematyczne: 211–31. doi: 10.3233/FI-2011-384.

Bourreau, Pierre, and Sylvain Salvati. 2011. “A Datalog recognizer for almost affine lambda-CFGs.” In Mathematics of Language, edited by Springer, 6878:21–38. Nara, Japan. doi: 10.1007/978-3-642-23211-4.

Yoshinaka, Ryo, and Makoto Kanazawa. 2011. “Distributional Learning of Abstract Categorial Grammars.” In Logical Aspects of Computational Linguistics, edited by Sylvain Pogodalla and Jean-Philippe Prost, 251–66. Springer Berlin Heidelberg. doi: 10.1007/978-3-642-22221-4_17.

Blom, Chris, Philippe de Groote, Yoad Winter, and Joost Zwarts. 2011. “Implicit Arguments: Event Modification or Option Type Categories?” In 18th Amsterdam Colloquium on Logic, Language and Meaning, edited by Maria Aloni, Vadim Kimmelman, Floris Roelofsen, Galit Weidman Sassoon, Katrin Schulz, and Matthijs Westera, 7218:240–50. Lecture Notes in Computer Science. Amsterdam, Netherlands: Springer. doi: 10.1007/978-3-642-31482-7_25.

Retoré, Christian, and Sylvain Salvati. 2010. “A Faithful Representation of Non-Associative Lambek Grammars in Abstract Categorial Grammars.” Journal of Logic, Language and Information 19 (2). Springer Verlag: 185–200. https://hal.inria.fr/inria-00409557.

Salvati, Sylvain. 2010. “On the Membership Problem for Non-Linear Abstract Categorial Grammars.” Journal of Logic, Language and Information 19 (2). Springer Verlag: 163–83. doi: 10.1007/s10849-009-9110-0.

Kanazawa, Makoto. 2010. “Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars.” Journal of Logic, Language and Information 19 (2): 137–61. doi: 10.1007/s10849-009-9109-6.

Kanazawa, Makoto. 2009. “Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling. ESSLLI 2009 Lecture Notes, Part I.” https://makotokanazawa.ws.hosei.ac.jp/publications/esslli2009_lectures.pdf.

Pogodalla, Sylvain. 2009. “Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling. ESSLLI 2009 Lecture Notes, Part II.” https://hal.inria.fr/hal-00749297.

Pompigne, Florent. 2009. “Modélisation des mouvements explicites dans les ACG avec le produit dépendant.” In Conférence sur le Traitement Automatique des Langues Naturelles - TALN 2009 - RECITAL. Senlis, France: LIPN. https://inria.hal.science/inria-00441912.

de Groote, Philippe, Sylvain Pogodalla, and Carl Pollard. 2009. “On the Syntax-Semantics Interface: From Convergent Grammar to Abstract Categorial Grammar.” In Logic, Language, Information and Computation: 16th International Workshop, WoLLIC 2009, Tokyo, Japan, June 21-24, 2009. Proceedings, edited by Makoto Kanazawa, Hiroakira Ono, and Ruy de Queiroz, 5514:182–96. Lecture Notes in Computer Science. Tokyo, Japan: Springer. doi: 10.1007/978-3-642-02261-6_15.

Kanazawa, Makoto. 2008. “A Prefix-Correct Earley Recognizer for Multiple Context-Free Grammars.” In Proceedings of the Ninth International Workshop on Tree Adjoining Grammar and Related Frameworks (TAG+9), 49–56. Tübingen, Germany: Association for Computational Linguistics. https://aclanthology.org/W08-2307.

Pogodalla, Sylvain. 2007a. “Ambiguı̈té de portée et approche fonctionnelle des TAG.” In Actes de la 14ème conférence sur le Traitement Automatique des Langues Naturelles (TALN 2007), edited by Nabil Hathout and Philippe Muller, 325–34. Toulouse, France. https://aclanthology.org/2007.jeptalnrecital-long.30/.

Pogodalla, Sylvain. 2007b. “Generalizing a Proof-Theoretic Account of Scope Ambiguity.” In Proceedings of the 7th International Workshop on Computational Semantics (IWCS-7), edited by Harry Bunt. Tilburg, Netherlands. https://hal.inria.fr/inria-00112898.

Kanazawa, Makoto, and Sylvain Salvati. 2007. “Generating control languages with Abstract Categorial Grammars.” In Formal Grammar FG 2007. Ireland: Laura Kallmeyer and Paola Monachesi and Gerald Penn. https://hal.archives-ouvertes.fr/hal-00306222.

Retoré, Christian, and Sylvain Salvati. 2007. “Non-Associative Categorial Grammars and Abstract Categorial Grammars.” In New Directions in Type Theoretic Grammars, 51–58. Ireland: R. Muskens. https://hal.archives-ouvertes.fr/hal-00306393.

Salvati, Sylvain. 2007a. “On the complexity of Abstract Categorial Grammars.” In Mathematics of Language, MOL 10. Ireland. https://hal.archives-ouvertes.fr/hal-00306231.

Salvati, Sylvain. 2007b. “On the membership problem for Non-linear Abstract Categorial Grammars.” In New Directions in Type Theoretic Grammars, 43–50. Ireland: Reinhard Muskens. https://hal.archives-ouvertes.fr/hal-00306230.

de Groote, Philippe, Sarah Maarek, and Ryo Yoshinaka. 2007. “On two Extensions of Abstract Categorial Grammars.” In 14th International Conference on Logic for Programming, Artificial Intel ligence and Reasoning - LPAR 2007, edited by Nachum Dershowitz and Andrei Voronkov, 4790:273–87. Lecture Notes in Computer Science. Yerevan, Armenia: Springer. doi: 10.1007/978-3-540-75560-9_21.

Kanazawa, Makoto. 2007. “Parsing and Generation as Datalog Queries.” In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics (Acl 2007), 176–83. Prague, Czech Republic: Association for Computational Linguistics. https://aclanthology.org/P07-1023.

de Groote, Philippe, and Sarah Maarek. 2007. “Type-theoretic extensions of Abstract Categorial Grammars.” https://hal.inria.fr/inria-00187759.

Kanazawa, Makoto. 2006. “Abstract Families of Abstract Categorial Languages.” Electronic Notes in Theoretical Computer Science 165: 65–80. doi: 10.1016/j.entcs.2006.05.037.

Salvati, Sylvain. 2006a. “Encoding second order string ACG with Deterministic Tree Walking Transducers.” In The 11th conference on Formal Grammar, edited by Shuly Wintner, 143–56. FG Online Proceedings. Malaga, Spain: Paola Monachesi; Gerald Penn; Giorgio Satta; Shuly Wintner; CSLI Publications. https://hal.inria.fr/inria-00333886.

Yoshinaka, Ryo. 2006a. “Extensions and Restrictions of Abstract Categorial Grammars.” PhD thesis, University of Tokyo. http://www.iip.ist.i.kyoto-u.ac.jp/member/ry/PhD_Yoshinaka.pdf.

Yoshinaka, Ryo. 2006b. “Linearization of Affine Abstract Categorial Grammars.” In Proceedings of the 11th Conference on Formal Grammar (Fg 2006). https://web.stanford.edu/group/cslipublications/cslipublications/FG/2006/yoshinaka.pdf.

Salvati, Sylvain. 2006b. “Parsing TAG with Abstract Categorial Grammar.” In TAG+8: Workshop on Tree Adjoining Grammar and Related Formalisms. Sidney, Australia. https://hal.inria.fr/inria-00334009.

Kanazawa, Makoto, and Ryo Yoshinaka. 2005. “Lexicalization of Second-Order ACGs.” NII Technical Report NII-2005-012E. Tokyo: National Institute of Informatics. https://www.nii.ac.jp/TechReports/public_html/05-012E.html.

Salvati, Sylvain. 2005. “Matching problem and parsing problem for abstract categorial grammars.” Theses, Institut National Polytechnique de Lorraine. https://hal.univ-lorraine.fr/tel-01750002.

Yoshinaka, Ryo, and Makoto Kanazawa. 2005. “The Complexity and Generative Capacity of Lexicalized Abstract Categorial Grammars.” In Logical Aspects of Computational Linguistics: 5th International Conference, Lacl 2005, Bordeaux, France, April 28-30, 2005. Proceedings, edited by Philippe Blache, Edward Stabler, Joan Busquets, and Richard Moot, 3492:330–48. LNCS/Lnai. Springer. doi: 10.1007/11422532_22.

Pogodalla, Sylvain. 2004a. “Computing Semantic Representation: Towards ACG Abstract Terms as Derivation Trees.” In Proceedings of the 7th International Workshop on Tree Adjoining Grammar and Related Formalisms (Tag+7), edited by Owen Rambow and Mattew Stone, 64–71. Vancouver, BC, Canada. https://aclanthology.org/W04-3309.

de Groote, Philippe, and Sylvain Pogodalla. 2004. “On the expressive power of Abstract Categorial Grammars: Representing context-free formalisms.” Journal of Logic, Language and Information 13 (4). Springer Verlag: 421–38. doi: 10.1007/s10849-004-2114-x.

Pogodalla, Sylvain. 2004b. “Using and Extending the ACG technology: Endowing Categorial Grammars with an Underspecified Semantic Representation.” In Proceedings of the Categorial Grammars Conference, edited by Michael Moortgat, 197–209. Montpellier, France. https://hal.inria.fr/inria-00108117.

Pogodalla, Sylvain. 2004c. “Vers un statut de l’arbre de dérivation : exemples de construction de représentations sémantiques pour les Grammaires d’Arbres Adjoints.” In Actes de la 11ème conférence sur le Traitement Automatique des Langues Naturelles (TALN 2004), edited by Bernard Bel and Isabelle Marlien, 377–86. Fès, Morocco: Association pour le Traitement Automatique des Langues. https://aclanthology.org/2004.jeptalnrecital-long.3/.

de Groote, Philippe, and Sylvain Pogodalla. 2003. “m-Linear Context-Free Rewriting Systems as Abstract Categorial Grammars.” In Proceedings of Eighth Meeting on Mathematics of Language (MOL 8), edited by Richard T. Oehrle and James Rogers, 71–80. Bloomington, Indiana, United States. https://hal.inria.fr/inria-00107690.

de Groote, Philippe. 2002. “Tree-Adjoining Grammars as Abstract Categorial Grammars.” In Proceedings of the Sixth International Workshop on Tree Adjoining Grammars and Related Frameworks (Tag+6), 145–50. Università di Venezia. http://aclanthology.org/W02-2220.

de Groote, Philippe. 2001. “Towards abstract categorial grammars.” In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, 148–55. Toulouse, France, France. doi: 10.3115/1073012.1073045.

ACGs were independently introduced but relate to several frameworks:

Grammatical Framework, developped by Aarne Ranta ((2004)⊕Ranta, Aarne. 2004. “Grammatical Framework: A Type-Theoretical Grammar Formalism.” Journal of Functional Programming 14 (2): 145–89. doi: 10.1017/S0956796803004738. and subsequent work).
Lambda Grammars, proposed by Reinhard Muskens (Muskens 2001, 2003)⊕Muskens, Reinhard. 2001. “Lambda Grammars and the Syntax-Semantics Interface.” In Proceedings of the Thirteenth Amsterdam Colloquium, edited by Robert van Rooy and Martin Stokhof, 150–55. Amsterdam. https://let.uvt.nl/general/people/rmuskens/pubs/amscoll.pdf.⊕Muskens, Reinhard. 2003. “Lambdas, Language, and Logic.” In Resource Sensitivity in Binding and Anaphora, edited by Geert-Jan Kruijff and Richard T. Oehrle, 23–54. Studies in Linguistics and Philosophy. Kluwer. doi: 10.1007/978-94-010-0037-6_2..
Interpreted Regular Tree Grammars, proposed by Koller and Kuhlmann (2011)⊕Koller, Alexander, and Marco Kuhlmann. 2011. “A Generalized View on Parsing and Translation.” In Proceedings of the 12th International Conference on Parsing Technologies, 2–13. Dublin, Ireland: Association for Computational Linguistics. https://aclanthology.org/W11-2902..