60 %
40 %
Information about fg04

Published on November 28, 2007

Author: Rafael

Source: authorstream.com

Local Parallel Rewriting : Theory and Applications *:  Local Parallel Rewriting : Theory and Applications * Giorgio Satta University of Padua * Joint work with : D. Melamed, O. Rambow, B. Wellington Slide2:  Part I : Introduction Parallel rewriting Locality Part II : Theory Descriptional complexity Normal forms and language hierarchy Part III : Applications Synchronous rewriting Translation Algorithms Summary : Slide3:  In Computational Linguistics, formal grammars are used to model the syntactic structure of natural language sentences Syntactic modeling is fundamental to applications such as natural language understanding, machine translation, etc. We can abstractly view a grammar as a set of elementary objects (productions) that represent descriptions of basic syntactic relations. These objects are then combined in order to obtain syntactic structures Slide4:  Example : Context-Free Grammars (CFGs) S[went] ® NP[pat] VP[went] VP[went] ® VP[went] Adv[early] VP[went] ® V[went] NP[home] V[went] ® went S[went] Adv[early] VP[went] NP[pat] VP[went] NP[home] V[went] went Slide5:  So called “long distance” relations cannot be directly represented by CFGs Example : extraction what did Alice eat ? S[eat] ® NP[what] S[eat] VP[eat] ® V[eat] NP[e] There is no direct dependence between the two productions above Slide6:  Several other constructions are problematic for CFGs Topicalization I enjoyed the soup, but the main course I thought was awful Clitic climbing Mari lo queria terminar de hacer Scrambling … dass den Kuhlschrank niemand zu reparieren versprochen hat Slide7:  A related problem arises in machine translation, where we want to relate phrases that correspond under the translation Example : damoy Pat rano pashol Pat went home early Slide8:  Several solutions have been proposed in the literature : Enriching CFGs with feature structures (HPSG, LFG, …) Use of logical constraints (ID/LP, linearization grammars) Use of special purpose operators (domain union, HPSG) Local parallel rewriting (TAG, LCFRS, …) Slide9:  A parallel rewriting system defines elementary objects that allow simultaneous rewriting of a sentential form at several places : Example : TAG Slide10:  The simplest way we can implement parallel rewriting is by using tuples of context-free productions (A1 ® a1 , … , Ar ® ar ) and define rewriting as the simultaneous application of all the production components g1 A1 g2 … gr -1 Ar gr  g1 a1 g2 … gr -1 ar gr Slide11:  Several parallel rewriting systems have been defined in the literature, as for instance Matrix Grammars, Vector Grammars, Scattered Context Grammars, etc. These systems are too powerful. They can generate NP-complete languages Non-semilinear languages Slide12:  Local rewriting is a restriction that requires each application of a production to rewrite symbols that have been introduced in a single step in a sentential form Example : (A ® ABA , A ® BA )  A B A C B A  A B A B A C B B A A C A Slide13:  Local rewriting can be implemented using superscript indices to distinguish among different occurrences of the same symbol Example : (A ® A (1) B (1) A (1) , A ® B (1) A (1) ) A (1) C (1) A (1)  A (2) B (2) A (2) C (1) B (2) A (2)  A (3) B (3) A (3) B (2) A (2) C (1) B (2) B (3) A (3) Slide14:  By combining parallel rewriting and local rewriting we obtain a local parallel grammar Example : damoy Pat rano pashol lit: home Pat early went Pat went home early (S[pashol] ® VP[pashol](1) NP[pat](2) VP[pashol] (1)) (VP[pashol] ® VP[pashol](1) , VP[pashol] ® Adv[rano](2) VP[pashol](1)) (VP[pashol] ® NP[damoy](1) , VP[pashol] ® V[pashol](2)) Slide15:  Example (cont’d) : S[pashol](1)  VP[pashol](2) NP[pat](3) VP[pashol](2)  VP[pashol](4) NP[pat](3) Adv[rano](5) VP[pashol](4)  NP[damoy](6) NP[pat](3) Adv[rano](5) V[pashol](7) * damoy Pat rano pashol Slide16:  Parallelism and locality have been exploited in many rewriting systems that have been independently defined in the literature, motivated by different application domains All these superficially different systems were later shown to be generatively equivalent This provides evidence that parallel rewriting and local rewriting are “natural” notions Slide17:  Known local parallel rewriting systems : Syntax-directed compilers Deterministic Tree-Walking Transducers (Aho and Ullman, 1971) Visual and relational languages, syntactic pattern matching and biological data modeling String generating Context-Free Hypergraph Grammars (Bauderon & Courcelle, 1987; Habel & Kreowsky, 1987) Formal language and translation theory Finite Copying Top-Down Tree-to-String Transducers (Engelfriet et al., 1980) Local Unordered Scattered Grammars (Rambow & Satta, 1998) Slide18:  Known local parallel rewriting systems (cont’d) : Natural language processing Linear Context-Free Rewriting Systems (Vijay-Shanker, Weir & Joshi, 1987) Multiple Context-Free Grammars (Kasami et al., 1987) Multi-Component Tree Adjoining Grammars (Weir, 1988) Finite-copying Lexical Functional Grammars (Seki et al., 1993) Minimalist Grammars (Stabler, 1997) Simple Range Concatenation Grammars (Boullier, 1998) Slide19:  Summary : Part I : Introduction Parallel rewriting Locality Part II : Theory Descriptional complexity Normal forms and language hierarchy Part III : Applications Synchronous rewriting Translation Algorithms Slide20:  Languages generated by local parallel rewriting systems have the following important properties : Are included in the class of Context-Sensitive Languages Can be parsed in deterministic polynomial time Are semilinear These languages belong to the class of Mildly Context Sensitive Languages (Joshi 1985; Joshi, Vijay-Shanker & Weir, 1991) Slide21:  In a local parallel rewriting system, derivations can be described by the trees generated by a context-free grammar : ( S[pashol] ® VP[pashol](1) N[pat](2) VP[pashol](1) ) ( N[pat] ® Pat ) . . . . . . ( VP[pashol] ® VP[pashol](1), VP[pashol] ® Adv[rano](2) VP[pashol] ) ( VP[pashol] ® NP[damoy](1), VP[pashol] ® V[pashol](2) ) Slide22:  Parallelism and locality can be viewed as resources and can therefore be measured Degree of parallelism = fan-out max number of components in productions Degree of locality = rank max number of productions that can rewrite a local domain max branching in underlying derivation Slide23:  Example : Slide24:  Examples : Linear Context-Free Languages : f = 1 , r = 1 Context-Free Languages : f = 1 , r = 2 Tree-Adjoining Languages : f = 2 , r = 2 Questions: Are there normal forms with bounded fan-out ? Are there normal forms with bounded rank ? Can we “trade” the two resources ? Slide25:  Fan-out = f , rank = r LCFL nl-CFL TAL CCL3 f = 1 2 3 4 r = 1 2 . . . 3 4 ET0Lf2 Slide26:  Summary : Part I : Introduction Parallel rewriting Locality Part II : Theory Descriptional complexity Normal forms and language hierarchy Part III : Applications Synchronous rewriting Translation Algorithms Slide27:  A synchronous grammar is a formal model of translation The model combines grammars by pairing productions that represent corresponding phrases Rewriting is carried out synchronously Examples : Finite Transducers Syntax Directed Translation Schemata Synchronous Tree Adjoining Grammars Slide28:  Example : ongaku wo kiku lit: music to listening listening to music [ VP[listening] ® V[listening](1) PP[music](2) , VP[kiku] ® PP[ongaku](2) V[kiku](1) ] [ PP[music] ® P[to](1) NP[music](2) , PP[ongaku] ® NP[ongaku](2) P[wo](1) ] Slide29:  Synchronous grammars can be viewed as specific applications of local parallel rewriting : Parallelism is exploited to rewrite on several dimensions Locality is exploited to enforce synchronous rewriting In this way we have a common and well-understood framework for investigating synchronous rewriting and for comparing already known synchronous formalisms Slide30:  Example : damoy Pat rano pashol lit: home Pat early went Pat went home early [ (S[pashol] ® VP[pashol](1) NP[pat](2) VP[pashol] (1)), (S[went] ® NP[pat](2) VP[went] (1)) ] . . . [ (VP[pashol] ® NP[damoy](1), VP[pashol] ® V[pashol](2)), (VP[went] ® V[went](2) NP[home](1)) ] Slide31:  Example (cont’d) : [ S[pashol](1) , S[went](1) ]  [ VP[pashol](2) NP[pat](3) VP[pashol](2) , NP[pat](3) VP[went](2) ]  [ VP[pashol](4) NP[pat](3) Adv[rano](5) VP[pashol](4), NP[pat](3) VP[went](4) Adv[early](5) ]  [ NP[damoy](6) NP[pat](3) Adv[rano](5) V[pashol](7), NP[pat](3) V[went](7) NP[home](6) Adv[early](5) ] * [ damoy Pat rano pashol, Pat went home early ] Slide32:  Translation problem for synchronous grammar G = ‹G1, G2› : Input string u Output set T (G, u ) of all strings that translate u (and their derivations) We encode T (G, u ) as a local parallel grammar Slide33:  Assume synchronous grammar G = ‹G1, G2› : L (Gj ) = language freely generated by grammar component Gj Tj = projection on the j –th dimension of translation T (G ) In general we have L (Gj ) ≠ Tj We can construct a local parallel grammar auto-proj(G, j ) that generates Tj Weak language preservation property Slide34:  We can intersect a synchronous translation T (G ) with relation L (M1) × L (M2), where M1 , M2 are finite automata This is done through a generalization of a construction for CFG due to (Bar-Hillel et al., 1964) The result is a synchronous grammar Slide35:  Algorithm : Construct G by intersecting G and finite automata M1 and M2, where M1 generates {u} and M2 generates S* Construct local parallel grammar auto-proj(G , 2) Slide36:  Local parallel rewriting systems have been used in several fields of Computer Science These languages form a two-dimensional non-collapsing hierarchy on the fan-out and rank parameters Synchronous rewriting can be viewed as a specific application of local parallel rewriting Translation algorithms can be developed on the basis of already known parsing techniques

Add a comment

Related presentations

Related pages


fg04.de Die Domain "fg04.de" ist nicht verfügbar.
Read more

Artikel »FG04« Halsband mit Bänder | Geschenke Gerdes

Halsband mit Bänder ... Auf Wunsch drucken wir Ihren Text. Für mehr Info, siehe bitte Rubrik Schokolade
Read more

Modellkunst aus dem Hause GvB

Fertig-Gelände "Sommer" Spur Z: FG04-001: Fertig-Gelände im Sommerstil zum Weiterbauen, Spur "Z" (1:220). Für ein Gleisoval. Sie benötigen 4 x 8510 und ...
Read more

Artikel »FG04« Halsband mit Bänder | Geschenke Gerdes

Halsband mit Bänder ... Artikel »HG03« Tischkarten, Tischdekoration Bonbonieren Gastgeschenke zur Hochzeit oder Jubiläen!
Read more

Rote Röhrenspinne – Wikipedia

Rote Röhrenspinne; Rote Röhrenspinne (Eresus kollari), Männchen. Systematik; Klasse: Spinnentiere (Arachnida) Ordnung: Webspinnen (Araneae) Familie ...
Read more

FG04 Review | Yamaha | Acoustic Guitars | Reviews ...

FG04 Reviewed by: Mrmachine628, on march 14, 2005 0 of 0 people found this review helpful
Read more

Green Dutchman Achtmaal > Ihr Partner in Gartenpflanzen ...

fg04.jpg: fg05.jpg: fg06.jpg: fg07.jpg: fg08.jpg: fg09.jpg: fg10.jpg: fg11.jpg: fg12.jpg: fg13.jpg: fg14.jpg: fg15.jpg: fg16.jpg: fg17.jpg: fg18.jpg: fg19 ...
Read more

Watch Videos Online | FG04 | Veoh.com

added: 6 yrs ago : length: 47:23: file size: 386.35 MB : language: Japanese: tags: fg 04
Read more

Seminar Detailinfo

FG04. Termin. 07.03. - 11.03.2016. Veranstaltungsort. 74821 Mosbach bei Heilbronn. Seminarinhalte. Im Mittelpunkt der Förderwoche steht die Vermittlung ...
Read more

How-To: Root SAMSUNG SCH-R940 gingerbread.fg04 2.3.6

How-To: Root SAMSUNG SCH-R940 (gingerbread.fg04) 2.3.6. Ready to root your SCH-R940? Thanks to One Click Root, rooting has never been safer, easier, or faster.
Read more