uu.seUppsala University Publications
Change search
Refine search result
1234567 101 - 150 of 833
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 101.
    Bengtson, Jesper
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Formalising the pi-calculus using nominal logic2007In: FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES, PROCEEDINGS / [ed] Seidl, H, 2007, p. 63-77Conference paper (Refereed)
    Abstract [en]

    We formalise the pi-calculus using the nominal datatype package, a package based on ideas from the nominal logic by Pitts et al., and demonstrate an implementation in Isabelle/HOL. The purpose is to derive powerful induction rules for the semantics in order to conduct machine checkable proofs, closely following the intuitive arguments found in manual proofs. In this way we have covered many of the standard theorems of bisimulation equivalence and congruence, both late and early, and both strong and weak in a unison manner. We thus provide one of the most extensive formalisations of a process calculus ever done inside a theorem prover.

    A significant gain in our formulation is that agents are identified up to alpha-equivalence, thereby greatly reducing the arguments about bound names. This is a normal strategy for manual proofs about the pi-calculus, but that kind of hand waving has previously been difficult to incorporate smoothly in an interactive theorem prover. We show how the nominal logic formalism and its support in Isabelle accomplishes this and thus significantly reduces the tedium of conducting completely formal proofs. This improves on previous work using weak higher order abstract syntax since we do not need extra assumptions to filter out exotic terms and can keep all arguments within a familiar first-order logic.

  • 102.
    Bengtson, Jesper
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Formalising the π-calculus using nominal logic2009In: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 5, no 2, p. 16:1-36Article in journal (Refereed)
  • 103.
    Bengtson, Jesper
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Psi-calculi in Isabelle2009In: Theorem Proving in Higher Order Logics, Berlin: Springer-Verlag , 2009, p. 99-114Conference paper (Refereed)
    Abstract [en]

    Psi-calculi are extensions of the pi-calculus, accommodating arbitrary nominal datatypes to represent not only data but also communication channels, assertions and conditions, giving it an expressive power beyond the applied pi-calculus and the concurrent constraint pi-calculus.

    We have formalised psi-calculi in the interactive theorem prover Isabelle using its nominal datatype package. One distinctive feature is that the framework needs to treat binding sequences, as opposed to single binders, in an efficient way. While different methods for formalising single binder calculi have been proposed over the last decades, representations for such binding sequences are not very well explored.

    The main effort in the formalisation is to keep the machine checked proofs as close to their pen-and-paper counterparts as possible. We discuss two approaches to reasoning about binding sequences along with their strengths and weaknesses. We also cover custom induction rules to remove the bulk of manual alpha-conversions.

  • 104.
    Bengtson, Jesper
    et al.
    IT Univ Copenhagen, Copenhagen, Denmark..
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Weber, Tjark
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Psi-Calculi in Isabelle2016In: Journal of automated reasoning, ISSN 0168-7433, E-ISSN 1573-0670, Vol. 56, no 1, p. 1-47Article in journal (Refereed)
    Abstract [en]

    This paper presents a mechanisation of psi-calculi, a parametric framework for modelling various dialects of process calculi including (but not limited to) the pi-calculus, the applied pi-calculus, and the spi calculus. psi-calculi are significantly more expressive, yet their semantics is as simple in structure as the semantics of the original pi-calculus. Proofs of meta-theoretic properties for psi-calculi are more involved, however, not least because psi-calculi (unlike simpler calculi) utilise binders that bind multiple names at once. The mechanisation is carried out in the Nominal Isabelle framework, an interactive proof assistant designed to facilitate formal reasoning about calculi with binders. Our main contributions are twofold. First, we have developed techniques that allow efficient reasoning about calculi that bind multiple names in Nominal Isabelle. Second, we have adopted these techniques to mechanise substantial results from the meta-theory of psi-calculi, including congruence properties of bisimilarity and the laws of structural congruence. To our knowledge, this is the most extensive formalisation of process calculi mechanised in a proof assistant to date.

  • 105. Bergami, Giacomo
    et al.
    Magnani, Matteo
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Montesi, Danilo
    University of Bologna.
    A Join Operator for Property Graphs2017In: EDBT/ICDT Workshops, 2017Conference paper (Refereed)
    Abstract [en]

    In the graph database literature the term “join” does not refer to an operator combining two graphs, but involves path traversal queries over a single graph. Current languages express binary joins through the combination of path traversal queries with graph creation operations. Such solution proves to be not efficient.

    In this paper we introduce a binary graph join opera- tor and a corresponding algorithm outperforming the solution proposed by query languages for either graphs (Cypher, SPARQL) and relational databases (SQL). This is achieved by using a specific graph data structure in secondary memory showing better performance than state of the art graph libraries (Boost Graph Library, SNAP) and database systems (Sparksee). 

  • 106.
    Berglund, Anders
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Pears, Arnold
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Nylén, Aletta
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Ahmad, Farooq
    Al Baha University, Al Baha, Saudi Arabia.
    Alghamdi, Bader
    Al Baha University, Al Baha, Saudi Arabia.
    Alghamdi, Khalid
    Al Baha University, Al Baha, Saudi Arabia.
    Alhabish, Ahmed
    Al Baha University, Al Baha, Saudi Arabia.
    Aljoufi, Abdullah
    Al Baha University, Al Baha, Saudi Arabia.
    Alzahrani, Eidah
    Al Baha University, Al Baha, Saudi Arabia.
    Alzahrani, Rami
    Al Baha University, Al Baha, Saudi Arabia.
    Aldmour, Ismat
    Al Baha University, Al Baha, Saudi Arabia.
    Athama, Areej
    Al Baha University, Al Baha, Saudi Arabia.
    AlSadoon, Hamada Shihad
    Al Baha University, Al Baha, Saudi Arabia.
    Budiarto, Rahmat
    Al Baha University, Al Baha, Saudi Arabia.
    Hafeez, Abdul
    Al Baha University, Al Baha, Saudi Arabia.
    Daupota, Nadeem Hassan
    Al Baha University, Al Baha, Saudi Arabia.
    Faiz, Dhafer
    Al Baha University, Al Baha, Saudi Arabia.
    Gabralla, Lubna Abdel Kareim
    Al Baha University, Al Baha, Saudi Arabia.
    Gamar, Mohammad
    Al Baha University, Al Baha, Saudi Arabia.
    Hannan, Abdul
    Al Baha University, Al Baha, Saudi Arabia.
    Kerim, Bedine
    Al Baha University, Al Baha, Saudi Arabia.
    Mazarbhuiya, F. A.
    Al Baha University, Al Baha, Saudi Arabia.
    Rabea, Ahmed
    Al Baha University, Al Baha, Saudi Arabia.
    Saleem, Muhammad Qaiser
    Al Baha University, Al Baha, Saudi Arabia.
    Saleh, Nimir
    Al Baha University, Al Baha, Saudi Arabia.
    Shenify, Mohamed
    Al Baha University, Al Baha, Saudi Arabia.
    Teaching and Learning Computer Science at Al Baha University, Saudi Arabia: Insights from a staff development course2015In: Proc. 3rd International Conference on Learning and Teaching in Computing and Engineering, Los Alamitos, CA: IEEE Computer Society, 2015, p. 1-6Conference paper (Refereed)
    Abstract [en]

    In this special session we meet a set of projects in computer science and engineering education at a university in Saudi Arabia. They are the product of a pedagogical development course ran in collaboration with a Swedish university during the academic year 2013/2014. The projects reflect the local situation, with its possibilities and challenges, and suggest steps to take, in the local environment, to enhance education. As such it is a unique document that brings insights from computer science and engineering education into the international literature.

  • 107.
    Bhat, Sooraj
    et al.
    Georgia Institute of Technology.
    Borgström, Johannes
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gordon, Andrew D.
    Microsoft Research, Cambridge.
    Russo, Claudio
    Microsoft Research, Cambridge.
    Deriving Probability Density Functions from Probabilistic Functional Programs2013In: Tools and Algorithms for the Construction and Analysis of Systems: 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings / [ed] N. Piterman and S. Smolka, Berlin/Heidelberg: Springer Berlin/Heidelberg, 2013, p. 508-522Conference paper (Refereed)
    Abstract [en]

    The probability density function of a probability distribution is a fundamental concept in probability theory and a key ingredient in various widely used machine learning methods. However, the necessary framework for compiling probabilistic functional programs to density functions has only recently been developed. In this work, we present a density compiler for a probabilistic language with discrete and continuous distributions, and discrete observations, and provide a proof of its soundness. The compiler greatly reduces the development effort of domain experts, which we demonstrate by solving inference problems from various scientific applications, such as modelling the global carbon cycle, using a standard Markov chain Monte Carlo framework. 

  • 108. Bhat, Sooraj
    et al.
    Borgström, Johannes
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gordon, Andrew D.
    Russo, Claudio
    Deriving Probability Density Functions from Probabilistic Functional Programs2017In: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 13, no 2, article id 16Article in journal (Refereed)
    Abstract [en]

    The probability density function of a probability distribution is a fundamental concept in probability theory and a key ingredient in various widely used machine learning methods. However, the necessary framework for compiling probabilistic functional programs to density functions has only recently been developed. In this work, we present a density compiler for a probabilistic language with failure and both discrete and continuous distributions, and provide a proof of its soundness. The compiler greatly reduces the development effort of domain experts, which we demonstrate by solving inference problems from various scientific applications, such as modelling the global carbon cycle, using a standard Markov chain Monte Carlo framework.

  • 109.
    Björdal, Gustav
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Flener, Pierre
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Pearson, Justin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Stuckey, Peter J.
    Tack, Guido
    Declarative local-search neighbourhoods in MiniZinc2018In: PROCEEDINGS OF THE 2018 IEEE 30TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI), IEEE Computer Society, 2018, p. 98-105Conference paper (Refereed)
    Abstract [en]

    The aim of solver-independent modelling is to create a model of a satisfaction or optimisation problem independent of a particular technology. This avoids early commitment to a solving technology and allows easy comparison of technologies. MiniZinc is a solver-independent modelling language, supported by CP, MIP, SAT, SMT, and constraint-based local search (CBLS) backends. Some technologies, in particular CP and CBLS, require not only a model but also a search strategy. While backends for these technologies offer default search strategies, it is often beneficial to include in a model a user-specified search strategy for a particular technology, especially if the strategy can encapsulate knowledge about the problem structure. This is complex since a local-search strategy (comprising a neighbourhood, a heuristic, and a meta-heuristic) is often tightly tied to the model. Hence we wish to use the same language for specifying the model and the local search. We show how to extend MiniZinc so that one can attach a fully declarative neighbourhood specification to a model, while maintaining the solver-independence of the language. We explain how to integrate a model-specific declarative neighbourhood with an existing CBLS backend for MiniZinc.

  • 110.
    Björdal, Gustav
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Monette, Jean-Noël
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Flener, Pierre
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Pearson, Justin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    A constraint-based local search backend for MiniZinc2015In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 20, no 3, p. 325-345Article in journal (Refereed)
  • 111.
    Björklund, Henrik
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Combinatorial Optimization for Infinite Games on Graphs2005Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc.

    The infinite games on finite graphs we study in this thesis have their primary applications in verification, but are also of fundamental importance from the complexity-theoretic point of view. They include parity, mean payoff, and simple stochastic games.

    We focus on solving graph games by using iterative strategy improvement and methods from linear programming and combinatorial optimization. To this end we consider old strategy evaluation functions, construct new ones, and show how all of them, due to their structural similarities, fit into a unifying combinatorial framework. This allows us to employ randomized optimization methods from combinatorial linear programming to solve the games in expected subexponential time.

    We introduce and study the concept of a controlled optimization problem, capturing the essential features of many graph games, and provide sufficent conditions for solvability of such problems in expected subexponential time.

    The discrete strategy evaluation function for mean payoff games we derive from the new controlled longest-shortest path problem, leads to improvement algorithms that are considerably more efficient than the previously known ones, and also improves the efficiency of algorithms for parity games.

    We also define the controlled linear programming problem, and show how the games are translated into this setting. Subclasses of the problem, more general than the games considered, are shown to belong to NP intersection coNP, or even to be solvable by subexponential algorithms.

    Finally, we take the first steps in investigating the fixed-parameter complexity of parity, Rabin, Streett, and Muller games.

    List of papers
    1. A discrete subexponential algorithm for parity games
    Open this publication in new window or tab >>A discrete subexponential algorithm for parity games
    2003 In: STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, 2003, p. 663-674Chapter in book (Other academic) Published
    Identifiers
    urn:nbn:se:uu:diva-92509 (URN)3-540-00623-0 (ISBN)
    Available from: 2005-01-18 Created: 2005-01-18Bibliographically approved
    2. Complexity of model checking by iterative improvement: the pseudo-Boolean framework
    Open this publication in new window or tab >>Complexity of model checking by iterative improvement: the pseudo-Boolean framework
    2003 In: Perspectives of Systems Informatics: 5th International Andrei Ershov Memorial Conference, 2003, p. 381-394Chapter in book (Other academic) Published
    Identifiers
    urn:nbn:se:uu:diva-92510 (URN)3-540-20813-5 (ISBN)
    Available from: 2005-01-18 Created: 2005-01-18Bibliographically approved
    3. Memoryless determinacy of parity and mean payoff games: a simple proof
    Open this publication in new window or tab >>Memoryless determinacy of parity and mean payoff games: a simple proof
    2004 In: Theoretical Computer Science, ISSN 0304-3975, Vol. 310, p. 365-378Article in journal (Refereed) Published
    Identifiers
    urn:nbn:se:uu:diva-92511 (URN)
    Available from: 2005-01-18 Created: 2005-01-18Bibliographically approved
    4. A combinatorial strongly subexponential algorithm for mean payoff games
    Open this publication in new window or tab >>A combinatorial strongly subexponential algorithm for mean payoff games
    2004 In: Mathematical Foundations of Computer Science 2004, 2004, p. 673-685Chapter in book (Other academic) Published
    Identifiers
    urn:nbn:se:uu:diva-92512 (URN)3-540-22823-3 (ISBN)
    Available from: 2005-01-18 Created: 2005-01-18Bibliographically approved
    5. The controlled linear programming problem: DIMACS Technical Report 2004-41, September 2004
    Open this publication in new window or tab >>The controlled linear programming problem: DIMACS Technical Report 2004-41, September 2004
    Manuscript (Other academic)
    Identifiers
    urn:nbn:se:uu:diva-92513 (URN)
    Available from: 2005-01-18 Created: 2005-01-18 Last updated: 2010-01-13Bibliographically approved
  • 112.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Nilsson, Olle
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Svensson, Ola
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Controlled Linear Programming: Boundedness and Duality2004Report (Other scientific)
    Abstract [en]

    Computer supported work is often stressful and inadequate computer sys-tems and poor usability contribute to the problem. Still the work situation, and work environment of users are seldom considered when developing computer systems, and it is difficult to incorporate the ideas of User Centred Systems Design (UCSD) in practice. Hence, this research addresses the dif-ficulty in integrating usability, UCSD and occupational health issues in IT systems development in order to improve the resulting work situation and well-being of users. How do basic values and perspectives of stakeholders in systems development projects affect the work with UCSD, usability and users’ health issues in the organisations studied?

    This research aims at influencing systems development in practice; hence, research is carried out in real life settings with an action research approach. Data is gathered and analysed with a qualitative research approach with in-terview studies, meetings with stakeholders, analysis of documentation, ob-servations and field studies. The theoretical framework adheres to situated action, participatory design, and UCSD that stresses the importance of in-volving users in the design process.

    This research shows that several basic values and perspectives affect sys-tems development and hinder the usability work, for example, the perspec-tive on user representatives, the value of rationality and objectivity, and the perspective underpinning descriptions and discourse on work. Moreover, this research indicates that the strong business values of automation, efficiency and customer satisfaction shape the development of new technology, and ultimately the tasks and work practices of the civil servants. In short, the studies show that there are some contradictions in business values and the implementation of user-centred systems design, usability and health issues in systems development.

    Attitudes and perspectives are not easily changed, and change comes gradually. In these organisations, we continuously discuss the integration of health issues in systems development, and by introducing and changing the models of systems development these will hopefully enable communication and change forwards of new perspectives and values. However, a focus on models alone is insufficient and therefore we need to develop a systematic approach to include reflection and new perspectives. Perhaps the reflection itself would help us see our values and perspectives and to alter them?

  • 113.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Nilsson, Olle
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Svensson, Ola
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    The Controlled Linear Programming Problem2004Report (Other scientific)
  • 114.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming2003Report (Other scientific)
  • 115.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming2003In: Proceedings of the Eighth European Summer School on Logic, Language, and Information (ESSLLI) Student Session, 2003, p. 13-24Conference paper (Refereed)
  • 116.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games2004Report (Other (popular scientific, debate etc.))
  • 117.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    A Discrete Subexponential Algorithm for Parity Games2003Report (Other scientific)
  • 118.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    A Discrete Subexponential Algorithm for Parity Games2003In: Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, STACS'2003, 2003Conference paper (Refereed)
  • 119.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    An Experimental Study of Algorithms for Completely Unimodal Optimization2002Report (Other scientific)
  • 120.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    An Improved Subexponential Algorithm for Parity Games2003Report (Other scientific)
  • 121.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Complexity of Model Checking by Iterative Improvement: the Pseudo-Boolean Framework2003In: Proceedings of the Andrei Ershov Fifth International Conference ``Perspectives of System Informatics'', 2003, p. 381-394Conference paper (Refereed)
  • 122.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Sandberg, Sven
    Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Vorobyov, Sergei
    Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Memoryless Determinacy of Parity and Mean Payoff Games: A Simple Proof2004In: Theoretical Computer Science, Vol. 310, no 1-3, p. 365-378Article in journal (Other (popular scientific, debate etc.))
  • 123.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Memoryless Determinacy of Parity Games: A Simple Proof2002Report (Other scientific)
  • 124.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    On Combinatorial Structure and Algorithms for Parity Games2003Report (Other scientific)
  • 125.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. COMPUTING SCIENCE.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    On Fixed-Parameter Complexity of Infinite Games2003Report (Other scientific)
  • 126.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Randomized Subexponential Algorithms for Infinite Games2004Report (Other (popular scientific, debate etc.))
    Abstract [en]

    The complexity of solving infinite games, including parity, mean payoff, and simple stochastic games, is an important open problem in verification, automata theory, and complexity theory. In this paper we develop an abstract setting for studying and solving such games, as well as related problems, based on function optimization over certain discrete structures. We introduce new classes of completely local-global (CLG) and recursively local-global (RLG) functions, and show that strategy evaluation functions for parity and simple stochastic games belong to these classes. We also establish a relation to the previously well-studied completely unimodal (CU) and local-global functions. A number of nice properties of CLG-functions are proved. In this setting, we survey several randomized optimization algorithms appropriate for CU-, CLG-, and RLG-functions. We show that the subexponential algorithms for linear programming by Kalai and Matousek, Sharir, and Welzl, can be adapted to optimizing the functions we study, with preserved subexponential expected running time. We examine the relations to two other abstract frameworks for subexponential optimization, the LP-type problems of Matousek, Sharir, Welzl, and the abstract optimization problems of Gärtner. The applicability of our abstract optimization approach to parity games builds upon a discrete strategy evaluation measure. We also consider local search type algorithms, and settle two nontrivial, but still exponential, upper bounds. As applications we address some complexity-theoretic issues including non-PLS-completeness of the problems studied.

  • 127.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Randomized Subexponential Algorithms for Parity Games2003Report (Other scientific)
  • 128.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Svensson, Ola
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
    Controlled Linear Programming for Infinite Games2004Report (Other (popular scientific, debate etc.))
  • 129.
    Björklund, Henrik
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Vorobyov, Sergei
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games2007In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 155, no 2, p. 210-229Article in journal (Refereed)
  • 130.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Two Adversary Lower Bounds for Parity Games2002Report (Other scientific)
    Abstract [en]

    By using the adversary arguments we settle the first exponential lower bounds for restricted classes of algorithms solving Parity Games The first result applies to any algorithms that rely only on estimating values of vertices from the viewpoint of one pl

  • 131.
    Björklund, Henrik
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Vorobyov, Sergei
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Sandberg, Sven
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Optimization on Completely Unimodal Hypercubes2002Report (Other scientific)
    Abstract [en]

    We investigate and compare, both theoretically and practically, several old and new algorithms for the completely unimodal pseudo-boolean function optimization problem. We settle the first nontrivial upper bounds for two well-known local search algorithms

  • 132.
    Blom, Johan
    et al.
    Blossom Grove AB, Jarfalla, Sweden.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Nyström, Sven-Olof
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Industrial Evaluation of Test Suite Generation Strategies for Model-Based Testing2016Conference paper (Refereed)
    Abstract [en]

    We report on a case study on model based testing for a commercially available telecom software system. A main purpose is to investigate how different strategies for test suite generation affect quality attributes of the generated test suites, in a realistic industrial environment. We develop a functional model in the form of an extended finite state machine, from which we generate test suites using several different (model) coverage criteria, alongside with randomly and manually generated test suites. We compare test suites with respect to fault-detection capability, incurred (source) code coverage, and test generation and execution time. The system under test is a commercially released version, not seeded with any faults, implying that exposed faults are "real" faults that passed previous testing. We did not find clear difference between coverage-based and random test suites. Test suite generation and execution is performed using the tool ERLY MARSH, developed by the first author.

  • 133.
    Blomquist, Hanna
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Möller, Johanna
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Anomaly detection with Machine learning: Quality assurance of statistical data in the Aid community2015Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    The overall purpose of this study was to find a way to identify incorrect data in Sida’s statistics about their contributions. A contribution is the financial support given by Sida to a project. The goal was to build an algorithm that determines if a contribution has a risk to be inaccurate coded, based on supervised classification methods within the area of Machine Learning. A thorough data analysis process was done in order to train a model to find hidden patterns in the data. Descriptive features containing important information about the contributions were successfully selected and used for this task. These included keywords that were retrieved from descriptions of the contributions. Two Machine learning methods, Adaboost and Support Vector Machines, were tested for ten classification models. Each model got evaluated depending on their accuracy of predicting the target variable into its correct class. A misclassified component was more likely to be incorrectly coded and was also seen as an anomaly. The Adaboost method performed better and more steadily on the majority of the models. Six classification models built with the Adaboost method were combined to one final ensemble classifier. This classifier was verified with new unseen data and an anomaly score was calculated for each component. The higher the score, the higher the risk of being anomalous. The result was a ranked list, where the most anomalous components were prioritized for further investigation of staff at Sida. 

  • 134.
    Blomqvist, Johanna
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Using XGBoost to classify theBeihang Keystroke Dynamics Database2018Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    Keystroke Dynamics enable biometric security systems by collecting and analyzing computer keyboard usage data. There are different approaches to classifying keystroke data and a method that has been gaining a lot of attention in the machine learning industry lately is the decision tree framework of XGBoost. XGBoost has won several Kaggle competitions in the last couple of years, but its capacity in the keystroke dynamics field has not yet been widely explored. Therefore, this thesis has attempted to classify the existing Beihang Keystroke Dynamics Database using XGBoost. To do this, keystroke features such as dwell time and flight time were extracted from the dataset, which contains 47 usernames and passwords. XGBoost was then applied to a binary classification problem, where the model attempts to distinguish keystroke feature sequences from genuine users from those of `impostors'. In this way, the ratio of inaccurately and accurately labeled password inputs can be analyzed. The result showed that, after tuning of the hyperparameters, the XGBoost yielded Equal Error Rates (EER) at best 0.31 percentage points better than the SVM used in the original study of the database at 11.52%, and a highest AUC of 0.9792. The scores achieved by this thesis are however significantly worse than a lot of others in the same field, but so were the results in the original study. The results varied greatly depending on user tested. These results suggests that XGBoost may be a useful tool, that should be tuned, but that a better dataset should be used to sufficiently benchmark the tool. Also, the quality of the model is greatly affected by variance among the users. For future research purposes, one should make sure that the database used is of good quality. To create a security system utilizing XGBoost, one should be careful of the setting and quality requirements when collecting training data

  • 135.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Chen, Juan
    Microsoft Research.
    Swamy, Nikhil
    Microsoft Research.
    Verified Stateful Programs with Substructural State and Hoare Types2011In: Proc. 5th ACM Workshop on Programming Languages Meets Program Verification, New York: ACM Press , 2011, p. 15-26Conference paper (Refereed)
  • 136.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Crafa, Silvia
    Proc. Combined 21st International Workshop on Expressiveness in Concurrency (EXPRESS 2014) and 11th Workshop on Structural Operational Semantics (SOS 2014)2014Conference proceedings (editor) (Refereed)
  • 137.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Dal Lago, Ugo
    Gordon, Andrew D.
    Szymczak, Marcin
    A Lambda-Calculus Foundation for Universal Probabilistic Programming2016In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 51, no 9, p. 33-46Article in journal (Refereed)
  • 138.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gordon, Andrew D.
    Microsoft Research, Cambridge.
    Greenberg, Michael
    University of Pennsylvania.
    Margetson, James
    Microsoft Research, Cambridge.
    van Gael, Jurgen
    Microsoft FUSE Labs, Cambridge.
    Measure transformer semantics for Bayesian machine learning2013In: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 9, no 3, p. 11-Article in journal (Refereed)
    Abstract [en]

    The Bayesian approach to machine learning amounts to computing posterior distributions of random variables from a probabilistic model of how the variables are related (that is, a prior distribution) and a set of observations of variables. There is a trend in machine learning towards expressing Bayesian models as probabilistic programs. As a foundation for this kind of programming, we propose a core functional calculus with primitives for sampling prior distributions and observing variables. We define measure-transformer combinators inspired by theorems in measure theory, and use these to give a rigorous semantics to our core calculus. The original features of our semantics include its support for discrete, continuous, and hybrid measures, and, in particular, for observations of zero-probability events. We compile our core language to a small imperative language that is processed by an existing inference engine for factor graphs, which are data structures that enable many efficient inference algorithms. This allows efficient approximate inference of posterior marginal distributions, treating thousands of observations per second for large instances of realistic models.

  • 139.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gordon, Andrew D.
    Ouyang, Long
    Russo, Claudio
    Scibior, Adam
    Szymczak, Marcin
    Fabular: Regression formulas as probabilistic programming2016In: Proc. 43rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New York: ACM Press, 2016, p. 271-283Conference paper (Refereed)
  • 140.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gutkovas, Ramunas
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Victor, Björn
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Åman Pohjola, Johannes
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    A Sorted Semantic Framework for Applied Process Calculi2016In: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 12, no 1, p. 1-49, article id 8Article in journal (Refereed)
    Abstract [en]

    Applied process calculi include advanced programming constructs such as type systems, communication with pattern matching, encryption primitives, concurrent constraints, nondeterminism, process creation, and dynamic connection topologies. Several such formalisms, e.g. the applied pi calculus, are extensions of the the pi-calculus; a growing number is geared towards particular applications or computational paradigms.

    Our goal is a unified framework to represent different process calculi and notions of computation. To this end, we extend our previous work on psi-calculi with novel abstract patterns and pattern matching, and add sorts to the data term language, giving sufficient criteria for subject reduction to hold. Our framework can directly represent several existing process calculi; the resulting transition systems are isomorphic to the originals up to strong bisimulation. We also demonstrate different notions of computation on data terms, including cryptographic primitives and a lambda-calculus with erratic choice. Finally, we prove standard congruence and structural properties of bisimulation; the proof has been machine-checked using Nominal Isabelle in the case of a single name sort.

  • 141.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gutkovas, Ramunas
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Victor, Björn
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Åman Pohjola, Johannes
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    A Sorted Semantic Framework for Applied Process Calculi (extended abstract)2014In: Trustworthy Global Computing: TGC 2013, Springer Berlin/Heidelberg, 2014, p. 103-118Conference paper (Refereed)
    Abstract [en]

    Applied process calculi include advanced programming constructs such as type systems, communication with pattern matching, encryption primitives, concurrent constraints, nondeterminism, process creation, and dynamic connection topologies. Several such formalisms, e.g. the applied pi calculus,  are extensions of the the pi-calculus; a growing number is geared towards particular applications or computational paradigms.

    Our goal is a unified framework to represent different process calculi and notions of computation. To this end, we extend our previous work on psi-calculi with novel abstract patterns and pattern matching, and add sorts to the data term language, giving sufficient criteria for subject reduction to hold. Our framework can accommodate several existing process calculi; the resulting transition systems are isomorphic to the originals up to strong bisimulation. We also demonstrate  different notions of computation on data terms, including cryptographic primitives and a lambda-calculus with erratic choice. Substantial parts of the meta-theory of sorted psi-calculi have been machine-checked using Nominal Isabelle.

  • 142.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gutkovas, Ramunas
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Rodhe, Ioana
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Victor, Björn
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    A Parametric Tool for Applied Process Calculi2013In: 13th International Conference on Application of Concurrency to System Design (ACSD 2013), IEEE Computer Society, 2013, p. 180-185Conference paper (Refereed)
    Abstract [en]

    High-level formalisms for concurrency are often defined as extensions of the the pi-calculus; a growing number is geared towards particular applications or computational paradigms. Psi-calculi is a parametric framework that can accommodate a wide spectrum of such calculi. It allows the definition of process calculi that extend the pi-calculus with arbitrary data, logic and logical assertions. All such psi calculi inherit machine-checked proofs of the meta-theory such as compositionality and bisimulation congruence.

    We present a generic tool for analysing processes from any psi calculus instance, and for implementing new instances with the help of a supporting library. The tool implements symbolic execution and bisimulation algorithms for both unicast and wireless broadcast communication. We illustrate the tool by examples from pi-calculus and the area of wireless sensor networks.

  • 143.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Gutkovas, Ramunas
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Rodhe, Ioana
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Victor, Björn
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    The Psi-Calculi Workbench: A Generic Tool for Applied Process Calculi2015In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 14, no 1, article id 9Article in journal (Refereed)
    Abstract [en]

    Psi-calculi is a parametric framework for extensions of the pi-calculus with arbitrary data and logic. All instances of the framework inherit machine-checked proofs of the metatheory such as compositionality and bisimulation congruence. We present a generic analysis tool for psi-calculus instances, enabling symbolic execution and (bi)simulation checking for both unicast and broadcast communication. The tool also provides a library for implementing new psi-calculus instances. We provide examples from traditional communication protocols and wireless sensor networks. We also describe the theoretical foundations of the tool, including an improved symbolic operational semantics, with additional support for scoped broadcast communication.

  • 144.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Huang, Shuqin
    Johansson, Magnus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Raabjerg, Palle
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Victor, Björn
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Åman Pohjola, Johannes
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Broadcast psi-calculi with an application to wireless protocols2015In: Software and Systems Modeling, ISSN 1619-1366, E-ISSN 1619-1374, Vol. 14, no 1, p. 201-216Article in journal (Refereed)
    Abstract [en]

    Psi-calculi is a parametric framework for extensions of the pi-calculus, with arbitrary data structures and logical assertions for facts about data. In this paper we add primitives for broadcast communication in order to model wireless protocols. The additions preserve the purity of the psi-calculi semantics, and we formally prove the standard congruence and structural properties of bisimilarity. We demonstrate the expressive power of broadcast psi-calculi by modelling the wireless ad-hoc routing protocol LUNAR and verifying a basic reachability property.

  • 145.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Huang, Shuqin
    Peking University, China.
    Johansson, Magnus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Raabjerg, Palle
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Victor, Björn
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Åman Pohjola, Johannes
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parrow, Joachim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Broadcast Psi-calculi with an Application to Wireless Protocols2011In: Software Engineering and Formal Methods: SEFM 2011, Springer Berlin/Heidelberg, 2011, p. 74-89Conference paper (Refereed)
    Abstract [en]

    Psi-calculi is a parametric framework for extensions of the pi-calculus, with arbitrary data structures and logical assertions for facts about data. In this paper we add primitives for broadcast communication % to the psi-calculi framework. in order to model wireless protocols. The additions preserve the purity of the psi-calculi semantics, and we formally prove the standard congruence and structural properties of bisimilarity. We demonstrate the expressive power of broadcast psi-calculi by modelling the wireless ad-hoc routing protocol LUNAR and verifying a basic reachability property.

  • 146.
    Borgström, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Luttik, BasEindhoven University of Technology.
    Proceedings Combined 20th International Workshop on Expressiveness in Concurrency and 10th Workshop on Structural Operational Semantics2013Conference proceedings (editor) (Refereed)
    Abstract [en]

    This volume contains the proceedings of the Combined 20th International Workshop on Expressiveness in Concurrency and the 10th Workshop on Structural Operational Semantics (EXPRESS/SOS 2013) which was held on 26th August, 2013 in Buenos Aires, Argentina, as an affiliated workshop of CONCUR 2013, the 24th International Conference on Concurrency Theory. The EXPRESS workshops aim at bringing together researchers interested in the expressiveness of various formal systems and semantic notions, particularly in the field of concurrency. Their focus has traditionally been on the comparison between programming concepts (such as concurrent, functional, imperative, logic and object-oriented programming) and between mathematical models of computation (such as process algebras, Petri nets, event structures, modal logics, and rewrite systems) on the basis of their relative expressive power. The EXPRESS workshop series has run successfully since 1994 and over the years this focus has become broadly construed. The SOS workshops aim at being a forum for researchers, students and practitioners interested in new developments, and directions for future investigation, in the field of structural operational semantics. One of the specific goals of the SOS workshop series is to establish synergies between the concurrency and programming language communities working on the theory and practice of SOS. Reports on applications of SOS to other fields are also most welcome, including: modelling and analysis of biological systems, security of computer systems programming, modelling and analysis of embedded systems, specification of middle-ware and coordination languages, programming language semantics and implementation, static analysis software and hardware verification, and semantics for domain-specific languages and model-based engineering.

  • 147. Bothorel, Cecile
    et al.
    Cruz, Juan David
    Magnani, Matteo
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Micenkova, Barbora
    Clustering attributed graphs: models, measures and methods2015In: Network Science, ISSN 2050-1242, Vol. 3, no 3, p. 408-444Article in journal (Refereed)
    Abstract [en]

    Clustering a graph, i.e., assigning its nodes to groups, is an important operation whose best known application is the discovery of communities in social networks. Graph clustering and community detection have traditionally focused on graphs without attributes, with the notable exception of edge weights. However, these models only provide a partial representation of real social systems, that are thus often described using node attributes, representing features of the actors, and edge attributes, representing different kinds of relationships among them. We refer to these models as attributed graphs. Consequently, existing graph clustering methods have been recently extended to deal with node and edge attributes. This article is a literature survey on this topic, organizing, and presenting recent research results in a uniform way, characterizing the main existing clustering methods and highlighting their conceptual differences. We also cover the important topic of clustering evaluation and identify current open problems.

  • 148. Boudeville, Olivier
    et al.
    Cesarini, Francesco
    Chechina, Natalia
    Lundin, Kenneth
    Papaspyrou, Nikolaos
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Thompson, Simon
    Trinder, Phil
    Wiger, Ulf
    RELEASE: A high-level paradigm for reliable large-scale server software2013In: Trends in Functional Programming, Springer Berlin/Heidelberg, 2013, p. 263-278Conference paper (Refereed)
  • 149.
    Brandauer, Stephan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Structured Data2018Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    References are a programming language construct that lets a programmer access a datum invariant of its location.

    References permit aliasing -- several references to the same object, effectively making a single object accessible through different names (or paths). Aliasing, especially of mutable data, is both a blessing and a curse: when used correctly, it can make a programmer's life easier; when used incorrectly, for example through accidental aliases that the programmer is unaware of, aliasing can lead to hard to find bugs, and hard to verify programs.

    Aliases allow us to build efficient data structures by connecting objects together, making them immediately reachable. Aliases are at the heart of many useful programming idioms. But with great power comes great responsibility: unless a programmer carefully manages aliases in a program, aliases propagate changes and make parts of a program's memory change seemingly for no reason. Additionally, such bugs are very easy to make but very hard to track down.

    This thesis presents an overview of techniques for controlling how, when and if data can be aliased, as well as how and if data can be mutated. Additionally, it presents three different projects aimed at conserving the blessings, but reducing the curses. The first project is disjointness domains, a type system for expressing intended aliasing in a fine-grained manner so that aliasing will not be unexpected; the second project is Spencer, a tool to flexibly and precisely analyse the use of aliasing in programs to improve our understanding of how aliasing of mutable data is used in practise; and the third project is c flat, an approach for implementing high-level collection data structures using a richer reference construct that reduces aliasing problems but still retains many of aliasing's benefits.

    List of papers
    1. Disjointness Domains for Fine-Grained Aliasing
    Open this publication in new window or tab >>Disjointness Domains for Fine-Grained Aliasing
    2015 (English)Conference paper, Published paper (Refereed)
    Abstract [en]

    Aliasing is crucial for supporting useful implementation patterns, but it makes reasoning about programs difficult. To deal with this problem, numerous type-based aliasing control mechanisms have been proposed, expressing properties such as uniqueness. Uniqueness, however, is black-and-white: either a reference is unique or it can be arbitrarily aliased; and global: excluding aliases throughout the entire system, making code brittle to changing requirements. Disjointness domains, a new approach to alias control, address this problem by enabling more graduations between uniqueness and arbitrary reference sharing. They allow expressing aliasing constraints local to a certain set of variables (either stack variables or fields) for instance that no aliasing occurs between variables within some set of variables but between such sets or the opposite, that aliasing occurs within that set but not between different sets. A hierarchy of disjointness domains controls the flow of references through a program, helping the programmer reason about disjointness and enforce local alias invariants. The resulting system supports fine-grained control of aliasing between both variables and objects, making aliasing explicit to programmers, compilers, and tooling. This paper presents a formal account of disjointness domains along with examples. Disjointness domains provide novel means of expressing may-alias kinds of constraints, which may prove useful in compiler optimisation and verification.

    Series
    ACM SIGPLAN NOTICES, ISSN 0362-1340
    Keywords
    Design; Theory; Aliasing; mutable state; type systems; uniqueness; linear types
    National Category
    Electrical Engineering, Electronic Engineering, Information Engineering
    Research subject
    Computer Science
    Identifiers
    urn:nbn:se:uu:diva-268747 (URN)10.1145/2814270.2814280 (DOI)000367256500051 ()
    Conference
    ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA)
    Available from: 2015-12-09 Created: 2015-12-09 Last updated: 2018-11-27Bibliographically approved
    2. Spencer: Interactive Heap Analysis for the Masses
    Open this publication in new window or tab >>Spencer: Interactive Heap Analysis for the Masses
    2017 (English)In: 2017 IEEE/ACM 14th International Conference on Mining Software Repositories (MSR 2017), IEEE, 2017, no 14, p. 113-123Conference paper, Published paper (Refereed)
    Abstract [en]

    Programming language-design and run-time-implementation require detailed knowledge about the programs that users want to implement. Acquiring this knowledge is hard, and there is little tool support to effectively estimate whether a proposed tradeoff actually makes sense in the context of real world applications. Ideally, knowledge about behaviour of "typical" programs is 1) easily obtainable, 2) easily reproducible, and 3) easily sharable. We present Spencer, an open source web service and API framework for dynamic analysis of a continuously growing set of traces of standard program corpora. Users do not obtain traces on their own, but can instead send queries to the web service that will be executed on a set of program traces. Queries are built in terms of a set of query combinators that present a high level interface for working with trace data. Since the framework is high level, and there is a hosted collection of recorded traces, queries are easy to implement. Since the data sets are shared by the research community, results are reproducible. Since the actual queries run on one (or many) servers that provide analysis as a service, obtaining results is possible on commodity hardware. Data in Spencer is meant to be obtained once, and analysed often, making the overhead of data collection mostly irrelevant. This allows Spencer to collect more data than traditional tracing tools can afford within their performance budget. Results in Spencer are cached, making complicated analyses that build on cached primitive queries speedy.

    Place, publisher, year, edition, pages
    IEEE, 2017
    Series
    IEEE International Working Conference on Mining Software Repositories, E-ISSN 2160-1852
    Keywords
    tracing, dynamic analysis, heap analysis, tracing
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-334818 (URN)10.1109/MSR.2017.35 (DOI)000425917100013 ()978-1-5386-1544-7 (ISBN)
    Conference
    IEEE/ACM 14th International Conference on Mining Software Repositories (MSR), Buenos Aires, Argentina, May 20-21, 2017
    Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2018-11-27Bibliographically approved
    3. Mining for Safety using Interactive Trace Analysis
    Open this publication in new window or tab >>Mining for Safety using Interactive Trace Analysis
    2017 (English)In: Pre-Proceedings - Fifteenth International Workshop on Quantitative Aspects of Programming Languages and Systems, 2017, no 15, article id 14Conference paper, Published paper (Refereed)
    Keywords
    tracing, dynamic analysis, heap analysis, tracing
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-334817 (URN)
    Conference
    Fifteenth International Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL)
    Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2018-11-27Bibliographically approved
    4. C♭: A New Modular Approach to Implementing Efficient and Tunable Collections
    Open this publication in new window or tab >>C♭: A New Modular Approach to Implementing Efficient and Tunable Collections
    2018 (English)In: Proceedings of the 2018 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward! 2018), ACM , 2018, p. 57-71Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    ACM, 2018
    Keywords
    data structure design, domain specific language, performance tuning
    National Category
    Computer Sciences
    Research subject
    Computer Science
    Identifiers
    urn:nbn:se:uu:diva-366812 (URN)10.1145/3276954.3276956 (DOI)000455805700005 ()
    Conference
    SPLASH 2018 - Systems, Programming, Languages and Applications: Software for Humanity, Boston, 4-9 November, 2018
    Projects
    UPMARC2012-04867 Structured Aliasing
    Funder
    Swedish Research Council, 2012-04967
    Available from: 2018-11-26 Created: 2018-11-26 Last updated: 2019-02-04Bibliographically approved
  • 150.
    Brandauer, Stephan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Castegren, Elias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Clarke, Dave
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Fernandez-Reyes, Kiko
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Johnsen, Einar Broch
    Univ Oslo, Dept Informat, N-0316 Oslo, Norway..
    Pun, Ka I.
    Univ Oslo, Dept Informat, N-0316 Oslo, Norway..
    Tarifa, S. Lizeth Tapia
    Univ Oslo, Dept Informat, N-0316 Oslo, Norway..
    Wrigstad, Tobias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Yang, Albert Mingkun
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parallel Objects for Multicores: A Glimpse at the Parallel Language ENCORE2015In: Formal Methods for Multicore Programming, 2015, p. 1-56Conference paper (Refereed)
    Abstract [en]

    The age of multi-core computers is upon us, yet current programming languages, typically designed for single-core computers and adapted post hoc for multi-cores, remain tied to the constraints of a sequential mindset and are thus in many ways inadequate. New programming language designs are required that break away from this old-fashioned mindset. To address this need, we have been developing a new programming language called Encore, in the context of the European Project UpScale. The paper presents a motivation for the Encore language, examples of its main constructs, several larger programs, a formalisation of its core, and a discussion of some future directions our work will take. The work is ongoing and we started more or less from scratch. That means that a lot of work has to be done, but also that we need not be tied to decisions made for sequential language designs. Any design decision can be made in favour of good performance and scalability. For this reason, Encore offers an interesting platform for future exploration into object-oriented parallel programming.

1234567 101 - 150 of 833
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf