Please use this identifier to cite or link to this item:
Volltext verfügbar? / Dokumentlieferung
doi:10.22028/D291-36151 | Title: | Efficient Translation with Linear Bimorphisms |
| Author(s): | Teichmann, Christoph Venant, Antoine Koller, Alexander |
| Editor(s): | Klein, Shmuel Tomi Martín-Vide, Carlos Shapira, Dana |
| Language: | English |
| Title: | Language and Automata Theory and Applications : 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings |
| Startpage: | 308 |
| Endpage: | 320 |
| Publisher/Platform: | Springer |
| Year of Publication: | 2018 |
| Place of publication: | Cham |
| Title of the Conference: | LATA 2018 |
| Place of the conference: | Ramat Gan, Israel |
| Publikation type: | Conference Paper |
| Abstract: | We show that the image of a regular tree language under a linear bimorphism over binary signatures can be computed in linear time in the size of the input automaton. We do this by transformation into a novel normal form. Our result applies to the translation and parsing complexity of a wide range of grammar formalisms used in computational linguistics, which can now be shown in a uniform way. |
| DOI of the first publication: | 10.1007/978-3-319-77313-1_24 |
| URL of the first publication: | https://link.springer.com/chapter/10.1007/978-3-319-77313-1_24 |
| Link to this record: | hdl:20.500.11880/32919 http://dx.doi.org/10.22028/D291-36151 |
| ISBN: | 978-3-319-77313-1 978-3-319-77312-4 |
| Date of registration: | 17-May-2022 |
| Notes: | Lecture notes in computer science ; 10792 |
| Faculty: | P - Philosophische Fakultät |
| Department: | P - Sprachwissenschaft und Sprachtechnologie |
| Professorship: | P - Prof. Dr. Alexander Koller |
| Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
There are no files associated with this item.
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.