Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics Article Swipe

PDF

Vladislav Ryzhikov , Przemysław Andrzej Wałęga , Michael Zakharyaschev ·

YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.24963/ijcai.2019/256

We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed words timestamped with binary fractions. We identify classes of ontology-mediated queries answering which can be done in AC0, NC1, L, NL, P, and coNP for data complexity, provide their rewritings to first-order logic and its extensions with primitive recursion, transitive closure or datalog, and establish lower complexity bounds.

Related Topics

Computer Science

Ontology

Theoretical Computer Science

Recursion (Computer Science)

Concepts

Datalog Computer science Transitive closure Description logic Semantics (computer science) Ontology Theoretical computer science Conjunctive query Recursion (computer science) Event (particle physics) Temporal logic Programming language Information retrieval Mathematics Discrete mathematics Relational database Physics Epistemology Quantum mechanics Philosophy

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.24963/ijcai.2019/256
PDF: https://www.ijcai.org/proceedings/2019/0256.pdf
OA Status: gold
Cited By: 21
References: 32
Related Works: 10
OpenAlex ID: https://openalex.org/W2965511917

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2965511917

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.24963/ijcai.2019/256

Digital Object Identifier
Title: Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2019

Year of publication
Publication date: 2019-07-28

Full publication date if available
Authors: Vladislav Ryzhikov, Przemysław Andrzej Wałęga, Michael Zakharyaschev

List of authors in order
Landing page: https://doi.org/10.24963/ijcai.2019/256

Publisher landing page
PDF URL: https://www.ijcai.org/proceedings/2019/0256.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: gold

Open access status per OpenAlex
OA URL: https://www.ijcai.org/proceedings/2019/0256.pdf

Direct OA link when available
Concepts: Datalog, Computer science, Transitive closure, Description logic, Semantics (computer science), Ontology, Theoretical computer science, Conjunctive query, Recursion (computer science), Event (particle physics), Temporal logic, Programming language, Information retrieval, Mathematics, Discrete mathematics, Relational database, Physics, Epistemology, Quantum mechanics, Philosophy

Top concepts (fields/topics) attached by OpenAlex
Cited by: 21

Total citation count in OpenAlex
Citations by year (recent): 2025: 1, 2024: 1, 2023: 6, 2022: 3, 2021: 5

