Back to the main page

Journal and proceedings papers: (my dblp list)

• Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing
  Chia-Hsuan Lu, Tony Tan and Michael Benedikt
  To appear in the proceedings of TACAS 2026
  https://arxiv.org/abs/2510.18591
  https://zenodo.org/records/17485304

• Model Counting for Dependency Quantified Boolean Formulas (pdf)
  Long-Hin Fung, Che Cheng, Jie-Hong Roland Jiang, Friedrich Slivovsky, Tony Tan
  To appear in the proceedings of AAAI 2026
  https://arxiv.org/abs/2511.07337
  https://github.com/Sat-DQBF/sharp2DQR

• Analysis of logics with arithmetic
  Michael Benedikt, Chia-Hsuan Lu, Tony Tan
  To appear in the proceedings of CSL 2026
  https://arxiv.org/abs/2508.03574

• Decidability of Graph Neural Networks via Logical Characterizations
  Michael Benedikt, Chia-Hsuan Lu, Boris Motik, Tony Tan
  Proceedings of ICALP 2024
  Accepted with minor revision in ACM TOCL
  https://arxiv.org/abs/2404.18151

• Fine-Grained Complexity Analysis of Dependency Quantified Boolean Formulas (pdf)
  Che Cheng, Long-Hin Fung, Jie-Hong Roland Jiang, Friedrich Slivovsky, Tony Tan
  Proceedings of SAT 2025
  Invited to Journal of AI and Journal of AI Research
  Submitted to Journal of AI Research

• Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting
  Louwe Kuijer, Tony Tan, Frank Wolter, Michael Zakharyaschev
  Proceedings of LICS 2025 (an extended abstract also appears in DL 2024)
  https://arxiv.org/abs/2504.20491

• Two Variable Logic with Ultimately Periodic Counting (pdf)
  Michael Benedikt, Egor Kostylev, Tony Tan
  SIAM Journal on Computing 53(4): 884--968 (2024)
  The preliminary version appears in the Proceedings of ICALP 2020

• 2-DQBF Solving and Certification via Property-Directed Reachability Analysis (pdf)
  Long-Hin Fung, Che Cheng, Yu-Wei Fan, Tony Tan, Jie-Hong Roland Jiang
  Proceedings of FMCAD 2024 (best paper award)
  Invited and submitted to Formal Methods in System Designs
  https://github.com/Sat-DQBF/2DQR-using-ABC

• On two-variable guarded fragment logic with expressive local Presburger constraints (pdf)
  Chia-Hsuan Lu, Tony Tan
  Logical Methods in Computer Science 20(3) (2024)
  https://arxiv.org/abs/2206.13731

• On the Complexity of k-DQBF (pdf)
  Long-Hin Fung, Tony Tan
  Proceedings of SAT 2023

• Reducing NEXP-complete problems to DQBF
  Fa-Hsun Chen, Shen-Chang Huang, Yu-Cheng Lu, Tony Tan
  Proceedings of FMCAD 2022
  https://arxiv.org/abs/2208.06014

• On Classical Decidable Logics Extended with Percentage Quantifiers and Arithmetics
  Bartosz Bednarczyk, Maja Orlowska, Anna Pacanowska, Tony Tan
  Proceedings of FSTTCS 2021
  https://arxiv.org/abs/2106.15250

• Towards a more efficient approach for the satisfiability of two-variable logic
  Ting-Wei Lin, Chia-Hsuan Lu, Tony Tan
  Proceedings of LICS 2021
  https://arxiv.org/abs/2104.10621

• A simple combinatorial proof for the small model property of two-variable logic
  Yanger Ma, Tony Tan
  Information Processing Letter, September 2021

• Subsequence versus substring constraints in sequence pattern languages
  Steven Engels, Tony Tan, Jan Van den Bussche
  Acta Informatica 58(1): 35-56 (2021)

• Finite-State Map-Reduce Computation and Relational Algebra Queries
  Frank Neven, Nicole Schweikardt, Frédéric Servais, Tony Tan
  ACM Transactions on Computational Logic (ACM TOCL) 19(2): 14:1-14:37 (2018)

• A note on first-order spectra with binary relations (pdf)
  Eryk Kopczynski and Tony Tan
  Logical Methods in Computer Science (LMCS) 14(2) (2018)
  https://arxiv.org/abs/1706.08691

