5 citations · 5 across the 3 of their papers we have counts for
3 papers
cs.LO2022
Reducing NEXP-complete problems to DQBF
Fa-Hsun Chen, Shen-Chang Huang, Yu-Cheng Lu +1
We present an alternative proof of the NEXP-hardness of the satisfiability of {\em Dependency Quantified Boolean Formulas} (DQBF). Besides being simple, our proof also gives us a g…
cs.LO2014★ 5 cited
Undecidability of satisfiability in the algebra of finite binary relations with union, composition, and difference
Tony Tan, Jan Van den Bussche, Xiaowang Zhang
We consider expressions built up from binary relation names using the operators union, composition, and set difference. We show that it is undecidable to test whether a given such…
cs.LO2014
On the variable hierarchy of first-order spectra
Eryk Kopczynski, Tony Tan
The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra…