2 Search Results for "Drewes, Frank"

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2024.138

Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers

Authors: Paul Gallot, Sebastian Maneth, Keisuke Nakano, and Charles Peyrat

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We present a novel normal form for (total deterministic) macro tree transducers (mtts), called "depth proper normal form". If an mtt is in this normal form, then it is guaranteed that each parameter of each state appears at arbitrary depths in the output trees of that state. Intuitively, if some parameter only appears at certain bounded depths in the output trees of a state, then this parameter can be eliminated by in-lining the corresponding output paths at each call site of that state. We use regular look-ahead in order to determine which of the paths should be in-lined. As a consequence of changing the look-ahead, a parameter that was previously appearing at unbounded depths, may be appearing at bounded depths for some new look-ahead; for this reason, our construction has to be iterated to obtain an mtt in depth-normal form. Using the normal form, we can decide whether the translation of an mtt has linear height increase or has linear size-to-height increase.

Cite as

Paul Gallot, Sebastian Maneth, Keisuke Nakano, and Charles Peyrat. Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 138:1-138:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gallot_et_al:LIPIcs.ICALP.2024.138,
  author =	{Gallot, Paul and Maneth, Sebastian and Nakano, Keisuke and Peyrat, Charles},
  title =	{{Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{138:1--138:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.138},
  URN =		{urn:nbn:de:0030-drops-202818},
  doi =		{10.4230/LIPIcs.ICALP.2024.138},
  annote =	{Keywords: automata, formal language theory, macro tree transducer, normal form}
}

Document

DOI: 10.4230/DagRep.5.3.143

Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122)

Authors: Frank Drewes, Kevin Knight, and Marco Kuhlmann

Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)

Abstract

In natural language processing (NLP) there is an increasing interest in formal models for processing graphs rather than more restricted structures such as strings or trees. Such models of graph transformation have previously been studied and applied in various other areas of computer science, including formal language theory, term rewriting, theory and implementation of programming languages, concurrent processes, and software engineering. However, few researchers from NLP are familiar with this work, and at the same time, few researchers from the theory of graph transformation are aware of the specific desiderata, possibilities and challenges that one faces when applying the theory of graph transformation to NLP problems. The Dagstuhl Seminar 15122 "Formal Models of Graph Transformation in Natural Language Processing" brought researchers from the two areas together. It initiated an interdisciplinary exchange about existing work, open problems, and interesting applications.

Cite as

Frank Drewes, Kevin Knight, and Marco Kuhlmann. Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122). In Dagstuhl Reports, Volume 5, Issue 3, pp. 143-161, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{drewes_et_al:DagRep.5.3.143,
  author =	{Drewes, Frank and Knight, Kevin and Kuhlmann, Marco},
  title =	{{Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122)}},
  pages =	{143--161},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{3},
  editor =	{Drewes, Frank and Knight, Kevin and Kuhlmann, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.143},
  URN =		{urn:nbn:de:0030-drops-53484},
  doi =		{10.4230/DagRep.5.3.143},
  annote =	{Keywords: Automata theory, Graph transformation, Natural language processing}
}

Refine by Author
1 Drewes, Frank
1 Gallot, Paul
1 Knight, Kevin
1 Kuhlmann, Marco
1 Maneth, Sebastian
Show More...

Refine by Classification
1 Theory of computation → Transducers

Refine by Keyword
1 Automata theory
1 Graph transformation
1 Natural language processing
1 automata
1 formal language theory
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2015
1 2024