• Register automata with linear arithmetic
  Yu-fang Chen, Ondrej Lengal, Tony Tan, Zhilin Wu
  Proceedings of LICS 2017
  https://arxiv.org/abs/1704.03972

• Parallel evaluation of multi-semi-join
  Jonny Daenen, Frank Neven, Tony Tan, Stijn Vansummeren
  Proceedings of VLDB Endowment 9(10): 732--743 (2016)
  https://arxiv.org/abs/1605.05219

• Regular expressions for data words (pdf)
  Leonid Libkin, Tony Tan, Domagoj Vrgoc
  Journal of Computer and System sciences 81(7): 1278-1297 (2015)

• On the Variable Hierarchy of First-Order Spectra (pdf)
  Eryk Kopczynski and Tony Tan
  ACM Transactions on Computational Logic 16(2):17 (2015)
  http://arxiv.org/abs/1403.2225

• Regular graphs and the spectra of two-variable logic with counting (pdf)
  Eryk Kopczynski and Tony Tan
  SIAM Journal on Computing 44(3):786--818 (2015)
  http://arxiv.org/abs/1304.0829

• Distributed Streaming with Finite Memory (pdf)
  Frank Neven, Nicole Schweikardt, Frederic Servais, Tony Tan
  Proceedings of ICDT 2015

• Gumbo: Guarded Fragment Queries over Big Data (pdf)
  Jonny Daenen, Frank Neven, Tony Tan
  Proceedings of EDBT 2015

• Regular Expressions for Querying Data graphs (pdf)
  Tony Tan and Domagoj Vrgoc
  International Journal of Foundations of Computer Science 25(8):971--986 (2014)
  Special issue of DLT 2013
  Proceedings of DLT 2013 under the title: Regular Expressions with Binding over Data Words for Querying Graph Databases (pdf)

• Extending Two-variable Logic on Data Trees with Order on Data Values and its Automata (pdf)
  Tony Tan
  ACM Transactions on Computational Logic 15(1):8 (2014)
  Proceedings of LICS 2012, under the title: An Automata Model for Trees with Ordered Data Values (pdf)
  http://arxiv.org/abs/1212.3251

• Graph Reachability and Pebble Automata over Infinite Alphabets (pdf)
  Tony Tan
  ACM Transactions on Computational Logic 14(3):5 2013
  Proceedings of LICS 2009. (pdf)
  http://arxiv.org/abs/1110.2776

• Efficient Reasoning about Data Trees via Integer Linear Programming (pdf)
  Claire David, Leonid Libkin and Tony Tan
  ACM Transactions on Database Systems 37(3): 19 (2012)
  Best paper award in ICDT 2011 (pdf)

• Feasible Automata for Two-Variable Logic with Successor on Data Words (pdf)
  Ahmet Kara, Thomas Schwentick and Tony Tan
  Proceedings of LATA 2012

• On the Complexity of Query Answering over Incomplete XML Documents (pdf)
  Amelie Gheerbrant, Leonid Libkin and Tony Tan
  Proceedings of ICDT 2012

• A Formalism for Graph Databases and its Model of Computation (pdf)
  Juan Reutter and Tony Tan
  Proceedings of AMW 2011

• A Note on Two-pebble Automata over Infinite Alphabets (pdf)
  Michael Kaminski and Tony Tan
  Fundamenta Informaticae 98(4): 379--390 (2010)

• On the Satisfiability of Two-Variable Logic over Data Words (pdf)
  Claire David, Leonid Libkin and Tony Tan
  Proceedings of LPAR 2010

• On Pebble Automata for Data Languages with Decidable Emptiness Problem (pdf)
  Tony Tan
  Proceedings of MFCS 2009
  Journal of Computer and System Sciences 76(8): 778--791 (2010)

• Tree Automata over Infinite Alphabets (pdf)
  Michael Kaminski and Tony Tan
  Pillars of Computer Science 2008, pages 386--423, LNCS 4800, Springer-Verlag

• Subdividing Alpha Complex (pdf)
  Alan Cheng Ho-lun and Tony Tan
  Computational Geometry 39(2): 104--117 (2008)
  Proceedings of MFCS 2005

• Regular Expressions for Languages over Infinite Alphabets (pdf)
  Michael Kaminski and Tony Tan
  Proceedings of COCOON 2004
  Fundamenta Informaticae 69(3): 301--318 (2006)

• Subdividing Alpha Complex (pdf)
  Alan Cheng Ho-lun and Tony Tan
  Proceedings of FSTTCS 2004

(End of page)