Detecting and explaining (in)equivalence of context-free grammars

• URL: http://arxiv.org/abs/2407.18220v1
• Date: Thu, 25 Jul 2024 17:36:18 GMT
• Title: Detecting and explaining (in)equivalence of context-free grammars
• Authors: Marko Schmellenkamp, Thomas Zeume, Sven Argo, Sandra Kiefer, Cedric Siems, Fynn Stebel,
• Abstract summary: 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.
• Score: 0.6282171844772422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Incremental Context-free Grammar Inference in Black Box Settings [17.601446198181048]
  Black-box context-free grammar inference is a significant challenge in many practical settings. We propose a novel method that segments example strings into smaller units and incrementally infers the grammar. Our approach, named Kedavra, has demonstrated superior grammar quality (enhanced precision and recall), faster runtime, and improved readability through empirical comparison.
  arXiv  Detail & Related papers  (2024-08-29T17:00:38Z)
• Language Models for Text Classification: Is In-Context Learning Enough? [54.869097980761595]
  Recent foundational language models have shown state-of-the-art performance in many NLP tasks in zero- and few-shot settings. An advantage of these models over more standard approaches is the ability to understand instructions written in natural language (prompts) This makes them suitable for addressing text classification problems for domains with limited amounts of annotated instances.
  arXiv  Detail & Related papers  (2024-03-26T12:47:39Z)
• A logical word embedding for learning grammar [4.111899441919164]
  We introduce the logical grammar emdebbing (LGE) to enable unsupervised inference of lexical categories and syntactic rules from a corpus of text. LGE produces comprehensible output summarizing its inferences, has a completely transparent process for producing novel sentences, and can learn from as few as a hundred sentences.
  arXiv  Detail & Related papers  (2023-04-28T01:53:54Z)
• CLSE: Corpus of Linguistically Significant Entities [58.29901964387952]
  We release a Corpus of Linguistically Significant Entities (CLSE) annotated by experts. CLSE covers 74 different semantic types to support various applications from airline ticketing to video games. We create a linguistically representative NLG evaluation benchmark in three languages: French, Marathi, and Russian.
  arXiv  Detail & Related papers  (2022-11-04T12:56:12Z)
• Multilingual Extraction and Categorization of Lexical Collocations with Graph-aware Transformers [86.64972552583941]
  We put forward a sequence tagging BERT-based model enhanced with a graph-aware transformer architecture, which we evaluate on the task of collocation recognition in context. Our results suggest that explicitly encoding syntactic dependencies in the model architecture is helpful, and provide insights on differences in collocation typification in English, Spanish and French.
  arXiv  Detail & Related papers  (2022-05-23T16:47:37Z)
• Learning grammar with a divide-and-concur neural network [4.111899441919164]
  We implement a divide-and-concur iterative projection approach to context-free grammar inference. Our method requires a relatively small number of discrete parameters, making the inferred grammar directly interpretable.
  arXiv  Detail & Related papers  (2022-01-18T22:42:43Z)
• On The Ingredients of an Effective Zero-shot Semantic Parser [95.01623036661468]
  We analyze zero-shot learning by paraphrasing training examples of canonical utterances and programs from a grammar. We propose bridging these gaps using improved grammars, stronger paraphrasers, and efficient learning methods. Our model achieves strong performance on two semantic parsing benchmarks (Scholar, Geo) with zero labeled data.
  arXiv  Detail & Related papers  (2021-10-15T21:41:16Z)
• Dependency Induction Through the Lens of Visual Perception [81.91502968815746]
  We propose an unsupervised grammar induction model that leverages word concreteness and a structural vision-based to jointly learn constituency-structure and dependency-structure grammars. Our experiments show that the proposed extension outperforms the current state-of-the-art visually grounded models in constituency parsing even with a smaller grammar size.
  arXiv  Detail & Related papers  (2021-09-20T18:40:37Z)
• VLGrammar: Grounded Grammar Induction of Vision and Language [86.88273769411428]
  We study grounded grammar induction of vision and language in a joint learning framework. We present VLGrammar, a method that uses compound probabilistic context-free grammars (compound PCFGs) to induce the language grammar and the image grammar simultaneously.
  arXiv  Detail & Related papers  (2021-03-24T04:05:08Z)
• Montague Grammar Induction [4.321645312120979]
  This framework provides the analyst fine-grained control over the assumptions that the induced grammar should conform to. We focus on the relationship between s(emantic)-selection and c(ategory)-selection, using as input a lexicon-scale acceptability judgment dataset.
  arXiv  Detail & Related papers  (2020-10-15T23:25:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.