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
13 January 2002
0 references
0.8778846
0 references
0.8614064
0 references
0.8541844
0 references
0.8445143
0 references
0.8436363
0 references
0.8411795
0 references
0.8392075
0 references
0.8386924
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