10 citations · 23 across the 13 of their papers we have counts for
16 papers
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…
On two-variable guarded fragment logic with expressive local Presburger constraints
Chia-Hsuan Lu, Tony Tan
We consider the extension of the two-variable guarded fragment logic with local Presburger quantifiers. These are quantifiers that can express properties such as "the number of inc…
On Classical Decidable Logics extended with Percentage Quantifiers and Arithmetics
Bartosz Bednarczyk, Maja Orłowska, Anna Pacanowska +1
During the last decades, a lot of effort was put into identifying decidable fragments of first-order logic. Such efforts gave birth, among the others, to the two-variable fragment…
Towards a more efficient approach for the satisfiability of two-variable logic
Ting-Wei Lin, Chia-Hsuan Lu, Tony Tan
We revisit the satisfiability problem for two-variable logic, denoted by SAT(FO2), which is known to be NEXP-complete. The upper bound is usually derived from its well known Expone…
Two variable logic with ultimately periodic counting
Michael Benedikt, Egor V. Kostylev, Tony Tan
We consider the extension of two variable logic with quantifiers that state that the number of elements where a formula holds should belong to a given ultimately periodic set. We s…
A simple combinatorial proof for small model property of two-variable logic
Yanger Ma, Tony Tan
We present another proof for the well-known {\em small model property} of two-variable logic. As far as we know, existing proofs of this property rely heavily on model theoretic co…
A note on first-order spectra with binary relations
Eryk Kopczynski, Tony Tan
The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at l…
Register automata with linear arithmetic
Yu-Fang Chen, Ondrej Lengal, Tony Tan +1
We propose a novel automata model over the alphabet of rational numbers, which we call register automata over the rationals (RA-Q). It reads a sequence of rational numbers and outp…
Parallel Evaluation of Multi-Semi-Joins
Jonny Daenen, Frank Neven, Tony Tan +1
While services such as Amazon AWS make computing power abundantly available, adding more computing nodes can incur high costs in, for instance, pay-as-you-go plans while not always…
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…
Regular graphs and the spectra of two-variable logic with counting
Eryk Kopczynski, Tony Tan
The {\em spectrum} of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using on…
Automata for two-variable logic over trees with ordered data values
Tony Tan
Data trees are trees in which each node, besides carrying a label from a finite alphabet, also carries a data value from an infinite domain. They have been used as an abstraction m…
Feasible Automata for Two-Variable Logic with Successor on Data Words
Ahmet Kara, Thomas Schwentick, Tony Tan
We introduce an automata model for data words, that is words that carry at each position a symbol from a finite alphabet and a value from an unbounded data domain. The model is (se…
Graph Reachability and Pebble Automata over Infinite Alphabets
Tony Tan
Let D denote an infinite alphabet -- a set that consists of infinitely many symbols. A word w = a_0 b_0 a_1 b_1 ... a_n b_n of even length over D can be viewed as a directed graph…
Extending Büchi Automata with Constraints on Data Values
Ahmet Kara, Tony Tan
Recently data trees and data words have received considerable amount of attention in connection with XML reasoning and system verification. These are trees or words that, in additi…
On Pebble Automata for Data Languages with Decidable Emptiness Problem
Tony Tan
In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we introduce the so-called top view weak PA. Roug…