Skip to Content

Path: DBAI > staff >

Tools: Drucken

• Sergei Vorobyov. Infinite Games and Linear Programming: A Survey. Discrete Applied Mathematics, to appear.
• Henrik Bjorklund and Sergei Vorobyov. A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics, 2007, vol 155, issue 2, pp. 210-229. (Retrieve an official copy from Science Direct )
• Daniel Andersson and Sergei Vorobyov. Fast Algorithms for Monotonic Discounted Linear Programs with Two Variables per Inequality. Isaac Newton Institute for Mathematical Sciences, Cambridge, UK. Preprint NI06019-LAA, May 2006. To appear in Theoretical Computer Science. (Daniel's Master Thesis, defended on 30 August 2006)
• Ola Svensson and Sergei Vorobyov. Linear Complementarity and P-matrices for Stochastic Games. 6th International Andrei Ershov Memorial Conference ``Perspectives of System Informatics'' (PSI'06), June 2006, Lecture Notes in Computer Science, vol. 4378, pp. 408-421.
• Ola Svensson and Sergei Vorobyov. Linear Programming Polytope and Algorithm for Mean Payoff Games. 2nd International Conference on Algorithmic Aspects in Information and Management, Hong Kong, China, June 2006, Lecture Notes in Computer Science, vol. 4041, pp. 64-78.
• Ola Svensson and Sergei Vorobyov. LP-Polytopes for Mean Payoff Games. RUTCOR Research Report RRR 34-2005, RUTCOR, Rutgers Center of Operations Research
• Henrik Bjorklund and Sergei Vorobyov. Combinatorial Structure and Randomized Subexponential Algorithms for Infinite Games . Theoretical Computer Science, 2005, 349(3): 347-360. To access the article, please go to http://www.sciencedirect.com/sd/article/S0304397505005761
• Ola Svensson and Sergei Vorobyov. A Subexponential Algorithm for a Subclass of P-Matrix Generalized Linear Complementarity Problems. DIMACS Technical Report 2005-20. Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, USA, June 2005.
• Henrik Bjorklund's, PhD Thesis defended on 18 February 2005. Contains several papers we coauthored (I was the supervisor, Erich Graedel the Opponent, Georg Gottlob, Johan Hastad, and Wang Yi the Committee Members)
• Henrik Bjorklund, Ola Svensson, and Sergei Vorobyov. Linear Complementarity Algorithms for Mean Payoff Games. DIMACS Technical Report 2005-05. Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, USA, February 2005.
• Henrik Bjorklund, Olle Nilsson, Ola Svensson, and Sergei Vorobyov. Controlled Linear Programming: Boundedness and Duality. DIMACS Technical Report 2004-56. Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, USA, December 2004.
• Henrik Bjorklund, Olle Nilsson, Ola Svensson, and Sergei Vorobyov. The Controlled Linear Programming Problem. DIMACS Technical Report 2004-41. Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, USA, September 2004.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. Randomized Subexponential Algorithms for Infinite Games. DIMACS Technical Report 2004-09. Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, USA, April 2004.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games. DIMACS Technical Report 2004-05. Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, USA, March 2004. Short MFCS'04 version in the Proceedings of the 29th Intl Symp on Mathematical Foundations of Computer Science (MFCS'2004), August 2004, Springer LNCS 3153.
• Sergei Vorobyov. The Most Nonelementary Theory. Information and Computation. Vol. 190, Issue 2, pp. 196-219 (2004). ScienceDirect reference
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. On Fixed-Parameter Complexity of Infinite Games. Technical Report TR-2003-038 Department of Information Technology, Uppsala University, August 2003.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. Memoryless determinacy of parity and mean payoff games: A simple proof. Theoretical Computer Science (Elsevier), vol 310 (2004), pp. 365-378.
• Henrik Bjorklund, Sven Sandberg and Sergei Vorobyov. Complexity of Model Checking by Iterative Improvement: the Pseudo-Boolean Framework. Proc. Andrei Ershov Fifth International Conference "Perspectives of System Informatics", pp. 262-270, July 9-12, 2003, Novosibirsk, Russia. Final version: Springer Lecture Notes in Computer Science, vol 2890, pp. 381-394 (2003), Broy, M. and Zamulin, A., editors. Direct Springer Link
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. Randomized Subexponential Algorithms for Parity Games. Technical Report TR-2003-019. Department of Information Technology, Uppsala University, April 2003.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. An Improved Subexponential Algorithm for Parity Games. Technical Report TR-2003-017. Department of Information Technology, Uppsala University, March 2003.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. On Combinatorial Structure and Algorithms for Parity Games Technical Report TR-2003-002. Department of Information Technology, Uppsala University, January 2003.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. Memoryless Determinacy of Parity and Mean Payoff Games: A Simple Proof. Technical Report TR-2002-033. Department of Information Technology, Uppsala University, October 2002.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. An Experimental Study of Algorithms for Completely Unimodal Optimization. Technical Report TR-2002-030, Department of Information Technology, Uppsala University, October 2002.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. A Discrete Subexponential Algorithms for Parity Games.
  • Technical Report TR-2002-26, Department of Information Technology, Uppsala University, September 13, 2002
  • Short version presented at the EU Games Project Meeting, Edinburgh, September 2002.
  • Proc. 20th International Symposium on Theoretical Aspects of Computer Science (STACS'2003), Berlin, March 2003, Springer Lecture Notes in Computer Science, vol. 2607, pp. 663-674.
• Henrik Bjorklund, Sven Sandberg, and Sergei Vorobyov. Optimization on Completely Unimodal Hypercubes. Technical Report TR-2002-018, Department of Information Technology, Uppsala University, May 2002.
• The Undecidability of the First-Order Theories of One Step Rewriting in Linear Canonical Systems. Information and Computation, 175, 182-213 (2002)
• Henrik Bjorklund and Sergei Vorobyov. Two Adversary Lower Bounds for Parity Games. Technical Report TR-2002-008, Department of Information Technology, Uppsala University, February 2002. Short version to be presented at LICS'2002.
• Emmanuel Beffara and Sergei Vorobyov. Adapting Gurvich-Karzanov-Khachiyan's Algorithm for Parity Games: Implementation and Experimentation, Technical Report TR-2001-020, Department of Information Technology, Uppsala University. Short version to be presented at LICS'2002.
• Henrik Bjorklund, Viktor Petersson, and Sergei Vorobyov. Experiments with Iterative Improvement Algorithms on Completely Unimodal Hypercubes, Technical Report, 2001-017 Information Technology/Uppsala University.
• Viktor Petersson and Sergei Vorobyov. Parity games: interior-point approach. Technical Report 2001-010, Department of Information Technology, Uppsala Unitersity.
• A randomized subexponential algorithm for parity games Viktor Petersson and Sergei Vorobyov. Nordic Journal of Computing, Vol 8, No. 3, 2001. Preliminary version: Technical Report 2001-001, Department of Information Technology, Uppsala Unitersity. Also: 12th Nordic Workshop on Programming Theory.
• AE^5-Equational Theory of Context Unification is Undecidable. Theoretical Computer Science, 2002, vol. 275, pp. 463-479.
• The Undecidability of the First-Order Theories of One Step Rewriting in Linear Canonical Systems. Information and Computation, 2002, vol. 174, pp 1-32. (to appear).
• Better Decision Algorithms for Parity Games and the Mu-Calculus Model Checking. Technical Report 2000-014, Information Technology/Computing Science Department. June 2000, Information Processing Letters, to appear.
• New Lower Bounds for the Expressiveness and the Higher-Order Matching Problem in the Simply Typed Lambda Calculus. Technical Report MPI-I-1999-3-001, Max-Planck Institut fuer Informatik, Saarbruecken, Germany, July 1999.
• Subtyping Functional + Nonempty Record Types. Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL'98). Springer Lecture Notes in Computer Science, vol, 1584, pp. 280-295, 1999. Brno, Czech Republic, August 24-28, 1998.
• AE*-Equational Theory of Context Unification is Pi_1^0-Hard. Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS'98). Springer Lecture Notes in Computer Science, vol, 1450, pp. 597-606, 1998. Brno, Czech Republic, August 24-28, 1998.
• Complexity of Nonrecursive Logic Programs with Complex Values (Andrei Voronkov and Sergei Vorobyov). Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'98)", pp. 244-253. Seattle, Washington, June 1-3, 1998.
• The Undecidability of the First-Order Theories of One Step Rewriting in Linear Canonical Systems. Technical Report MPI-I-1998-2-009, Max-Planck Institut fuer Informatik, Saarbruecken, Germany, May, 1998.
• AE-Equational Theory of Context Unification is Co-RE-Hard. Technical Report MPI-I-1998-2-008, Max-Planck Institut fuer Informatik, Saarbruecken, Germany, March, 1998.
• The Most Nonelementary Theory (A Direct Lower Bound Proof). Technical Report MPI-I-1998-2-007, Max-Planck Institut fuer Informatik, Saarbruecken, Germany, April, 1998.
• Satisfiability of Functional+Record Subtype Constraints is NP-Hard. Technical Report MPI-I-1998-2-004, Max-Planck Institut fuer Informatik, Saarbruecken, Germany, January, 1998.
• Context Unification = Word Equations + Linear Integer Constraints. Technical Report MPI-I-1998-2-001, Max-Planck Institut fuer Informatik, Saarbruecken, Germany, January, 1998.
• Complexity of Nonrecursive Logic Programs with Complex Values (Andrei Voronkov and Sergei Vorobyov). Technical Report MPI-I-1997-2-010, Max-Planck Institut fuer Informatik, Saarbruecken, Germany, November, 1997.
• The "Hardest" Natural Decidable Theory. Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science (LICS'97), pp. 294--305. Warsaw, June 29-July 2, 1997.
• The First-Order Theory of One Step Rewriting in Linear Noetherian Systems is Undecidable. Proceedings of the 8th International Conference on Rewriting Techniques and Applications (RTA'97). Springer Lecture Notes in Computer Science, vol, 1232, pp. 254--268. Barcelona, Spain, June 1-4, 1997.
• On the Bounded Theories of Finite Trees. Proceedings of the Asian'96 Computing Science Conference (ASIAN'96) Springer Lecture Notes in Computer Science, vol, 1179, pp. 152--161, December 1-3, 1996, Singapore.
• An Improved Lower Bound for the Elementary Theories of Trees". Proceedings of the 13th International Conference on Automated Deduction (CADE'96). Springer Lecture Notes in Artificial Intelligence, vol. 1104, pp. 275--287. New Brunswick, NJ, July/August, 1996.
• Structural decidable extensions of bounded quantification. Proceedings of the 22nd ACM Symposium on Principles of Programming Languages (POPL'95), pp. 164--175. San Francisco, CA, January, 1995.
• Fsub with Recursive Types: `Types-as-Propositions' Interpretations M. Rabin's S2S. Proc. Journees Francophones des Langages Applicatifs (JFLA'95), INRIA, France, pp. 49-73. Bois d'Amont, Jura, France, January, 1995.
• Could Orders be Captured by Term Rewriting Systems? Proceedings of the 3rd International Workshop on Conditional Rewriting Systems (CTRS'92), Springer Lecture Notes in Computer Science, vol. 656, pp. 315--327. Pont-a-Mousson, Lorraine, France, July, 1992.
• "A Structural Completeness Theorem for a Class of Conditional Rewrite Rule Systems. Proceedings of the International Conference on Computer Logic (COLOG'88). Springer Lecture Notes in Computer Science, vol. 417", pp. 313-326, 1990. Tallinn, Estonia, December 1988.
• Conditional Rewrite Rule Systems with Built-in Arithmetic and Induction. Proceedings of the 3rd International Conference on Rewriting, Techniques and Applications (RTA'89). Springer Lecture Notes in Computer Science, vol, 355, pp. 492-512, Chapel Hill, NC, April 1989.
• On the Arithmetic Inexpressiveness of Term Rewriting Systems. Proceedings of the 3rd Annual IEEE Symposium on Logic in Computer Science (LICS'88), pp. 212-217, Edinburgh, Scotland, June, 1988.

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist die Fakultät für Informatik an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung