Computational solutions for structural constraints. Learning structural permissions in categorial grammar (Q2762867)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1689576
Language Label Description Also known as
default for all languages
No label defined
    English
    Computational solutions for structural constraints. Learning structural permissions in categorial grammar
    scientific article; zbMATH DE number 1689576

      Statements

      0 references
      13 January 2002
      0 references
      Computational solutions for structural constraints. Learning structural permissions in categorial grammar (English)
      0 references
      The need to solve structural constraints arises when we investigate computational solutions to the question: \textit{``in which logics is a given formula deducible?''} This question is posed when one wants to learn the structural permissions for a Categorial Grammar deduction. This paper is part of a project to deal with the question above. Here, we focus on \textit{structural constraints}, a form of Structurally-Free Theorem Proving, that deal with an unknown transformation \(X\) which, when applied to a given set of components \(P_1 \ldots P_n\), generates a desired structure \(Q\). The constraint is treated in the framework of the combinator calculus as \(X P_1 \ldots P_n {\rightarrow} Q\), where the transformation \(X\) is a combinator, the components \(P_i\) and \(Q\) are terms, and \({\rightarrow}\) reads ``reduces to''. We show that in the usual combinator system not all admissible constraints have a solution; in particular, we show that a structural constraint that \textit{represents right-associativity} cannot be solved in it nor in any consistent extension of it. To solve this problem, we introduce the notion of a \textit{restricted combinator system}, which can be consistently extended with \textit{complex combinators} to represent right-associativity. Finally, we show that solutions for admissible structural constraints always exist and can be efficiently computed in such extension. For the entire collection see [Zbl 0967.00057].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references