Título:
|
Automatic evaluation of context-free grammars (system description)
|
Autor/a:
|
Creus López, Carles; Godoy Balil, Guillem
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
Abstract:
|
We implement an online judge for context-free grammars. Our system contains a list of problems describing formal languages, and asking for grammars generating them. A submitted proposal grammar receives a verdict of acceptance or rejection depending on whether the judge determines that it is equivalent to the reference solution grammar provided by the problem setter. Since equivalence of context-free grammars is an undecidable problem, we consider a maximum length l and only test equivalence of the generated languages up to words of length l. This length restriction is very often sufficient for the well-meant submissions. Since this restricted problem is still NP-complete, we design and implement methods based on hashing, SAT, and automata that perform well in practice. © 2014 Springer International Publishing Switzerland. |
Abstract:
|
Peer Reviewed |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Sistemes d'informació -Context-free grammar -Automata theory -Biomineralization -Context free grammars -Differentiation (calculus) -automata -equivalence -grammars -hashing -SAT -Context free languages -Gramàtica lliure de context |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Objeto de conferencia |
Editor:
|
Springer
|
Compartir:
|
|