On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators Article Swipe
Alessandro Artale
,
Anton Gnatenko
,
Vladislav Ryzhikov
,
Michael Zakharyaschev
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.icdt.2025.31
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.icdt.2025.31
Our concern is the data complexity of answering linear monadic datalog queries whose atoms in the rule bodies can be prefixed by operators of linear temporal logic LTL. We first observe that, for data complexity, answering any connected query with operators ○/○- (at the next/previous moment) is either in AC⁰, or in ACC⁰\AC⁰, or NC¹-complete, or L-hard and in NL. Then we show that the problem of deciding L-hardness of answering such queries is PSpace-complete, while checking membership in the classes AC⁰ and ACC⁰ as well as NC¹-completeness can be done in ExpSpace. Finally, we prove that membership in AC⁰ or in ACC⁰, NC¹-completeness, and L-hardness are undecidable for queries with operators ◇/◇- (sometime in the future/past) provided that NC¹ ≠ NL and L ≠ NL.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2501.13762
- https://arxiv.org/pdf/2501.13762
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4406793808
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4406793808Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.icdt.2025.31Digital Object Identifier
- Title
-
On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL OperatorsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-01-01Full publication date if available
- Authors
-
Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, Michael ZakharyaschevList of authors in order
- Landing page
-
https://arxiv.org/abs/2501.13762Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2501.13762Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2501.13762Direct OA link when available
- Concepts
-
Datalog, Computer science, Deductive database, Programming language, Linear temporal logic, Theoretical computer science, MathematicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4406793808 |
|---|---|
| doi | https://doi.org/10.4230/lipics.icdt.2025.31 |
| ids.doi | https://doi.org/10.48550/arxiv.2501.13762 |
| ids.openalex | https://openalex.org/W4406793808 |
| fwci | 0.0 |
| type | preprint |
| title | On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10317 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9902999997138977 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Advanced Database Systems and Queries |
| topics[1].id | https://openalex.org/T11063 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.982200026512146 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Rough Sets and Fuzzy Logic |
| topics[2].id | https://openalex.org/T10215 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9789000153541565 |
| 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 | Semantic Web and Ontologies |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C148230440 |
| concepts[0].level | 2 |
| concepts[0].score | 0.9725033044815063 |
| 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.5701438784599304 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C2777502361 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5554630160331726 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1182254 |
| concepts[2].display_name | Deductive database |
| concepts[3].id | https://openalex.org/C199360897 |
| concepts[3].level | 1 |
| concepts[3].score | 0.4280727505683899 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[3].display_name | Programming language |
| concepts[4].id | https://openalex.org/C4777664 |
| concepts[4].level | 2 |
| concepts[4].score | 0.42040693759918213 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q1536492 |
| concepts[4].display_name | Linear temporal logic |
| concepts[5].id | https://openalex.org/C80444323 |
| concepts[5].level | 1 |
| concepts[5].score | 0.37404507398605347 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[5].display_name | Theoretical computer science |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.3512671887874603 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| keywords[0].id | https://openalex.org/keywords/datalog |
| keywords[0].score | 0.9725033044815063 |
| keywords[0].display_name | Datalog |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.5701438784599304 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/deductive-database |
| keywords[2].score | 0.5554630160331726 |
| keywords[2].display_name | Deductive database |
| keywords[3].id | https://openalex.org/keywords/programming-language |
| keywords[3].score | 0.4280727505683899 |
| keywords[3].display_name | Programming language |
| keywords[4].id | https://openalex.org/keywords/linear-temporal-logic |
| keywords[4].score | 0.42040693759918213 |
| keywords[4].display_name | Linear temporal logic |
| keywords[5].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[5].score | 0.37404507398605347 |
| keywords[5].display_name | Theoretical computer science |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.3512671887874603 |
| keywords[6].display_name | Mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2501.13762 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2501.13762 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2501.13762 |
| locations[1].id | doi:10.48550/arxiv.2501.13762 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2501.13762 |
| locations[2].id | doi:10.4230/lipics.icdt.2025.31 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S7407052059 |
| locations[2].source.type | repository |
| locations[2].source.is_oa | False |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | Dagstuhl Research Online Publication Server |
| locations[2].source.host_organization | |
| locations[2].source.host_organization_name | |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.4230/lipics.icdt.2025.31 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5035993641 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3852-9351 |
| authorships[0].author.display_name | Alessandro Artale |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Artale, Alessandro |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5082436525 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-1499-2090 |
| authorships[1].author.display_name | Anton Gnatenko |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Gnatenko, Anton |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5038062752 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-6847-6465 |
| authorships[2].author.display_name | Vladislav Ryzhikov |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Ryzhikov, Vladislav |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5001878365 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-2210-5183 |
| authorships[3].author.display_name | Michael Zakharyaschev |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Zakharyaschev, Michael |
| authorships[3].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2501.13762 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-01-25T00:00:00 |
| display_name | On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10317 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9902999997138977 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Advanced Database Systems and Queries |
| related_works | https://openalex.org/W1565767456, https://openalex.org/W4242285398, https://openalex.org/W2593015871, https://openalex.org/W2570392075, https://openalex.org/W79246384, https://openalex.org/W1552372479, https://openalex.org/W1556735226, https://openalex.org/W2023906867, https://openalex.org/W2583213513, https://openalex.org/W2124217695 |
| cited_by_count | 0 |
| locations_count | 3 |
| best_oa_location.id | pmh:oai:arXiv.org:2501.13762 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2501.13762 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2501.13762 |
| primary_location.id | pmh:oai:arXiv.org:2501.13762 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2501.13762 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2501.13762 |
| publication_date | 2025-01-01 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.L | 123 |
| abstract_inverted_index.NL | 121 |
| abstract_inverted_index.We | 28 |
| abstract_inverted_index.as | 84, 86 |
| abstract_inverted_index.be | 19, 89 |
| abstract_inverted_index.by | 21 |
| abstract_inverted_index.in | 14, 48, 51, 58, 78, 91, 98, 101, 114 |
| abstract_inverted_index.is | 2, 46, 73 |
| abstract_inverted_index.of | 6, 23, 66, 69 |
| abstract_inverted_index.or | 50, 53, 55, 100 |
| abstract_inverted_index.we | 61, 94 |
| abstract_inverted_index.(at | 42 |
| abstract_inverted_index.NL. | 59, 125 |
| abstract_inverted_index.Our | 0 |
| abstract_inverted_index.and | 57, 82, 104, 122 |
| abstract_inverted_index.any | 36 |
| abstract_inverted_index.are | 106 |
| abstract_inverted_index.can | 18, 88 |
| abstract_inverted_index.for | 32, 108 |
| abstract_inverted_index.the | 3, 15, 43, 64, 79, 115 |
| abstract_inverted_index.≠ | 120, 124 |
| abstract_inverted_index.LTL. | 27 |
| abstract_inverted_index.NC¹ | 119 |
| abstract_inverted_index.Then | 60 |
| abstract_inverted_index.data | 4, 33 |
| abstract_inverted_index.done | 90 |
| abstract_inverted_index.rule | 16 |
| abstract_inverted_index.show | 62 |
| abstract_inverted_index.such | 71 |
| abstract_inverted_index.that | 63, 96, 118 |
| abstract_inverted_index.well | 85 |
| abstract_inverted_index.with | 39, 110 |
| abstract_inverted_index.AC⁰ | 81, 99 |
| abstract_inverted_index.atoms | 13 |
| abstract_inverted_index.first | 29 |
| abstract_inverted_index.logic | 26 |
| abstract_inverted_index.prove | 95 |
| abstract_inverted_index.query | 38 |
| abstract_inverted_index.that, | 31 |
| abstract_inverted_index.while | 75 |
| abstract_inverted_index.whose | 12 |
| abstract_inverted_index.ACC⁰ | 83 |
| abstract_inverted_index.AC⁰, | 49 |
| abstract_inverted_index.L-hard | 56 |
| abstract_inverted_index.bodies | 17 |
| abstract_inverted_index.either | 47 |
| abstract_inverted_index.linear | 8, 24 |
| abstract_inverted_index.ACC⁰, | 102 |
| abstract_inverted_index.classes | 80 |
| abstract_inverted_index.concern | 1 |
| abstract_inverted_index.datalog | 10 |
| abstract_inverted_index.moment) | 45 |
| abstract_inverted_index.monadic | 9 |
| abstract_inverted_index.observe | 30 |
| abstract_inverted_index.problem | 65 |
| abstract_inverted_index.queries | 11, 72, 109 |
| abstract_inverted_index.Finally, | 93 |
| abstract_inverted_index.checking | 76 |
| abstract_inverted_index.deciding | 67 |
| abstract_inverted_index.prefixed | 20 |
| abstract_inverted_index.provided | 117 |
| abstract_inverted_index.temporal | 25 |
| abstract_inverted_index.◇/◇- | 112 |
| abstract_inverted_index.○/○- | 41 |
| abstract_inverted_index.(sometime | 113 |
| abstract_inverted_index.ExpSpace. | 92 |
| abstract_inverted_index.answering | 7, 35, 70 |
| abstract_inverted_index.connected | 37 |
| abstract_inverted_index.operators | 22, 40, 111 |
| abstract_inverted_index.L-hardness | 68, 105 |
| abstract_inverted_index.complexity | 5 |
| abstract_inverted_index.membership | 77, 97 |
| abstract_inverted_index.complexity, | 34 |
| abstract_inverted_index.undecidable | 107 |
| abstract_inverted_index.future/past) | 116 |
| abstract_inverted_index.ACC⁰\AC⁰, | 52 |
| abstract_inverted_index.next/previous | 44 |
| abstract_inverted_index.NC¹-complete, | 54 |
| abstract_inverted_index.PSpace-complete, | 74 |
| abstract_inverted_index.NC¹-completeness | 87 |
| abstract_inverted_index.NC¹-completeness, | 103 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile.value | 0.02080192 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |