Lidia Tendera
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Lidia Tendera has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Ian Pratt-Hartmann
University of Manchester
3 shared publications - Wiesław Szwast
INSTYTUT INFORMATYKI UNIWERSYTET OPOLSKI 45-040 OPOLE, POLAND
3 shared publications - Emanuel Kieroński
University of Wroclaw
1 shared publication
Latest Publications
- 6 June 2019
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 84 (3) , 1020-1048
THE FLUTED FRAGMENT REVISITED
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$ , the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$ . We show that, for $m \ge 2$ , this subfragment forces $\left\lfloor {m/2} \right\rfloor$ -tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$ -NExpTime-hard. We further establish that, for $m \ge 3$ , any satisfiable ${\cal F}{{\cal L}^m}$ -formula has a model of at most ( $m - 2$ )-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ( $m - 2$ )-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for ${\cal F}{{\cal L}^m}$ for all $m \le 4$ .- 6 June 2019
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 84 (3) , 1020-1048
THE FLUTED FRAGMENT REVISITED
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$ , the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$ . We show that, for $m \ge 2$ , this subfragment forces $\left\lfloor {m/2} \right\rfloor$ -tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$ -NExpTime-hard. We further establish that, for $m \ge 3$ , any satisfiable ${\cal F}{{\cal L}^m}$ -formula has a model of at most ( $m - 2$ )-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ( $m - 2$ )-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for ${\cal F}{{\cal L}^m}$ for all $m \le 4$ .- Open Access
Quine's Fluted Fragment Revisited
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originally identified in 1968 by W.V. Quine. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NExpTime. More precisely, we consider $\mathcal{FL}^m$, the intersection of the fluted fragment and the $m$-variable fragment of first-order logic, for all $m \geq 1$. We show that, for $m \geq 2$, this sub-fragment forces $\lfloor m/2\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\lfloor m/2\rfloor$-NExpTime-hard. We further establish that, for $m \geq 3$, any satisfiable $\mathcal{FL}^m$-formula has a model of at most ($m-2$)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ($m-2$)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for $\mathcal{FL}^m$ for all $m \leq 4$.Open AccessQuine's Fluted Fragment Revisited
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originally identified in 1968 by W.V. Quine. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NExpTime. More precisely, we consider $\mathcal{FL}^m$, the intersection of the fluted fragment and the $m$-variable fragment of first-order logic, for all $m \geq 1$. We show that, for $m \geq 2$, this sub-fragment forces $\lfloor m/2\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\lfloor m/2\rfloor$-NExpTime-hard. We further establish that, for $m \geq 3$, any satisfiable $\mathcal{FL}^m$-formula has a model of at most ($m-2$)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ($m-2$)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for $\mathcal{FL}^m$ for all $m \leq 4$. - Open Access
- 4 December 2015
- Published by Oxford University Press (OUP) in Journal of Logic and Computation
- p. exv075
Equivalence closure in the two-variable guarded fragment
We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.
- 4 December 2015
- Published by Oxford University Press (OUP) in Journal of Logic and Computation
- p. exv075
Open AccessEquivalence closure in the two-variable guarded fragment
We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.
- 1 August 2004
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 128 (1-3) , 227-276
The guarded fragment with transitive guards*1
- 1 August 2004
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 128 (1-3) , 227-276
The guarded fragment with transitive guards*1