Publications

Journal papers

H. Björklund, J. Björklund, and N. Zechner.
Title: Compression of finite-state automata through failure transitions.
Theoretical Computer Science (TCS), accepted for publication, to appear.

M. Berglund, H. Björklund, and J. Björklund.
Shuffled Languages - Representation and Recognition.
Theoretical Computer Science (TCS), Vol 489-490, pp. 1-20, Elsevier 2013.

H. Björklund and W. Martens.
The Tractability Frontier for NFA Minimization.
Journal of Computer and System Sciences (JCSS), Vol 78, pp. 198-210, Elsevier 2012.

H. Björklund, W. Martens, and T. Schwentick.
Conjunctive Query Containment over Trees.
Journal of Computer and System Sciences (JCSS), Vol. 77, pp. 450-472, Elsevier 2011.

H. Björklund, W. Gelade, and W. Martens.
Incremental XPath Evaluation.
ACM Transactions on Database Systems (TODS), Vol. 35, article 29, 2010.

H. Björklund and T. Schwentick.
On notions of regularity for data languages.
Theoretical Computer Science (TCS), Vol. 411, pp. 702-715, Elsevier 2010.

H. Björklund and S. Vorobyov.
A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games.
Discrete Applied Mathematics, Vol. 155, pp. 210-229, Elsevier 2007.

H. Björklund and S. Vorobyov.
Combinatorial structure and randomized subexponential algorithms for infinite games.
Theoretical Computer Science, Vol. 349, pp. 347-360, Elsevier 2005.

H. Björklund, S. Sandberg, and S. Vorobyov.
Memoryless determinacy of parity and mean payoff games: A simple proof.
Theoretical Computer Science, Vol. 310, pp. 365-378, 2004.

Conference papers

H. Björklund, and P. Ericson.
A Note on the Complexity of Deterministic Tree-Walking Transducers.
Non-Classical Models of Automata (NCMA'13), pp. 69-83, Austrian Computer Society 2013.

H. Björklund, W. Martens, and T. Schwentick.
Validity of Tree Pattern Queries with Respect to Schema Information.
Mathematical Foundations of Computer Science (MFCS'13), pp. 171-182, Springer 2013.

M. Berglund, H. Björklund, and F. Drewes.
On the Parameterized Complexity of Linear Context-Free Rewriting Systems.
Mathematics of Language 13 (MoL13 2013), pp. 21-29, Association for Computational Linguistics 2013.

M. Berglund, H. Björklund, F. Drewes, B. van der Merwe, and B. Watson.
Cuts in Regular Expressions.
Developments in Language Theory (DLT 2013), pp. 70-81, Springer 2013.

H. Björklund, M. Schuster, T. Schwentick, and J. Kulbatzki.
On Optimum Left-to-Right Strategies for Active Context-Free Games.
International Conference on Database Theory (ICDT 2013), pp. 105-116, ACM 2013.

M. Berglund, H. Björklund, and J. Högberg.
Recognizing Shuffled Languages.
Language and Automata Theory and Applications (LATA 2011), LNCS 6638, pp. 142-154, Springer 2011.

S. Bensch, H. Björklund, and F. Drewes.
Algorithmic Properties of Millstream Systems .
Developments in Language Theory (DLT 2010), LNCS 6224, pp. 54-65, Springer 2010.

H. Björklund, W. Gelade, M. Marquardt, and W. Martens.
Incremental XPath Evaluation.
12^th International Conference on Database Theory (ICDT 2009), pp. 162-173, ACM 2009.

H. Björklund, W. Martens, and T. Schwentick.
Optimizing Conjunctive Queries over Trees Using Schema Information.
In 33^d International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), LNCS 5162, pp. 132-143, Springer 2008.

H. Björklund and W. Martens.
The Tractability Frontier for NFA Minimization.
In 35^th International Colloquium on Automata, Languages and Programming (ICALP(2)'08), LNCS 5126, pp. 27-38, Springer 2008.

H. Björklund, W. Martens, and T. Schwentick.
Conjunctive Query Containment over Trees.
In 11^th International Symposium on Database Programming Languages (DBPL'07), LNCS 4797, pp. 66-80, Springer 2007.

H. Björklund and M. Bojanczyk.
Shuffle expressions and words with nested data.
In 32^nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07), LNCS 4708, pp. 750-761, Springer 2007.

H. Björklund and T. Schwentick.
On notions of regularity for data languages.
In 16^th International Symposium on Fundamentals of Computation Theory (FCT'07), LNCS 4639, pp. 88-99, Springer, 2007.

H. Björklund and M. Bojanczyk.
Bounded depth data trees.
In L. Arge et al., editors, 34^th International Colloquium on Automata, Languages and Programming (ICALP'07), LNCS 4596, pp. 862-874, Springer, 2007.

H. Björklund, S. Sandberg, and S. Vorobyov.
A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games.
In, J. Fiala, et. al., editors, 29^th International Symposium on Mathematical Foundations of Computer Science (MFCS'04), LNCS 3153, pp. 673-685, Springer, 2004.

H. Björklund, O. Nilsson, O. Svensson, and S. Vorobyov.
The controlled linear programming problem.
Abstract. In 16^th Nordic Workshop on Programming Theory (NWPT'04), Technical Report 2004-041, Department of Information Technology, Uppsala University, pp. 45-47, 2004. http://www.it.uu.se/research/reports/

H. Björklund, S. Sandberg, and S. Vorobyov.
A discrete subexponential algorithm for parity games.
In H. Alt and M. Habib, editors, 20^th International Symposium on Theoretical Aspects of Computer Science (STACS'03), LNCS 2607, pages 663-674, Springer-Verlag, 2003.

H. Björklund, S. Sandberg, and S. Vorobyov.
Complexity of model checking by iterative improvement: the pseudo-Boolean framework.
In A. Zamulin, editor, Andrei Ershov Fifth International Conference: ``Perspectives of System Informatics'' (PSI'03), LNCS 2890, pp. 381-394, Springer 2003.

H. Björklund, S. Sandberg, and S. Vorobyov.
On fixed-parameter complexity of infinite games.
Abstract. In Nordic Workshop on Programming Theory (NWPT'03). Editors: K. Sere and M. Walden. Published by Åbo Akademi, Dept. of Computer Science, pp. 62-64, 2003.

H. Björklund and S. Sandberg.
Algorithms for combinatorial optimization and games adapted from linear programming.
In B. ten Cate, editor, Proceedings of the Eighth ESSLLI Student Session, pp. 13-24, 2003.

Book chapters

H. Björklund.
State Verification.
In M. Broy et al, editors, Model Based Testing of Reactive Systems, LNCS 3472, pp. 69-86, Springer 2005.

Popular science

H. Björklund, W. Martens, N. Schweikardt, and T. Schwentick.
Logik und Automaten: ein echtes Dreamteam.
Informatik Spektrum, Vol. 33(5), pp. 452-461, 2010.

Dissertation

H. Björklund.
Combinatorial optimization for infinite games on graphs.
Acta Universitatis Upsaliensis. Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology 3. Uppsala 2005. ISBN 91-554-6129-8. Opponent: Professor E. Grädel (RWTH Aachen).