Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic Article Swipe
Agi Kurucz
,
Vladislav Ryzhikov
,
Yury Savateev
,
Michael Zakharyaschev
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1613/jair.1.14061
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1613/jair.1.14061
Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) formulated in linear temporal logic LTL over (Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with some extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC0, ACC0 and NC1 coincides with FO(<,≡)-rewritability using unary predicates x ≡ 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We prove that, similarly to known PSᴘᴀᴄᴇ-completeness of recognising FO(<)-definability of regular languages, deciding FO(<,≡)- and FO(<,MOD)-definability is also PSᴘᴀᴄᴇ-complete (unless ACC0 = NC1). We then use this result to show that deciding FO(<)-, FO(<,≡)- and FO(<,MOD)-rewritability of LTL OMQs is ExᴘSᴘᴀᴄᴇ-complete, and that these problems become PSᴘᴀᴄᴇ-complete for OMQs with a linear Horn ontology and an atomic query, and also a positive query in the cases of FO(<)- and FO(<,≡)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSᴘᴀᴄᴇ-, Π2p- and coNP-complete.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1613/jair.1.14061
- https://www.jair.org/index.php/jair/article/download/14061/26901
- OA Status
- diamond
- Cited By
- 3
- References
- 113
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4324130885
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4324130885Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1613/jair.1.14061Digital Object Identifier
- Title
-
Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal LogicWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-03-13Full publication date if available
- Authors
-
Agi Kurucz, Vladislav Ryzhikov, Yury Savateev, Michael ZakharyaschevList of authors in order
- Landing page
-
https://doi.org/10.1613/jair.1.14061Publisher landing page
- PDF URL
-
https://www.jair.org/index.php/jair/article/download/14061/26901Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
diamondOpen access status per OpenAlex
- OA URL
-
https://www.jair.org/index.php/jair/article/download/14061/26901Direct OA link when available
- Concepts
-
Unary operation, PSPACE, Conjunctive query, P, Mathematics, Time complexity, EXPTIME, Decidability, Discrete mathematics, Theoretical computer science, Temporal logic, Datalog, Linear temporal logic, Computer science, Computational complexity theory, Relational database, Algorithm, DatabaseTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
3Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 2, 2023: 1Per-year citation counts (last 5 years)
- References (count)
-
113Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4324130885 |
|---|---|
| doi | https://doi.org/10.1613/jair.1.14061 |
| ids.doi | https://doi.org/10.1613/jair.1.14061 |
| ids.openalex | https://openalex.org/W4324130885 |
| fwci | 0.76632866 |
| type | article |
| title | Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic |
| biblio.issue | |
| biblio.volume | 76 |
| biblio.last_page | 703 |
| biblio.first_page | 645 |
| 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.9958999752998352 |
| 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/T11010 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9947999715805054 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Logic, Reasoning, and Knowledge |
| topics[2].id | https://openalex.org/T10317 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9937999844551086 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Advanced Database Systems and Queries |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C78023250 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7456449866294861 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q657596 |
| concepts[0].display_name | Unary operation |
| concepts[1].id | https://openalex.org/C197685441 |
| concepts[1].level | 3 |
| concepts[1].score | 0.7003897428512573 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q500716 |
| concepts[1].display_name | PSPACE |
| concepts[2].id | https://openalex.org/C65647387 |
| concepts[2].level | 3 |
| concepts[2].score | 0.5393365025520325 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1781706 |
| concepts[2].display_name | Conjunctive query |
| concepts[3].id | https://openalex.org/C134026603 |
| concepts[3].level | 3 |
| concepts[3].score | 0.5375432968139648 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q846354 |
| concepts[3].display_name | P |
| concepts[4].id | https://openalex.org/C33923547 |
| concepts[4].level | 0 |
| concepts[4].score | 0.509874701499939 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[4].display_name | Mathematics |
| concepts[5].id | https://openalex.org/C311688 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5005230903625488 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[5].display_name | Time complexity |
| concepts[6].id | https://openalex.org/C56049555 |
| concepts[6].level | 4 |
| concepts[6].score | 0.49828362464904785 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1276570 |
| concepts[6].display_name | EXPTIME |
| concepts[7].id | https://openalex.org/C153269930 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4941239655017853 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q430001 |
| concepts[7].display_name | Decidability |
| concepts[8].id | https://openalex.org/C118615104 |
| concepts[8].level | 1 |
| concepts[8].score | 0.4795522391796112 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[8].display_name | Discrete mathematics |
| concepts[9].id | https://openalex.org/C80444323 |
| concepts[9].level | 1 |
| concepts[9].score | 0.42090755701065063 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[9].display_name | Theoretical computer science |
| concepts[10].id | https://openalex.org/C25016198 |
| concepts[10].level | 2 |
| concepts[10].score | 0.4195968508720398 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q781833 |
| concepts[10].display_name | Temporal logic |
| concepts[11].id | https://openalex.org/C148230440 |
| concepts[11].level | 2 |
| concepts[11].score | 0.41325652599334717 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q1172264 |
| concepts[11].display_name | Datalog |
| concepts[12].id | https://openalex.org/C4777664 |
| concepts[12].level | 2 |
| concepts[12].score | 0.4110995829105377 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q1536492 |
| concepts[12].display_name | Linear temporal logic |
| concepts[13].id | https://openalex.org/C41008148 |
| concepts[13].level | 0 |
| concepts[13].score | 0.37953513860702515 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[13].display_name | Computer science |
| concepts[14].id | https://openalex.org/C179799912 |
| concepts[14].level | 2 |
| concepts[14].score | 0.3181728720664978 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q205084 |
| concepts[14].display_name | Computational complexity theory |
| concepts[15].id | https://openalex.org/C5655090 |
| concepts[15].level | 2 |
| concepts[15].score | 0.2790749669075012 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q192588 |
| concepts[15].display_name | Relational database |
| concepts[16].id | https://openalex.org/C11413529 |
| concepts[16].level | 1 |
| concepts[16].score | 0.2251068651676178 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[16].display_name | Algorithm |
| concepts[17].id | https://openalex.org/C77088390 |
| concepts[17].level | 1 |
| concepts[17].score | 0.11536037921905518 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q8513 |
| concepts[17].display_name | Database |
| keywords[0].id | https://openalex.org/keywords/unary-operation |
| keywords[0].score | 0.7456449866294861 |
| keywords[0].display_name | Unary operation |
| keywords[1].id | https://openalex.org/keywords/pspace |
| keywords[1].score | 0.7003897428512573 |
| keywords[1].display_name | PSPACE |
| keywords[2].id | https://openalex.org/keywords/conjunctive-query |
| keywords[2].score | 0.5393365025520325 |
| keywords[2].display_name | Conjunctive query |
| keywords[3].id | https://openalex.org/keywords/p |
| keywords[3].score | 0.5375432968139648 |
| keywords[3].display_name | P |
| keywords[4].id | https://openalex.org/keywords/mathematics |
| keywords[4].score | 0.509874701499939 |
| keywords[4].display_name | Mathematics |
| keywords[5].id | https://openalex.org/keywords/time-complexity |
| keywords[5].score | 0.5005230903625488 |
| keywords[5].display_name | Time complexity |
| keywords[6].id | https://openalex.org/keywords/exptime |
| keywords[6].score | 0.49828362464904785 |
| keywords[6].display_name | EXPTIME |
| keywords[7].id | https://openalex.org/keywords/decidability |
| keywords[7].score | 0.4941239655017853 |
| keywords[7].display_name | Decidability |
| keywords[8].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[8].score | 0.4795522391796112 |
| keywords[8].display_name | Discrete mathematics |
| keywords[9].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[9].score | 0.42090755701065063 |
| keywords[9].display_name | Theoretical computer science |
| keywords[10].id | https://openalex.org/keywords/temporal-logic |
| keywords[10].score | 0.4195968508720398 |
| keywords[10].display_name | Temporal logic |
| keywords[11].id | https://openalex.org/keywords/datalog |
| keywords[11].score | 0.41325652599334717 |
| keywords[11].display_name | Datalog |
| keywords[12].id | https://openalex.org/keywords/linear-temporal-logic |
| keywords[12].score | 0.4110995829105377 |
| keywords[12].display_name | Linear temporal logic |
| keywords[13].id | https://openalex.org/keywords/computer-science |
| keywords[13].score | 0.37953513860702515 |
| keywords[13].display_name | Computer science |
| keywords[14].id | https://openalex.org/keywords/computational-complexity-theory |
| keywords[14].score | 0.3181728720664978 |
| keywords[14].display_name | Computational complexity theory |
| keywords[15].id | https://openalex.org/keywords/relational-database |
| keywords[15].score | 0.2790749669075012 |
| keywords[15].display_name | Relational database |
| keywords[16].id | https://openalex.org/keywords/algorithm |
| keywords[16].score | 0.2251068651676178 |
| keywords[16].display_name | Algorithm |
| keywords[17].id | https://openalex.org/keywords/database |
| keywords[17].score | 0.11536037921905518 |
| keywords[17].display_name | Database |
| language | en |
| locations[0].id | doi:10.1613/jair.1.14061 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S139930977 |
| locations[0].source.issn | 1076-9757, 1943-5037 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 1076-9757 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | True |
| locations[0].source.display_name | Journal of Artificial Intelligence Research |
| locations[0].source.host_organization | https://openalex.org/P4310315760 |
| locations[0].source.host_organization_name | AI Access Foundation |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310315760 |
| locations[0].source.host_organization_lineage_names | AI Access Foundation |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://www.jair.org/index.php/jair/article/download/14061/26901 |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Journal of Artificial Intelligence Research |
| locations[0].landing_page_url | https://doi.org/10.1613/jair.1.14061 |
| indexed_in | crossref, doaj |
| authorships[0].author.id | https://openalex.org/A5038619560 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-6233-6277 |
| authorships[0].author.display_name | Agi Kurucz |
| authorships[0].countries | GB |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I183935753 |
| authorships[0].affiliations[0].raw_affiliation_string | Department of Informatics, King's College London |
| authorships[0].institutions[0].id | https://openalex.org/I183935753 |
| authorships[0].institutions[0].ror | https://ror.org/0220mzb33 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I124357947, https://openalex.org/I183935753 |
| authorships[0].institutions[0].country_code | GB |
| authorships[0].institutions[0].display_name | King's College London |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Agi Kurucz |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Department of Informatics, King's College London |
| authorships[1].author.id | https://openalex.org/A5038062752 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-6847-6465 |
| authorships[1].author.display_name | Vladislav Ryzhikov |
| authorships[1].countries | GB |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I98259816 |
| authorships[1].affiliations[0].raw_affiliation_string | Department of Computer Science, Birkbeck, University of London |
| authorships[1].institutions[0].id | https://openalex.org/I98259816 |
| authorships[1].institutions[0].ror | https://ror.org/02mb95055 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I124357947, https://openalex.org/I98259816 |
| authorships[1].institutions[0].country_code | GB |
| authorships[1].institutions[0].display_name | Birkbeck, University of London |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Vladislav Ryzhikov |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Department of Computer Science, Birkbeck, University of London |
| authorships[2].author.id | https://openalex.org/A5010357513 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-5112-4992 |
| authorships[2].author.display_name | Yury Savateev |
| authorships[2].countries | GB |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I98259816 |
| authorships[2].affiliations[0].raw_affiliation_string | Department of Computer Science, Birkbeck, University of London |
| 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 | middle |
| authorships[2].raw_author_name | Yury Savateev |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Department of Computer Science, Birkbeck, University of London |
| 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].countries | GB |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I98259816 |
| authorships[3].affiliations[0].raw_affiliation_string | Department of Computer Science, Birkbeck, University of London |
| authorships[3].institutions[0].id | https://openalex.org/I98259816 |
| authorships[3].institutions[0].ror | https://ror.org/02mb95055 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I124357947, https://openalex.org/I98259816 |
| authorships[3].institutions[0].country_code | GB |
| authorships[3].institutions[0].display_name | Birkbeck, University of London |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Michael Zakharyaschev |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Department of Computer Science, Birkbeck, University of London |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://www.jair.org/index.php/jair/article/download/14061/26901 |
| open_access.oa_status | diamond |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic |
| has_fulltext | True |
| 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.9958999752998352 |
| 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/W2026191634, https://openalex.org/W2029582218, https://openalex.org/W1893650332, https://openalex.org/W2963589932, https://openalex.org/W2963364464, https://openalex.org/W2740681086, https://openalex.org/W2551830925, https://openalex.org/W4288363924, https://openalex.org/W4389096604, https://openalex.org/W2966447359 |
| cited_by_count | 3 |
| counts_by_year[0].year | 2024 |
| counts_by_year[0].cited_by_count | 2 |
| counts_by_year[1].year | 2023 |
| counts_by_year[1].cited_by_count | 1 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1613/jair.1.14061 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S139930977 |
| best_oa_location.source.issn | 1076-9757, 1943-5037 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 1076-9757 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | True |
| best_oa_location.source.display_name | Journal of Artificial Intelligence Research |
| best_oa_location.source.host_organization | https://openalex.org/P4310315760 |
| best_oa_location.source.host_organization_name | AI Access Foundation |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310315760 |
| best_oa_location.source.host_organization_lineage_names | AI Access Foundation |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://www.jair.org/index.php/jair/article/download/14061/26901 |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Journal of Artificial Intelligence Research |
| best_oa_location.landing_page_url | https://doi.org/10.1613/jair.1.14061 |
| primary_location.id | doi:10.1613/jair.1.14061 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S139930977 |
| primary_location.source.issn | 1076-9757, 1943-5037 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 1076-9757 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | True |
| primary_location.source.display_name | Journal of Artificial Intelligence Research |
| primary_location.source.host_organization | https://openalex.org/P4310315760 |
| primary_location.source.host_organization_name | AI Access Foundation |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310315760 |
| primary_location.source.host_organization_lineage_names | AI Access Foundation |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://www.jair.org/index.php/jair/article/download/14061/26901 |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Journal of Artificial Intelligence Research |
| primary_location.landing_page_url | https://doi.org/10.1613/jair.1.14061 |
| publication_date | 2023-03-13 |
| publication_year | 2023 |
| referenced_works | https://openalex.org/W6633513001, https://openalex.org/W6661523041, https://openalex.org/W6680484969, https://openalex.org/W6631329903, https://openalex.org/W6634862398, https://openalex.org/W6785683103, https://openalex.org/W2235742114, https://openalex.org/W3016366169, https://openalex.org/W3214083543, https://openalex.org/W2040566369, https://openalex.org/W4240781210, https://openalex.org/W6643119825, https://openalex.org/W6664053925, https://openalex.org/W2111132083, https://openalex.org/W6633647713, https://openalex.org/W2787345006, https://openalex.org/W161453261, https://openalex.org/W2949102816, https://openalex.org/W2588857520, https://openalex.org/W2346723917, https://openalex.org/W2972451557, https://openalex.org/W2579756286, https://openalex.org/W2982509390, https://openalex.org/W6735207027, https://openalex.org/W2001399171, https://openalex.org/W2137862151, https://openalex.org/W2274615375, https://openalex.org/W6657385584, https://openalex.org/W199851562, https://openalex.org/W6679510460, https://openalex.org/W146462443, https://openalex.org/W6803521803, https://openalex.org/W2578059697, https://openalex.org/W6679480774, https://openalex.org/W6745794593, https://openalex.org/W6654255166, https://openalex.org/W3033823979, https://openalex.org/W2009098458, https://openalex.org/W2309621853, https://openalex.org/W6799603462, https://openalex.org/W1506076469, https://openalex.org/W2026629052, https://openalex.org/W6660559572, https://openalex.org/W6629417139, https://openalex.org/W6681325349, https://openalex.org/W2740681086, https://openalex.org/W4288363924, https://openalex.org/W2136421307, https://openalex.org/W2001372818, https://openalex.org/W6617347132, https://openalex.org/W6629650154, https://openalex.org/W6629040674, https://openalex.org/W6645211092, https://openalex.org/W1549064707, https://openalex.org/W6632581794, https://openalex.org/W2965511917, https://openalex.org/W2116250539, https://openalex.org/W1978405212, https://openalex.org/W6647820883, https://openalex.org/W1998084650, https://openalex.org/W200063938, https://openalex.org/W3089573429, https://openalex.org/W3174085730, https://openalex.org/W2125615295, https://openalex.org/W6649489421, https://openalex.org/W2047754004, https://openalex.org/W2019120929, https://openalex.org/W104477597, https://openalex.org/W42364276, https://openalex.org/W7036995562, https://openalex.org/W3034722188, https://openalex.org/W4225991507, https://openalex.org/W6753115406, https://openalex.org/W2945688618, https://openalex.org/W6784761822, https://openalex.org/W4390424460, https://openalex.org/W2600455691, https://openalex.org/W2039529128, https://openalex.org/W1581108661, https://openalex.org/W3101483322, https://openalex.org/W1498203978, https://openalex.org/W1485990531, https://openalex.org/W2027683388, https://openalex.org/W4206031975, https://openalex.org/W3097222332, https://openalex.org/W2098171268, https://openalex.org/W1482134990, https://openalex.org/W2044831893, https://openalex.org/W2838709227, https://openalex.org/W4324130885, https://openalex.org/W4293765636, https://openalex.org/W2139891885, https://openalex.org/W1566071135, https://openalex.org/W3188628610, https://openalex.org/W4285793031, https://openalex.org/W112858668, https://openalex.org/W4230191592, https://openalex.org/W3210476636, https://openalex.org/W2131225255, https://openalex.org/W2615399484, https://openalex.org/W2963967056, https://openalex.org/W2142614470, https://openalex.org/W2044922487, https://openalex.org/W2963987338, https://openalex.org/W2060270693, https://openalex.org/W2953020458, https://openalex.org/W1527197079, https://openalex.org/W3081110571, https://openalex.org/W2055403716, https://openalex.org/W2752061190, https://openalex.org/W3081083544, https://openalex.org/W1489366126, https://openalex.org/W1991366422 |
| referenced_works_count | 113 |
| abstract_inverted_index.0 | 68 |
| abstract_inverted_index.= | 101 |
| abstract_inverted_index.a | 130, 140, 157 |
| abstract_inverted_index.x | 66 |
| abstract_inverted_index.We | 79, 103 |
| abstract_inverted_index.an | 12, 31, 135 |
| abstract_inverted_index.in | 17, 42, 55, 143 |
| abstract_inverted_index.is | 2, 28, 96, 119, 168 |
| abstract_inverted_index.it | 27, 167 |
| abstract_inverted_index.of | 5, 10, 50, 86, 89, 116, 146, 154 |
| abstract_inverted_index.to | 30, 83, 108 |
| abstract_inverted_index.we | 39, 151 |
| abstract_inverted_index.LTL | 21, 117 |
| abstract_inverted_index.NC1 | 59 |
| abstract_inverted_index.OMQ | 53, 162 |
| abstract_inverted_index.Our | 0 |
| abstract_inverted_index.and | 24, 48, 58, 72, 94, 114, 121, 134, 138, 148, 160, 171 |
| abstract_inverted_index.for | 127, 164 |
| abstract_inverted_index.n), | 70 |
| abstract_inverted_index.the | 3, 7, 45, 144 |
| abstract_inverted_index.use | 105 |
| abstract_inverted_index.≡ | 67 |
| abstract_inverted_index.(mod | 69 |
| abstract_inverted_index.AC0, | 56 |
| abstract_inverted_index.ACC0 | 57, 100 |
| abstract_inverted_index.Horn | 132 |
| abstract_inverted_index.OMQs | 118, 128, 155 |
| abstract_inverted_index.also | 97, 139 |
| abstract_inverted_index.data | 8 |
| abstract_inverted_index.line | 43 |
| abstract_inverted_index.over | 22 |
| abstract_inverted_index.show | 109 |
| abstract_inverted_index.some | 35 |
| abstract_inverted_index.that | 110, 122 |
| abstract_inverted_index.then | 104 |
| abstract_inverted_index.this | 106 |
| abstract_inverted_index.with | 34, 44, 61, 129, 156 |
| abstract_inverted_index.(OMQ) | 15 |
| abstract_inverted_index.NC1). | 102 |
| abstract_inverted_index.cases | 145 |
| abstract_inverted_index.extra | 36 |
| abstract_inverted_index.known | 84 |
| abstract_inverted_index.logic | 20 |
| abstract_inverted_index.prove | 80 |
| abstract_inverted_index.query | 14, 142 |
| abstract_inverted_index.that, | 41, 81 |
| abstract_inverted_index.these | 123 |
| abstract_inverted_index.unary | 64 |
| abstract_inverted_index.using | 63, 74 |
| abstract_inverted_index.which | 165 |
| abstract_inverted_index.Π2p- | 170 |
| abstract_inverted_index.First, | 38 |
| abstract_inverted_index.atomic | 136 |
| abstract_inverted_index.become | 125 |
| abstract_inverted_index.linear | 18, 131 |
| abstract_inverted_index.query, | 137 |
| abstract_inverted_index.result | 107 |
| abstract_inverted_index.(unless | 99 |
| abstract_inverted_index.circuit | 46 |
| abstract_inverted_index.concern | 1 |
| abstract_inverted_index.observe | 40 |
| abstract_inverted_index.problem | 4 |
| abstract_inverted_index.regular | 51, 90 |
| abstract_inverted_index.whether | 26 |
| abstract_inverted_index.(Z,<) | 23 |
| abstract_inverted_index.Further, | 150 |
| abstract_inverted_index.classes, | 163 |
| abstract_inverted_index.consider | 152 |
| abstract_inverted_index.deciding | 25, 92, 111, 166 |
| abstract_inverted_index.identify | 161 |
| abstract_inverted_index.ontology | 133, 159 |
| abstract_inverted_index.positive | 141 |
| abstract_inverted_index.possibly | 33 |
| abstract_inverted_index.problems | 124 |
| abstract_inverted_index.temporal | 19 |
| abstract_inverted_index.FO(<)- | 147 |
| abstract_inverted_index.answering | 11, 54 |
| abstract_inverted_index.coincides | 60 |
| abstract_inverted_index.primitive | 76 |
| abstract_inverted_index.similarly | 82 |
| abstract_inverted_index.FO(<)-, | 112 |
| abstract_inverted_index.complexity | 9, 47 |
| abstract_inverted_index.formulated | 16 |
| abstract_inverted_index.languages, | 52, 91 |
| abstract_inverted_index.predicates | 65 |
| abstract_inverted_index.recursion, | 77 |
| abstract_inverted_index.relational | 75 |
| abstract_inverted_index.rewritable | 29 |
| abstract_inverted_index.determining | 6 |
| abstract_inverted_index.predicates. | 37 |
| abstract_inverted_index.recognising | 87 |
| abstract_inverted_index.FO(<,≡)- | 93, 113 |
| abstract_inverted_index.binary-clause | 158 |
| abstract_inverted_index.respectively. | 78 |
| abstract_inverted_index.coNP-complete. | 172 |
| abstract_inverted_index.FO(<)-query, | 32 |
| abstract_inverted_index.FO-definability | 49 |
| abstract_inverted_index.PSᴘᴀᴄᴇ-, | 169 |
| abstract_inverted_index.ontology-mediated | 13 |
| abstract_inverted_index.FO(<)-definability | 88 |
| abstract_inverted_index.FO(RPR)-rewritability | 73 |
| abstract_inverted_index.FO(<)-rewritability | 153 |
| abstract_inverted_index.PSᴘᴀᴄᴇ-complete | 98, 126 |
| abstract_inverted_index.FO(<,MOD)-definability | 95 |
| abstract_inverted_index.FO(<,MOD)-rewritability | 115 |
| abstract_inverted_index.FO(<,≡)-rewritability | 62 |
| abstract_inverted_index.FO(<,MOD)-rewritability, | 71 |
| abstract_inverted_index.FO(<,≡)-rewritability. | 149 |
| abstract_inverted_index.PSᴘᴀᴄᴇ-completeness | 85 |
| abstract_inverted_index.ExᴘSᴘᴀᴄᴇ-complete, | 120 |
| cited_by_percentile_year.max | 96 |
| cited_by_percentile_year.min | 89 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 4 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/4 |
| sustainable_development_goals[0].score | 0.4099999964237213 |
| sustainable_development_goals[0].display_name | Quality Education |
| citation_normalized_percentile.value | 0.7181855 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |