Second-order abstract categorial grammars as hyperedge replacement grammars
Journal of Logic, Language and Information 19 (2) (2010)
| Abstract | Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string and tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,865 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesSylvain Salvati (2010). On the Membership Problem for Non-Linear Abstract Categorial Grammars. Journal of Logic, Language and Information 19 (2).
Daniel Feinstein & Shuly Wintner (2008). Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17 (3).
Barbara Dziemidowicz-Gryz (2007). On Learnability of Restricted Classes of Categorial Grammars. Studia Logica 85 (2):153 - 169.
Wojciech Buszkowski (1988). Gaifman's Theorem on Categorial Grammars Revisited. Studia Logica 47 (1):23 - 33.
Wojciech Zielonka (1978). A Direct Proof of the Equivalence of Free Categorial Grammars and Simple Phrase Structure Grammars. Studia Logica 37 (1):41 - 57.
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Christian Retoré & Sylvain Salvati (2010). A Faithful Representation of Non-Associative Lambek Grammars in Abstract Categorial Grammars. Journal of Logic, Language and Information 19 (2).
Philippe de Groote & Sylvain Pogodalla (2004). On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms. Journal of Logic, Language and Information 13 (4).
Analytics
Monthly downloads |
Added to index2009-12-21Total downloads3 ( #203,804 of 556,807 )Recent downloads (6 months)1 ( #64,847 of 556,807 )How can I increase my downloads? |
My notes
Discussion
