Detecting and Explaining (In-)equivalence of Context-Free Grammars
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913013927247872 |
|---|---|
| author | Schmellenkamp, Marko Zeume, Thomas Argo, Sven Kiefer, Sandra Siems, Cedric Stebel, Fynn |
| author_facet | Schmellenkamp, Marko Zeume, Thomas Argo, Sven Kiefer, Sandra Siems, Cedric Stebel, Fynn |
| contents | We propose a scalable framework for deciding, proving, and explaining (in-)equivalence of context-free grammars. We present an implementation of the framework and evaluate it on large data sets collected within educational support systems. Even though the equivalence problem for context-free languages is undecidable in general, the framework is able to handle a large portion of these datasets. It introduces and combines techniques from several areas, such as an abstract grammar transformation language to identify equivalent grammars as well as sufficiently similar inequivalent grammars, theory-based comparison algorithms for a large class of context-free languages, and a graph-theory-inspired grammar canonization that allows to efficiently identify isomorphic grammars. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18220 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Detecting and Explaining (In-)equivalence of Context-Free Grammars Schmellenkamp, Marko Zeume, Thomas Argo, Sven Kiefer, Sandra Siems, Cedric Stebel, Fynn Formal Languages and Automata Theory Computers and Society Programming Languages We propose a scalable framework for deciding, proving, and explaining (in-)equivalence of context-free grammars. We present an implementation of the framework and evaluate it on large data sets collected within educational support systems. Even though the equivalence problem for context-free languages is undecidable in general, the framework is able to handle a large portion of these datasets. It introduces and combines techniques from several areas, such as an abstract grammar transformation language to identify equivalent grammars as well as sufficiently similar inequivalent grammars, theory-based comparison algorithms for a large class of context-free languages, and a graph-theory-inspired grammar canonization that allows to efficiently identify isomorphic grammars. |
| title | Detecting and Explaining (In-)equivalence of Context-Free Grammars |
| topic | Formal Languages and Automata Theory Computers and Society Programming Languages |
| url | https://arxiv.org/abs/2407.18220 |