Regular transductions with MCFG input syntax

Mark Jan Nederhof; Heiko Vogler

Regular transductions with MCFG input syntax

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that regular transductions for which the input part is generated by some multiple context-free grammar can be simulated by synchronous multiple context-free grammars. We prove that synchronous multiple context-free grammars are strictly more powerful than this combination of regular transductions and multiple context-free grammars.

Original language	English
Title of host publication	Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing
Editors	Andreas Maletti, Heiko Vogler
Place of Publication	Dresden
Publisher	Association for Computational Linguistics
Pages	56-64
Number of pages	9
Publication status	Published - 23 Sept 2019
Event	14th International Conference on Finite-State Methods and Natural Language Processing - Dresden, Dresden, Germany Duration: 23 Sept 2019 → 25 Sept 2019 https://wwwtcs.inf.tu-dresden.de/fsmnlp2019/

Conference

Conference	14th International Conference on Finite-State Methods and Natural Language Processing
Country/Territory	Germany
City	Dresden
Period	23/09/19 → 25/09/19
Internet address	https://wwwtcs.inf.tu-dresden.de/fsmnlp2019/

Keywords

Parsing algorithms
Formal grammars

Access to Document

CopW19-3109
Copyright © 2019 Association for Computational Linguistics. Materials published in or after 2016 are licensed on a Creative Commons Attribution 4.0 International License.
Final published version, 358 KBLicence: CC BY

https://www.aclweb.org/anthology/W19-3109/Licence: CC BY

Cite this

@inproceedings{66c18ee7bd904f8bbe9f15febc52f86d,

title = "Regular transductions with MCFG input syntax",

abstract = "We show that regular transductions for which the input part is generated by some multiple context-free grammar can be simulated by synchronous multiple context-free grammars. We prove that synchronous multiple context-free grammars are strictly more powerful than this combination of regular transductions and multiple context-free grammars.",

keywords = "Parsing algorithms, Formal grammars",

author = "Nederhof, {Mark Jan} and Heiko Vogler",

year = "2019",

month = sep,

day = "23",

language = "English",

pages = "56--64",

editor = "Andreas Maletti and Heiko Vogler",

booktitle = "Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing",

publisher = "Association for Computational Linguistics",

note = "14th International Conference on Finite-State Methods and Natural Language Processing ; Conference date: 23-09-2019 Through 25-09-2019",

url = "https://wwwtcs.inf.tu-dresden.de/fsmnlp2019/",

}

Nederhof, MJ & Vogler, H 2019, Regular transductions with MCFG input syntax. in A Maletti & H Vogler (eds), Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing. Association for Computational Linguistics, Dresden, pp. 56-64, 14th International Conference on Finite-State Methods and Natural Language Processing, Dresden, Saxony, Germany, 23/09/19. <https://www.aclweb.org/anthology/W19-3109/>

Regular transductions with MCFG input syntax. / Nederhof, Mark Jan; Vogler, Heiko.
Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing. ed. / Andreas Maletti; Heiko Vogler. Dresden: Association for Computational Linguistics, 2019. p. 56-64.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Regular transductions with MCFG input syntax

AU - Nederhof, Mark Jan

AU - Vogler, Heiko

PY - 2019/9/23

Y1 - 2019/9/23

N2 - We show that regular transductions for which the input part is generated by some multiple context-free grammar can be simulated by synchronous multiple context-free grammars. We prove that synchronous multiple context-free grammars are strictly more powerful than this combination of regular transductions and multiple context-free grammars.

AB - We show that regular transductions for which the input part is generated by some multiple context-free grammar can be simulated by synchronous multiple context-free grammars. We prove that synchronous multiple context-free grammars are strictly more powerful than this combination of regular transductions and multiple context-free grammars.

KW - Parsing algorithms

KW - Formal grammars

M3 - Conference contribution

SP - 56

EP - 64

BT - Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing

A2 - Maletti, Andreas

A2 - Vogler, Heiko

PB - Association for Computational Linguistics

CY - Dresden

T2 - 14th International Conference on Finite-State Methods and Natural Language Processing

Y2 - 23 September 2019 through 25 September 2019

ER -

Regular transductions with MCFG input syntax

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this