Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to be fixed rather than being part of the input. Little is known about restrictions under which truly uniform polynomial parsing is possible. In this paper we propose a low-degree polynomialtime algorithm that solves the uniform parsing problem for a restricted type of hyperedgereplacement grammars which we expect to be of interest for practical applications. (c) 2020 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Martin Alois Rohrmeier, Steffen Alexander Herff, Gabriele Cecchetti
Karl Aberer, Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên