Details
| Original language | English |
|---|---|
| Title of host publication | Foundations of Information and Knowledge Systems |
| Subtitle of host publication | 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings |
| Editors | Stefan Woltran, Flavio Ferrarotti |
| Publisher | Springer Verlag |
| Pages | 303-321 |
| Number of pages | 19 |
| Edition | 1. |
| ISBN (electronic) | 978-3-319-90050-6 |
| ISBN (print) | 978-3-319-90049-0 |
| Publication status | Published - 2018 |
| Event | 10th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2018 - Budapest, Hungary Duration: 14 May 2018 → 18 May 2018 |
Publication series
| Name | Lecture Notes in Computer Science (LNCS) |
|---|---|
| Volume | 10833 |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
| Name | Information Systems and Applications, incl. Internet/Web, and HCI (LNISA) |
|---|---|
| ISSN (Print) | 2946-1642 |
| ISSN (electronic) | 2946-1634 |
Abstract
Keywords
- cs.LO, cs.CC
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Foundations of Information and Knowledge Systems: 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings. ed. / Stefan Woltran; Flavio Ferrarotti. 1. ed. Springer Verlag, 2018. p. 303-321 (Lecture Notes in Computer Science (LNCS); Vol. 10833), (Information Systems and Applications, incl. Internet/Web, and HCI (LNISA)).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Enumeration complexity of poor man’s propositional dependence logic
AU - Meier, Arne
AU - Reinbold, Christian
PY - 2018
Y1 - 2018
N2 - Dependence logics are a modern family of logics of independence and dependence which mimic notions of database theory. In this paper, we aim to initiate the study of enumeration complexity in the field of dependence logics and thereby get a new point of view on enumerating answers of database queries. Consequently, as a first step, we investigate the problem of enumerating all satisfying teams of formulas from a given fragment of propositional dependence logic. We distinguish between restricting the team size by arbitrary functions and the parametrised version where the parameter is the team size. We show that a polynomial delay can be reached for polynomials and otherwise in the parametrised setting we reach FPT delay. However, the constructed enumeration algorithm with polynomial delay requires exponential space. We show that an incremental polynomial delay algorithm exists which uses polynomial space only. Negatively, we show that for the general problem without restricting the team size, an enumeration algorithm running in polynomial space cannot exist.
AB - Dependence logics are a modern family of logics of independence and dependence which mimic notions of database theory. In this paper, we aim to initiate the study of enumeration complexity in the field of dependence logics and thereby get a new point of view on enumerating answers of database queries. Consequently, as a first step, we investigate the problem of enumerating all satisfying teams of formulas from a given fragment of propositional dependence logic. We distinguish between restricting the team size by arbitrary functions and the parametrised version where the parameter is the team size. We show that a polynomial delay can be reached for polynomials and otherwise in the parametrised setting we reach FPT delay. However, the constructed enumeration algorithm with polynomial delay requires exponential space. We show that an incremental polynomial delay algorithm exists which uses polynomial space only. Negatively, we show that for the general problem without restricting the team size, an enumeration algorithm running in polynomial space cannot exist.
KW - cs.LO
KW - cs.CC
UR - http://www.scopus.com/inward/record.url?scp=85046898533&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1704.03292
DO - 10.48550/arXiv.1704.03292
M3 - Conference contribution
AN - SCOPUS:85046898533
SN - 978-3-319-90049-0
T3 - Lecture Notes in Computer Science (LNCS)
SP - 303
EP - 321
BT - Foundations of Information and Knowledge Systems
A2 - Woltran, Stefan
A2 - Ferrarotti, Flavio
PB - Springer Verlag
T2 - 10th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2018
Y2 - 14 May 2018 through 18 May 2018
ER -