Per-year citation counts (last 5 years)
References (count): 32

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2965511917
doi	https://doi.org/10.24963/ijcai.2019/256
ids.doi	https://doi.org/10.24963/ijcai.2019/256
ids.mag	2965511917
ids.openalex	https://openalex.org/W2965511917
fwci	1.99703069
type	article
title	Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics
awards[0].id	https://openalex.org/G3958398022
awards[0].funder_id	https://openalex.org/F4320334627
awards[0].display_name
awards[0].funder_award_id	EP/L012138/1
awards[0].funder_display_name	Engineering and Physical Sciences Research Council
awards[1].id	https://openalex.org/G5652537686
awards[1].funder_id	https://openalex.org/F4320334627
awards[1].display_name
awards[1].funder_award_id	EP/S019111/1
awards[1].funder_display_name	Engineering and Physical Sciences Research Council
awards[2].id	https://openalex.org/G7107892453
awards[2].funder_id	https://openalex.org/F4320334627
awards[2].display_name
awards[2].funder_award_id	EP/N014359/1
awards[2].funder_display_name	Engineering and Physical Sciences Research Council
awards[3].id	https://openalex.org/G4741435936
awards[3].funder_id	https://openalex.org/F4320334627
awards[3].display_name
awards[3].funder_award_id	EP/K00607X/1
awards[3].funder_display_name	Engineering and Physical Sciences Research Council
biblio.issue
biblio.volume
biblio.last_page	1857
biblio.first_page	1851
topics[0].id	https://openalex.org/T10215
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998000264167786
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Semantic Web and Ontologies
topics[1].id	https://openalex.org/T10317
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9994999766349792
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Advanced Database Systems and Queries
topics[2].id	https://openalex.org/T11010
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9990000128746033
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1702
topics[2].subfield.display_name	Artificial Intelligence
topics[2].display_name	Logic, Reasoning, and Knowledge
funders[0].id	https://openalex.org/F4320334627
funders[0].ror	https://ror.org/0439y7842
funders[0].display_name	Engineering and Physical Sciences Research Council
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C148230440
concepts[0].level	2
concepts[0].score	0.852593183517456
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1172264
concepts[0].display_name	Datalog
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.6814533472061157
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C128896722
concepts[2].level	2
concepts[2].score	0.6088809370994568
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1501387
concepts[2].display_name	Transitive closure
concepts[3].id	https://openalex.org/C102993220
concepts[3].level	2
concepts[3].score	0.5885037183761597
concepts[3].wikidata	https://www.wikidata.org/wiki/Q387196
concepts[3].display_name	Description logic
concepts[4].id	https://openalex.org/C184337299
concepts[4].level	2
concepts[4].score	0.541111409664154
concepts[4].wikidata	https://www.wikidata.org/wiki/Q1437428
concepts[4].display_name	Semantics (computer science)
concepts[5].id	https://openalex.org/C25810664
concepts[5].level	2
concepts[5].score	0.5159128904342651
concepts[5].wikidata	https://www.wikidata.org/wiki/Q44325
concepts[5].display_name	Ontology
concepts[6].id	https://openalex.org/C80444323
concepts[6].level	1
concepts[6].score	0.5105989575386047
concepts[6].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[6].display_name	Theoretical computer science
concepts[7].id	https://openalex.org/C65647387
concepts[7].level	3
concepts[7].score	0.4976864159107208
concepts[7].wikidata	https://www.wikidata.org/wiki/Q1781706
concepts[7].display_name	Conjunctive query
concepts[8].id	https://openalex.org/C168773036
concepts[8].level	2
concepts[8].score	0.493594765663147
concepts[8].wikidata	https://www.wikidata.org/wiki/Q264164
concepts[8].display_name	Recursion (computer science)
concepts[9].id	https://openalex.org/C2779662365
concepts[9].level	2
concepts[9].score	0.47022128105163574
concepts[9].wikidata	https://www.wikidata.org/wiki/Q5416694
concepts[9].display_name	Event (particle physics)
concepts[10].id	https://openalex.org/C25016198
concepts[10].level	2
concepts[10].score	0.437593013048172
concepts[10].wikidata	https://www.wikidata.org/wiki/Q781833
concepts[10].display_name	Temporal logic
concepts[11].id	https://openalex.org/C199360897
concepts[11].level	1
concepts[11].score	0.28325775265693665
concepts[11].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[11].display_name	Programming language
concepts[12].id	https://openalex.org/C23123220
concepts[12].level	1
concepts[12].score	0.26369285583496094
concepts[12].wikidata	https://www.wikidata.org/wiki/Q816826
concepts[12].display_name	Information retrieval
concepts[13].id	https://openalex.org/C33923547
concepts[13].level	0
concepts[13].score	0.24383017420768738
concepts[13].wikidata	https://www.wikidata.org/wiki/Q395
concepts[13].display_name	Mathematics
concepts[14].id	https://openalex.org/C118615104
concepts[14].level	1
concepts[14].score	0.19948172569274902
concepts[14].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[14].display_name	Discrete mathematics
concepts[15].id	https://openalex.org/C5655090
concepts[15].level	2
concepts[15].score	0.18559378385543823
concepts[15].wikidata	https://www.wikidata.org/wiki/Q192588
concepts[15].display_name	Relational database
concepts[16].id	https://openalex.org/C121332964
concepts[16].level	0
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q413
concepts[16].display_name	Physics
concepts[17].id	https://openalex.org/C111472728
concepts[17].level	1
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q9471
concepts[17].display_name	Epistemology
concepts[18].id	https://openalex.org/C62520636
concepts[18].level	1
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q944
concepts[18].display_name	Quantum mechanics
concepts[19].id	https://openalex.org/C138885662
concepts[19].level	0
concepts[19].score	0.0
concepts[19].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[19].display_name	Philosophy
keywords[0].id	https://openalex.org/keywords/datalog
keywords[0].score	0.852593183517456
keywords[0].display_name	Datalog
keywords[1].id	https://openalex.org/keywords/computer-science
keywords[1].score	0.6814533472061157
keywords[1].display_name	Computer science
keywords[2].id	https://openalex.org/keywords/transitive-closure
keywords[2].score	0.6088809370994568
keywords[2].display_name	Transitive closure
keywords[3].id	https://openalex.org/keywords/description-logic
keywords[3].score	0.5885037183761597
keywords[3].display_name	Description logic
keywords[4].id	https://openalex.org/keywords/semantics
keywords[4].score	0.541111409664154
keywords[4].display_name	Semantics (computer science)
keywords[5].id	https://openalex.org/keywords/ontology
keywords[5].score	0.5159128904342651
keywords[5].display_name	Ontology
keywords[6].id	https://openalex.org/keywords/theoretical-computer-science
keywords[6].score	0.5105989575386047
keywords[6].display_name	Theoretical computer science
keywords[7].id	https://openalex.org/keywords/conjunctive-query
keywords[7].score	0.4976864159107208
keywords[7].display_name	Conjunctive query
keywords[8].id	https://openalex.org/keywords/recursion
keywords[8].score	0.493594765663147
keywords[8].display_name	Recursion (computer science)
keywords[9].id	https://openalex.org/keywords/event
keywords[9].score	0.47022128105163574
keywords[9].display_name	Event (particle physics)
keywords[10].id	https://openalex.org/keywords/temporal-logic
keywords[10].score	0.437593013048172
keywords[10].display_name	Temporal logic
keywords[11].id	https://openalex.org/keywords/programming-language
keywords[11].score	0.28325775265693665
keywords[11].display_name	Programming language
keywords[12].id	https://openalex.org/keywords/information-retrieval
keywords[12].score	0.26369285583496094
keywords[12].display_name	Information retrieval
keywords[13].id	https://openalex.org/keywords/mathematics
keywords[13].score	0.24383017420768738
keywords[13].display_name	Mathematics
keywords[14].id	https://openalex.org/keywords/discrete-mathematics
keywords[14].score	0.19948172569274902
keywords[14].display_name	Discrete mathematics
keywords[15].id	https://openalex.org/keywords/relational-database
keywords[15].score	0.18559378385543823
keywords[15].display_name	Relational database
language	en
locations[0].id	doi:10.24963/ijcai.2019/256
locations[0].is_oa	True
locations[0].source
locations[0].license
locations[0].pdf_url	https://www.ijcai.org/proceedings/2019/0256.pdf
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
locations[0].landing_page_url	https://doi.org/10.24963/ijcai.2019/256
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5038062752
authorships[0].author.orcid	https://orcid.org/0000-0002-6847-6465
authorships[0].author.display_name	Vladislav Ryzhikov
authorships[0].countries	GB
authorships[0].affiliations[0].institution_ids	https://openalex.org/I98259816
authorships[0].affiliations[0].raw_affiliation_string	Birkbeck, University of London, UK
authorships[0].institutions[0].id	https://openalex.org/I98259816
authorships[0].institutions[0].ror	https://ror.org/02mb95055
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I124357947, https://openalex.org/I98259816
authorships[0].institutions[0].country_code	GB
authorships[0].institutions[0].display_name	Birkbeck, University of London
authorships[0].author_position	first
authorships[0].raw_author_name	Vladislav Ryzhikov
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Birkbeck, University of London, UK
authorships[1].author.id	https://openalex.org/A5053108637
authorships[1].author.orcid	https://orcid.org/0000-0003-2922-0472
authorships[1].author.display_name	Przemysław Andrzej Wałęga
authorships[1].countries	GB, PL
authorships[1].affiliations[0].institution_ids	https://openalex.org/I4654613
authorships[1].affiliations[0].raw_affiliation_string	University of Warsaw, Poland
authorships[1].affiliations[1].institution_ids	https://openalex.org/I40120149
authorships[1].affiliations[1].raw_affiliation_string	University of Oxford, UK
authorships[1].institutions[0].id	https://openalex.org/I40120149
authorships[1].institutions[0].ror	https://ror.org/052gg0110
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I40120149
authorships[1].institutions[0].country_code	GB
authorships[1].institutions[0].display_name	University of Oxford
authorships[1].institutions[1].id	https://openalex.org/I4654613
authorships[1].institutions[1].ror	https://ror.org/039bjqg32
authorships[1].institutions[1].type	education
authorships[1].institutions[1].lineage	https://openalex.org/I4654613
authorships[1].institutions[1].country_code	PL
authorships[1].institutions[1].display_name	University of Warsaw
authorships[1].author_position	middle
authorships[1].raw_author_name	Przemyslaw Andrzej Walega
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	University of Oxford, UK, University of Warsaw, Poland
authorships[2].author.id	https://openalex.org/A5001878365
authorships[2].author.orcid	https://orcid.org/0000-0002-2210-5183
authorships[2].author.display_name	Michael Zakharyaschev
authorships[2].countries	GB
authorships[2].affiliations[0].institution_ids	https://openalex.org/I98259816
authorships[2].affiliations[0].raw_affiliation_string	Birkbeck, University of London, UK
authorships[2].institutions[0].id	https://openalex.org/I98259816
authorships[2].institutions[0].ror	https://ror.org/02mb95055
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I124357947, https://openalex.org/I98259816
authorships[2].institutions[0].country_code	GB
authorships[2].institutions[0].display_name	Birkbeck, University of London
authorships[2].author_position	last
authorships[2].raw_author_name	Michael Zakharyaschev
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Birkbeck, University of London, UK
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://www.ijcai.org/proceedings/2019/0256.pdf
open_access.oa_status	gold
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10215
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998000264167786
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Semantic Web and Ontologies
related_works	https://openalex.org/W20972493, https://openalex.org/W2338525844, https://openalex.org/W2951257011, https://openalex.org/W4299540831, https://openalex.org/W2964256304, https://openalex.org/W2896766859, https://openalex.org/W4297895951, https://openalex.org/W4288363924, https://openalex.org/W4301141272, https://openalex.org/W2926816154
cited_by_count	21
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2024
counts_by_year[1].cited_by_count	1
counts_by_year[2].year	2023
counts_by_year[2].cited_by_count	6
counts_by_year[3].year	2022
counts_by_year[3].cited_by_count	3
counts_by_year[4].year	2021
counts_by_year[4].cited_by_count	5
counts_by_year[5].year	2020
counts_by_year[5].cited_by_count	3
counts_by_year[6].year	2019
counts_by_year[6].cited_by_count	2
locations_count	1
best_oa_location.id	doi:10.24963/ijcai.2019/256
best_oa_location.is_oa	True
best_oa_location.source
best_oa_location.license
best_oa_location.pdf_url	https://www.ijcai.org/proceedings/2019/0256.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	proceedings-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
best_oa_location.landing_page_url	https://doi.org/10.24963/ijcai.2019/256
primary_location.id	doi:10.24963/ijcai.2019/256
primary_location.is_oa	True
primary_location.source
primary_location.license
primary_location.pdf_url	https://www.ijcai.org/proceedings/2019/0256.pdf
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
primary_location.landing_page_url	https://doi.org/10.24963/ijcai.2019/256
publication_date	2019-07-28
publication_year	2019
referenced_works	https://openalex.org/W2838709227, https://openalex.org/W1782436202, https://openalex.org/W2965511917, https://openalex.org/W1498203978, https://openalex.org/W2099367286, https://openalex.org/W2566250634, https://openalex.org/W2235742114, https://openalex.org/W2779369300, https://openalex.org/W1527197079, https://openalex.org/W2574526943, https://openalex.org/W4236835455, https://openalex.org/W2026629052, https://openalex.org/W2745704899, https://openalex.org/W2097622845, https://openalex.org/W1549387132, https://openalex.org/W2137862151, https://openalex.org/W2132858301, https://openalex.org/W2139891885, https://openalex.org/W2142614470, https://openalex.org/W2803623806, https://openalex.org/W270081759, https://openalex.org/W2191435020, https://openalex.org/W2740681086, https://openalex.org/W4293765636, https://openalex.org/W1851620109, https://openalex.org/W2763521382, https://openalex.org/W3302859, https://openalex.org/W2963099300, https://openalex.org/W2600455691, https://openalex.org/W2904140812, https://openalex.org/W2573530796, https://openalex.org/W1970956440
referenced_works_count	32
abstract_inverted_index.L,	44
abstract_inverted_index.P,	46
abstract_inverted_index.We	0, 30
abstract_inverted_index.be	39
abstract_inverted_index.by	9
abstract_inverted_index.in	41
abstract_inverted_index.of	5, 33
abstract_inverted_index.or	66
abstract_inverted_index.to	55
abstract_inverted_index.NL,	45
abstract_inverted_index.and	47, 58, 68
abstract_inverted_index.are	22
abstract_inverted_index.can	38
abstract_inverted_index.for	49
abstract_inverted_index.its	59
abstract_inverted_index.the	2, 15
abstract_inverted_index.AC0,	42
abstract_inverted_index.NC1,	43
abstract_inverted_index.coNP	48
abstract_inverted_index.data	3, 20, 50
abstract_inverted_index.done	40
abstract_inverted_index.that	19
abstract_inverted_index.with	27, 61
abstract_inverted_index.logic	12, 57
abstract_inverted_index.lower	70
abstract_inverted_index.their	53
abstract_inverted_index.timed	24
abstract_inverted_index.under	14
abstract_inverted_index.which	37
abstract_inverted_index.words	25
abstract_inverted_index.binary	28
abstract_inverted_index.finite	23
abstract_inverted_index.metric	10
abstract_inverted_index.bounds.	72
abstract_inverted_index.classes	32
abstract_inverted_index.closure	65
abstract_inverted_index.provide	52
abstract_inverted_index.queries	7, 35
abstract_inverted_index.assuming	18
abstract_inverted_index.datalog,	67
abstract_inverted_index.identify	31
abstract_inverted_index.mediated	8
abstract_inverted_index.temporal	11
abstract_inverted_index.answering	6, 36
abstract_inverted_index.establish	69
abstract_inverted_index.instances	21
abstract_inverted_index.primitive	62
abstract_inverted_index.semantics	17
abstract_inverted_index.complexity	4, 71
abstract_inverted_index.extensions	60
abstract_inverted_index.fractions.	29
abstract_inverted_index.ontologies	13
abstract_inverted_index.recursion,	63
abstract_inverted_index.rewritings	54
abstract_inverted_index.transitive	64
abstract_inverted_index.complexity,	51
abstract_inverted_index.event-based	16
abstract_inverted_index.first-order	56
abstract_inverted_index.investigate	1
abstract_inverted_index.timestamped	26
abstract_inverted_index.ontology-mediated	34
cited_by_percentile_year.max	98
cited_by_percentile_year.min	90
countries_distinct_count	2
institutions_distinct_count	3
citation_normalized_percentile.value	0.8936141
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False