Characterizing the Program Expressive Power of Existential Rule
Languages
- URL: http://arxiv.org/abs/2112.08136v2
- Date: Fri, 17 Dec 2021 08:43:29 GMT
- Title: Characterizing the Program Expressive Power of Existential Rule
Languages
- Authors: Heng Zhang
- Abstract summary: Existential rule languages have been widely used in in-mediated query answering (OMQA)
The expressive power of representing domain knowledge for OMQA, known as the program expressive power, is not well-understood yet.
In this paper, we establish a number of novel characterizations for the program expressive power of several important existential rule languages.
- Score: 4.38078043834754
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existential rule languages are a family of ontology languages that have been
widely used in ontology-mediated query answering (OMQA). However, for most of
them, the expressive power of representing domain knowledge for OMQA, known as
the program expressive power, is not well-understood yet. In this paper, we
establish a number of novel characterizations for the program expressive power
of several important existential rule languages, including tuple-generating
dependencies (TGDs), linear TGDs, as well as disjunctive TGDs. The
characterizations employ natural model-theoretic properties, and
automata-theoretic properties sometimes, which thus provide powerful tools for
identifying the definability of domain knowledge for OMQA in these languages.
Related papers
- Natural Language Processing RELIES on Linguistics [13.142686158720021]
We argue the acronym RELIES that encapsulates six major facets where linguistics contributes to NLP.
This list is not exhaustive, nor is linguistics the main point of reference for every effort under these themes.
arXiv Detail & Related papers (2024-05-09T17:59:32Z) - NLAS-multi: A Multilingual Corpus of Automatically Generated Natural
Language Argumentation Schemes [4.015890309289342]
We present an effective methodology for the automatic generation of natural language arguments in different topics and languages.
We also present a set of solid baselines and fine-tuned models for the automatic identification of argumentation schemes.
arXiv Detail & Related papers (2024-02-22T11:31:50Z) - ChatRule: Mining Logical Rules with Large Language Models for Knowledge
Graph Reasoning [107.61997887260056]
We propose a novel framework, ChatRule, unleashing the power of large language models for mining logical rules over knowledge graphs.
Specifically, the framework is initiated with an LLM-based rule generator, leveraging both the semantic and structural information of KGs.
To refine the generated rules, a rule ranking module estimates the rule quality by incorporating facts from existing KGs.
arXiv Detail & Related papers (2023-09-04T11:38:02Z) - Dissociating language and thought in large language models [52.39241645471213]
Large Language Models (LLMs) have come closest among all models to date to mastering human language.
We ground this distinction in human neuroscience, which has shown that formal and functional competence rely on different neural mechanisms.
Although LLMs are surprisingly good at formal competence, their performance on functional competence tasks remains spotty.
arXiv Detail & Related papers (2023-01-16T22:41:19Z) - Formal Specifications from Natural Language [3.1806743741013657]
We study the ability of language models to translate natural language into formal specifications with complex semantics.
In particular, we fine-tune off-the-shelf language models on three datasets consisting of structured English sentences.
arXiv Detail & Related papers (2022-06-04T10:49:30Z) - Including Signed Languages in Natural Language Processing [48.62744923724317]
Signed languages are the primary means of communication for many deaf and hard of hearing individuals.
This position paper calls on the NLP community to include signed languages as a research area with high social and scientific impact.
arXiv Detail & Related papers (2021-05-11T17:37:55Z) - SIGTYP 2020 Shared Task: Prediction of Typological Features [78.95376120154083]
A major drawback hampering broader adoption of typological KBs is that they are sparsely populated.
As typological features often correlate with one another, it is possible to predict them and thus automatically populate typological KBs.
Overall, the task attracted 8 submissions from 5 teams, out of which the most successful methods make use of such feature correlations.
arXiv Detail & Related papers (2020-10-16T08:47:24Z) - Linguistic Typology Features from Text: Inferring the Sparse Features of
World Atlas of Language Structures [73.06435180872293]
We construct a recurrent neural network predictor based on byte embeddings and convolutional layers.
We show that some features from various linguistic types can be predicted reliably.
arXiv Detail & Related papers (2020-04-30T21:00:53Z) - Model-theoretic Characterizations of Existential Rule Languages [9.845164265154832]
Existential rules, a.k.a. dependencies in databases, are a family of important logical languages widely used in computer science and artificial intelligence.
We establish model-theoretic characterizations for a number of existential rule languages such as (disjunctive) embedded dependencies,generating dependencies (TGDs), (frontier-)guarded TGDs and linear TGDs.
As a natural application of these characterizations, complexity bounds for the rewritability of above languages are also identified.
arXiv Detail & Related papers (2020-01-23T17:29:18Z) - Cross-lingual, Character-Level Neural Morphological Tagging [57.0020906265213]
We train character-level recurrent neural taggers to predict morphological taggings for high-resource languages and low-resource languages together.
Learning joint character representations among multiple related languages successfully enables knowledge transfer from the high-resource languages to the low-resource ones, improving accuracy by up to 30% over a monolingual model.
arXiv Detail & Related papers (2017-08-30T08:14:34Z)
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.