$n$-permutability and linear Datalog implies symmetric Datalog
We show that if $\mathbb A$ is a core relational structure such that CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is $n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric Datalog program (and thus CSP($\mathbb A$) lies in deterministic logspac...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2018-04-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2029/pdf |
| _version_ | 1797268616645705728 |
|---|---|
| author | Alexandr Kazda |
| author_facet | Alexandr Kazda |
| author_sort | Alexandr Kazda |
| collection | DOAJ |
| description | We show that if $\mathbb A$ is a core relational structure such that
CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is
$n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric
Datalog program (and thus CSP($\mathbb A$) lies in deterministic logspace). At
the moment, it is not known for which structures $\mathbb A$ will CSP($\mathbb
A$) be solvable by a linear Datalog program. However, once somebody obtains a
characterization of linear Datalog, our result immediately gives a
characterization of symmetric Datalog. |
| first_indexed | 2024-04-25T01:35:19Z |
| format | Article |
| id | doaj.art-38fd184f4ddf43daaf27e8378bae7a3b |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:19Z |
| publishDate | 2018-04-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-38fd184f4ddf43daaf27e8378bae7a3b2024-03-08T09:59:19ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742018-04-01Volume 14, Issue 210.23638/LMCS-14(2:3)20182029$n$-permutability and linear Datalog implies symmetric DatalogAlexandr KazdaWe show that if $\mathbb A$ is a core relational structure such that CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is $n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric Datalog program (and thus CSP($\mathbb A$) lies in deterministic logspace). At the moment, it is not known for which structures $\mathbb A$ will CSP($\mathbb A$) be solvable by a linear Datalog program. However, once somebody obtains a characterization of linear Datalog, our result immediately gives a characterization of symmetric Datalog.https://lmcs.episciences.org/2029/pdfcomputer science - computational complexity68q17, 68r05, 03c05 |
| spellingShingle | Alexandr Kazda $n$-permutability and linear Datalog implies symmetric Datalog Logical Methods in Computer Science computer science - computational complexity 68q17, 68r05, 03c05 |
| title | $n$-permutability and linear Datalog implies symmetric Datalog |
| title_full | $n$-permutability and linear Datalog implies symmetric Datalog |
| title_fullStr | $n$-permutability and linear Datalog implies symmetric Datalog |
| title_full_unstemmed | $n$-permutability and linear Datalog implies symmetric Datalog |
| title_short | $n$-permutability and linear Datalog implies symmetric Datalog |
| title_sort | n permutability and linear datalog implies symmetric datalog |
| topic | computer science - computational complexity 68q17, 68r05, 03c05 |
| url | https://lmcs.episciences.org/2029/pdf |
| work_keys_str_mv | AT alexandrkazda npermutabilityandlineardatalogimpliessymmetricdatalog |