Bimorphisms and synchronous grammars
We tend to think of the study of language as proceeding by characterizing the strings and structures of a language, and we think of natural language processing as using those structures to build systems of utility in manipulating the language. But many language-related problems are more fruitfully v...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Computer Science, Polish Academy of Sciences
2014-07-01
|
| Series: | Journal of Language Modelling |
| Subjects: | |
| Online Access: | https://jlm.ipipan.waw.pl/index.php/JLM/article/view/84 |
| _version_ | 1818298281812295680 |
|---|---|
| author | Stuart M. Shieber |
| author_facet | Stuart M. Shieber |
| author_sort | Stuart M. Shieber |
| collection | DOAJ |
| description | We tend to think of the study of language as proceeding by characterizing the strings and structures of a language, and we think of natural language processing as using those structures to build systems of utility in manipulating the language. But many language-related problems are more fruitfully viewed as requiring the specification of a relation between two languages, rather than the specification of a single language.
We provide a synthesis and extension of work that unifies two approaches to such language relations: the automata-theoretic approach based on tree transducers that transform trees to their counterparts in the relation, and the grammatical approach based on synchronous grammars that derive pairs of trees in the relation. In particular, we characterize synchronous tree-substitution grammars and synchronous tree-adjoining grammars in terms of bimorphisms, which have previously been used to characterize tree transducers. In the process, we provide new approaches to formalizing the various concepts: a metanotation for describing varieties of tree automata and transducers in equational terms; a rigorous formalization of tree-adjoining and tree-substitution grammars and their synchronous counterparts, using trees over ranked alphabets; and generalizations of tree-adjoining grammar allowing multiple adjunction. |
| first_indexed | 2024-12-13T04:32:50Z |
| format | Article |
| id | doaj.art-8c1dc9bd482e455b9156bfb0bcf2ed37 |
| institution | Directory Open Access Journal |
| issn | 2299-856X 2299-8470 |
| language | English |
| last_indexed | 2024-12-13T04:32:50Z |
| publishDate | 2014-07-01 |
| publisher | Institute of Computer Science, Polish Academy of Sciences |
| record_format | Article |
| series | Journal of Language Modelling |
| spelling | doaj.art-8c1dc9bd482e455b9156bfb0bcf2ed372022-12-21T23:59:29ZengInstitute of Computer Science, Polish Academy of SciencesJournal of Language Modelling2299-856X2299-84702014-07-012110.15398/jlm.v2i1.8425Bimorphisms and synchronous grammarsStuart M. Shieber0Harvard UniversityWe tend to think of the study of language as proceeding by characterizing the strings and structures of a language, and we think of natural language processing as using those structures to build systems of utility in manipulating the language. But many language-related problems are more fruitfully viewed as requiring the specification of a relation between two languages, rather than the specification of a single language. We provide a synthesis and extension of work that unifies two approaches to such language relations: the automata-theoretic approach based on tree transducers that transform trees to their counterparts in the relation, and the grammatical approach based on synchronous grammars that derive pairs of trees in the relation. In particular, we characterize synchronous tree-substitution grammars and synchronous tree-adjoining grammars in terms of bimorphisms, which have previously been used to characterize tree transducers. In the process, we provide new approaches to formalizing the various concepts: a metanotation for describing varieties of tree automata and transducers in equational terms; a rigorous formalization of tree-adjoining and tree-substitution grammars and their synchronous counterparts, using trees over ranked alphabets; and generalizations of tree-adjoining grammar allowing multiple adjunction.https://jlm.ipipan.waw.pl/index.php/JLM/article/view/84synchronous grammarstree transducerstree-adjoining grammartree-substitution grammar |
| spellingShingle | Stuart M. Shieber Bimorphisms and synchronous grammars Journal of Language Modelling synchronous grammars tree transducers tree-adjoining grammar tree-substitution grammar |
| title | Bimorphisms and synchronous grammars |
| title_full | Bimorphisms and synchronous grammars |
| title_fullStr | Bimorphisms and synchronous grammars |
| title_full_unstemmed | Bimorphisms and synchronous grammars |
| title_short | Bimorphisms and synchronous grammars |
| title_sort | bimorphisms and synchronous grammars |
| topic | synchronous grammars tree transducers tree-adjoining grammar tree-substitution grammar |
| url | https://jlm.ipipan.waw.pl/index.php/JLM/article/view/84 |
| work_keys_str_mv | AT stuartmshieber bimorphismsandsynchronousgrammars |