Simulating Feature Structures with Simple Types (2022)

Abstract: Feature structures have been several times considered to enrich categorial grammars in order to build fine-grained grammars. Most attempts to unify both frameworks either model categorial types as feature structures or add feature structures on top of categorial types. We pursue a different approach: using feature structure as categorial atomic types. In this article, we present a procedure to create, from a simplified HPSG grammar, an equivalent abstract categorial grammar (ACG). We represent a feature structure by the enumeration of its totally well-typed upper bounds, so that unification can be simulated as intersection. We implement this idea as a meta-ACG preprocessor.

## introduction feature structures (fss) @xcite have been widely used to represent natural language syntax, particularly by hpsgs (head-driven phrase structure grammars, @xcite ). in the original ideas of categorial grammars @xcite @xcite , only a few number of atomic categories are taken, and complex categories are built on them as simple types. this approach makes it less flexible to capture fine-grained morpho-syntactic phenomena (e.g. agreement or case). grammatical systems combining categorial and feature approaches have been developed, aiming at recovering these fine structures and grammatical interactions, but also allowing a better lexicon organization (e.g. hierarchy inheritance) @xcite . according to @xcite , first generation hybrid systems @xcite @xcite encode categorial logic in feature logic. 1 source code is available at https://doi.org/10. 12763/vwknsa by contrast, second generation hybrid systems @xcite preserve the categorial inferential system by adding a layer of feature structures to categorial type atoms. 2 while the general framework of feature logic may suffer from turing-completeness when regarding time complexity of parsing @xcite , second generation hybrids bypass this issue by restricting feature structure power to subtyping @xcite . however, this restriction forbids the latter to exploit structure-sharing (i.e. reentrancy). more recent systems fall in either generation. unification-based general categorial grammars @xcite encode combinatory categorial grammars @xcite as feature structures using asymmetric default unification. extensions of abstract categorial grammars @xcite to dependent product, variant types and records model feature logic inside type theory @xcite . however, these extensions make it undecidable @xcite . in this article, we advocate for a different, yet intuitive combination of categorial logic and feature logic: representing feature structures as atomic categorial types with no additional operation. unification is not implemented, but simulated by set intersection. this proposal is based on two ideas: we focus here on abstract categorial grammars (acgs). we present a first implementation of the preprocessor, called meta-acg preprocessor. as feature structure are not yet implemented in acgtk @xcite , this program brings the possibility to work with acgs and fss. we also mention how it reduces labor when defining a grammar. the motivation of this work is thus twofold: in section 2, we present our system and its formal proof of work. we exemplify it by exhibiting a transformation from simplified hpsg grammars into acg grammars. in section 3, we present the meta-acg preprocessor. ## conclusion we introduced and formalized a novel way to include feature structures in categorial grammars. our method consists in automatizing the idea of taking feature structures as categorial atomic types. the labor is divided into two separate modules: a preprocessor and a grammar engine. for every type with a feature structure, the preprocessor generates a representative set of categorial types. this creates an intermediary grammar given to the grammar engine. the latter works on these representative categorial types and just have to select right ones when parsing a sentence. we proved that this approach of simulating feature structures by a set of representatives is sound and complete by showing that unification amounts to intersection of these representative sets. having such a preprocessor avoids adding a unification module inside the grammar engine. it is modular and also easier to implement. we evaluated this proposal by implementing a preprocessor for the grammar engine acgtk working on abstract categorial grammars (acg). this provides the first implementation of feature structures in an acg toolkit. example grammars show the well functioning of this method. however, example grammars with a complex system of type hierarchy outlines the limits of the "enumeration-and-intersection" approach. because of combinatorial explosion, the intermediary grammar can get really voluminous and take time to be created. this may restrict uses of such a preprocessor to toy acg grammars only, waiting for a more efficient implementation of feature structures in acgtk.