𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Gaifman's theorem on categorial grammars revisited

✍ Scribed by Wojciech Buszkowski

Publisher
Springer Netherlands
Year
1988
Tongue
English
Weight
638 KB
Volume
47
Category
Article
ISSN
0039-3215

No coin nor oath required. For personal study only.

✦ Synopsis

The equivalence of (classical) categorial grammars and context-free grammars, proved by Gaifman [4], is a very basic result of the theory of formal grammars (an essentially equivalent result is known as the Greibach normal form theorem [1], [14]). We analyse the contents of Gaifman's theorem within the framework of structure and type transformations. We give a new proof of this theorem which relies on the algebra of phrase structures and exhibit a possibility to justify the key construction used in Gaifman's ,proof by means of the Lambek calculus of syntactic types [15].

πŸ“œ SIMILAR VOLUMES

Adams theorem on Bernoulli numbers revis
Adams theorem on Bernoulli numbers revisited
✍ R. Thangadurai πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 212 KB

If we denote B n to be nth Bernoulli number, then the classical result of Adams (J. Reine Angew. Math. 85 (1878) 269) says that p c jn and Γ°p Γ€ 1Þ[n; then p c jB n where p is any odd prime p43: We conjecture that if Γ°p Γ€ 1Þ[n; p c jn and p cΓΎ1 [n for any odd prime p43; then the exact power of p divi

Residual implications revisited. Notes o
Residual implications revisited. Notes on the Smets–Magrez Theorem
✍ MichaΕ‚ BaczyΕ„ski πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 257 KB

It is well known that continuous residual implications are conjugate with the Lukasiewicz implication. This fact was ΓΏrst obtained by Smets and Magrez (Internat. J. Approx. Reason. 1 (1987) 327). In this paper we show that the assumption of the monotonicity in this theorem can be omitted. We are als