uu.seUppsala universitets publikasjoner
Endre søk
Begrens søket
45678910 301 - 350 of 2118
RefereraExporteraLink til resultatlisten
Permanent link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Treff pr side
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Forfatter A-Ø
  • Forfatter Ø-A
  • Tittel A-Ø
  • Tittel Ø-A
  • Type publikasjon A-Ø
  • Type publikasjon Ø-A
  • Eldste først
  • Nyeste først
  • Skapad (Eldste først)
  • Skapad (Nyeste først)
  • Senast uppdaterad (Eldste først)
  • Senast uppdaterad (Nyeste først)
  • Disputationsdatum (tidligste først)
  • Disputationsdatum (siste først)
  • Standard (Relevans)
  • Forfatter A-Ø
  • Forfatter Ø-A
  • Tittel A-Ø
  • Tittel Ø-A
  • Type publikasjon A-Ø
  • Type publikasjon Ø-A
  • Eldste først
  • Nyeste først
  • Skapad (Eldste først)
  • Skapad (Nyeste først)
  • Senast uppdaterad (Eldste først)
  • Senast uppdaterad (Nyeste først)
  • Disputationsdatum (tidligste først)
  • Disputationsdatum (siste først)
Merk
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 301.
    Berglund, Anders
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Lister, Raymond
    Introductory programming and the didactic triangle2010Inngår i: Australian Computer Science Communications, ISSN 0157-3055, Vol. 32, nr 2, s. 35-44Artikkel i tidsskrift (Fagfellevurdert)
  • 302.
    Berglund, Anders
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Pears, Arnold
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Alagla, Ali
    Al Baha University, Saudi Arabia.
    Salih, Nimir
    Al Baha University, Saudi Arabia.
    Shenify, Mohamed
    Al Baha University, Saudi Arabia.
    Learning to develop learning and teaching of CS: a collaborative example2014Inngår i: Proc. 2nd International Conference on Learning and Teaching in Computing and Engineering, Los Alamitos, CA: IEEE Computer Society, 2014, s. 147-148Konferansepaper (Fagfellevurdert)
    Abstract [en]

    Developing and improving teaching and learning in computer science is a complex task. One of the most significant challenges involves encouraging students, teachers and the formal university structures to all move in the same direction, for example to embrace the ideas of Scholarship of Teaching and Learning (SoTL). Much of the difficulty can be found in the fact that the intrinsic nature of SoTL implies that teaching and learning should be researched and critically examined. This in turn demands a development of underlying staff and organisational attitudes. As a consequence, the ways to relate to the students, the subject area, the teaching and our colleagues must scrutinised, with the intent of finding new teaching and learning forms. This contribution discusses an on-going four year project, ABoLT (Al Baha optimising Teaching and Learning), in which Uppsala University (UU) in Sweden and Al Baha University (ABU) in Saudi Arabia collaborate on developing computer science (CS) education at ABU, based in the ideas of SoTL to the benefit of both partners. In the project, ABU will renew its teaching in CS and, at the same time, initialise, formulate and conduct research in computing education, as a means to understand and improve its own teaching and the learning of its students.

  • 303.
    Berglund, Anders
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Thota, Neena
    A glimpse into the cultural situatedness of computer science: Some insights from a pilot study2014Inngår i: Proc. 2nd International Conference on Learning and Teaching in Computing and Engineering, Los Alamitos, CA: IEEE Computer Society, 2014, s. 92-99Konferansepaper (Fagfellevurdert)
    Abstract [en]

    To what extent is students' understanding of computer science culturally situated? This, possibly philosophical question, has come to the surface at Uppsala University, Uppsala, Sweden, where many Chinese students study computer science together with the local students. We did an exploratory study using email interviews to see if our intuitions could be relied on. We collected data from Chinese students studying in master programs and analysed the data using a phenomenographic perspective. A complex intertwined relationship between the content of their learning (the WHAT) the ways in which they went about studying (the HOW), the aims of their studies (the WHY), and the competencies developed from the intercultural context they studied in (the WHERE) was observed. In this paper we offer some insights from the results of the pilot study and discuss how they have shaped our on-going study in the field.

  • 304.
    Berglund, Anders
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Thota, Neena
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    How do master level students in Computer Science perceive plagiarism?2011Inngår i: Proc. 2nd International Conference on Computer Science Education: Innovation and Technology, Singapore: Global Science and Technology Forum , 2011, s. 90-95Konferansepaper (Fagfellevurdert)
    Abstract [en]

    Plagiarism is a serious problem in computer science.This paper reports the analyses of data about plagiarism that wasgathered from master level students in computing. We haveidentified how students perceive plagiarism, how they choose torespond when faced by a scenario involving plagiarism, and whatdrives them to take a particular stance or adopt an action. Thedata-driven analyses show complex understanding of plagiarismand a range of motives that could lead students to plagiarize. Wehave found discrepancies between how students understandplagiarism and how they argue they would act when facing adilemma involving plagiarism. The implications of theseperceptions and motives for computer science educators arediscussed. A number of questions for discussion and furtherinvestigation are raised.

  • 305.
    Berglund, Anders
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Thota, Neena
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Man, Yemao
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
    The Sino–Swedish Master Programme in Computer Science and Software Engineering: Chinese students' experiences2013Inngår i: Collaborative Academic Programs as a Contribution to Developing Nations: FICAP-1 Proceedings / [ed] Justine Hitchcock, Leo Hitchcock, Petteri Kaskenpalo, Boca Raton, Fl, USA: BrownWalker Press, 2013, s. 37-45Kapittel i bok, del av antologi (Fagfellevurdert)
    Abstract [en]

    Internationalisation in higher education has led to the emergence of joint educational programmes between universities. In this paper, we document the Sino-Swedish master programme in computer science and software engineering, taught jointly by a Swedish and a Chinese university, from the perspective of the Swedish partner, Uppsala University. We also describe what the programme means to the Chinese students studying in Sweden. For this purpose, we interviewed the Chinese students and asked questions about their experiences of learning and living in Sweden. The students identified the differences in the experiences in Sweden from that of learning and living in China and the challenges that they faced in Sweden. The students also offered recommendations for improving their learning experiences. We discuss the benefits and challenges of joint education programs.

  • 306.
    Berglund, Anders
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Wiggberg, MattiasUppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Proc. 6th Baltic Sea Conference on Computing Education Research: Koli Calling2007Konferanseproceedings (Annet vitenskapelig)
  • 307. Bernáld, Helena
    et al.
    Cajander, Åsa
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Bildanalys och människa-datorinteraktion.
    Daniels, Mats
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Laxer, Cary
    Reasoning about the value of cultural awareness in international collaboration2011Inngår i: Journal of Applied Computing and Information Technology, ISSN 2230-4398, Vol. 15, nr 1:I2Artikkel i tidsskrift (Fagfellevurdert)
  • 308.
    Bertholds, Alexander
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
    Larsson, Emil
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
    An intelligent search for feature interactions using Restricted Boltzmann Machines2013Independent thesis Advanced level (professional degree), 20 poäng / 30 hpOppgave
    Abstract [en]

    Klarna uses a logistic regression to estimate the probability that an e-store customer will default on its given credit. The logistic regression is a linear statistical model which cannot detect non-linearities in the data. The aim of this project has been to develop a program which can be used to find suitable non-linear interaction-variables. This can be achieved using a Restricted Boltzmann Machine, an unsupervised neural network, whose hidden nodes can be used to model the distribution of the data. By using the hidden nodes as new variables in the logistic regression it is possible to see which nodes that have the greatest impact on the probability of default estimates. The contents of the hidden nodes, corresponding to different parts of the data distribution, can be used to find suitable interaction-variables which will allow the modelling of non-linearities.

    It was possible to find the data distribution using the Restricted Boltzmann Machine and adding its hidden nodes to the logistic regression improved the model's ability to predict the probability of default. The hidden nodes could be used to create interaction-variables which improve Klarna's internal models used for credit risk estimates.

  • 309.
    Bevemyr, Johan
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för ADB och datalogi.
    Data-parallel Implementation of Prolog1996Doktoravhandling, med artikler (Annet vitenskapelig)
  • 310.
    Bhat, Sooraj
    et al.
    Georgia Institute of Technology.
    Borgström, Johannes
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Gordon, Andrew D.
    Microsoft Research, Cambridge.
    Russo, Claudio
    Microsoft Research, Cambridge.
    Deriving Probability Density Functions from Probabilistic Functional Programs2013Inngår i: 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, s. 508-522Konferansepaper (Fagfellevurdert)
    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. 

  • 311. Bhat, Sooraj
    et al.
    Borgström, Johannes
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Gordon, Andrew D.
    Russo, Claudio
    Deriving Probability Density Functions from Probabilistic Functional Programs2017Inngår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 13, nr 2, artikkel-id 16Artikkel i tidsskrift (Fagfellevurdert)
    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.

  • 312.
    Bjurefors, Fredrik
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datorteknik. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Measurements in opportunistic networks2012Licentiatavhandling, med artikler (Annet vitenskapelig)
    Abstract [en]

    Opportunistic networks are a subset of delay tolerant networks where the contacts are unscheduled. Such networks can be formed ad hoc by wireless devices, such as mobile phones and laptops. In this work we use a data-centric architecture for opportunistic networks to evaluate data dissemination overhead, congestion in nodes' buffer, and the impact of transfer ordering. Dissemination brings an overhead since data is replicated to be spread in the network and overhead leads to congestion, i.e., overloaded buffers.

    We develop and implement an emulation testbed to experimentally evaluate properties of opportunistic networks. We evaluate the repeatability of experiments in the emulated testbed that is based on virtual computers. We show that the timing variations are on the order of milliseconds.

    The testbed was used to investigate overhead in data dissemination, congestion avoidance, and transfer ordering in opportunistic networks. We show that the overhead can be reduced by informing other nodes in the network about what data a node is carrying. Congestion avoidance was evaluated in terms of buffer management, since that is the available tool in an opportunistic network, to handle congestion. It was shown that replication information of data objects in the buffer yields the best results. We show that in a data-centric architecture were each data item is valued differently, transfer ordering is important to achieve delivery of the most valued data.

  • 313.
    Bjurefors, Fredrik
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datorteknik. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Opportunistic Networking: Congestion, Transfer Ordering and Resilience2014Doktoravhandling, med artikler (Annet vitenskapelig)
    Abstract [en]

    Opportunistic networks are constructed by devices carried by people and vehicles. The devices use short range radio to communicate. Since the network is mobile and often sparse in terms of node contacts, nodes store messages in their buffers, carrying them, and forwarding them upon node encounters. This form of communication leads to a set of challenging issues that we investigate: congestion, transfer ordering, and resilience.

    Congestion occurs in opportunistic networks when a node's buffers becomes full. To be able to receive new messages, old messages have to be evicted. We show that buffer eviction strategies based on replication statistics perform better than strategies that evict messages based on the content of the message.

    We show that transfer ordering has a significant impact on the dissemination of messages during time limited contacts. We find that transfer strategies satisfying global requests yield a higher delivery ratio but a longer delay for the most requested data compared to satisfying the neighboring node's requests.

    Finally, we assess the resilience of opportunistic networks by simulating different types of attacks. Instead of enumerating all possible attack combinations, which would lead to exhaustive evaluations, we introduce a method that use heuristics to approximate the extreme outcomes an attack can have. The method yields a lower and upper bound for the evaluated metric over the different realizations of the attack. We show that some types of attacks are harder to predict the outcome of and other attacks may vary in the impact of the attack due to the properties of the attack, the forwarding protocol, and the mobility pattern.

    Delarbeid
    1. Haggle Testbed: a Testbed for Opportunistic Networks
    Åpne denne publikasjonen i ny fane eller vindu >>Haggle Testbed: a Testbed for Opportunistic Networks
    2011 (engelsk)Inngår i: In Proceedings of the 7th Swedish National Computer Networking Workshop, 2011Konferansepaper, Publicerat paper (Fagfellevurdert)
    Identifikatorer
    urn:nbn:se:uu:diva-155530 (URN)
    Prosjekter
    Haggle
    Tilgjengelig fra: 2011-06-23 Laget: 2011-06-23 Sist oppdatert: 2014-06-30
    2. Congestion Avoidance in a Data-Centric Opportunistic Network
    Åpne denne publikasjonen i ny fane eller vindu >>Congestion Avoidance in a Data-Centric Opportunistic Network
    2011 (engelsk)Inngår i: Proceedings of the 2011 ACM SIGCOMM Workshop on Information-Centric Networking (ICN-2011), 2011Konferansepaper, Publicerat paper (Fagfellevurdert)
    Identifikatorer
    urn:nbn:se:uu:diva-155528 (URN)
    Prosjekter
    ResumeNet
    Tilgjengelig fra: 2011-06-23 Laget: 2011-06-23 Sist oppdatert: 2014-06-30
    3. Making the Most of Your Contacts: Transfer Ordering in Data-Centric Opportunistic Networks
    Åpne denne publikasjonen i ny fane eller vindu >>Making the Most of Your Contacts: Transfer Ordering in Data-Centric Opportunistic Networks
    Vise andre…
    2012 (engelsk)Inngår i: Proceedings of the 2012 ACM MobiOpp Workshop on Mobile Opportunistic Networks, Zürich: ACM Press, 2012Konferansepaper, Publicerat paper (Fagfellevurdert)
    Abstract [en]

    Opportunistic networks use unpredictable and time-limited con- tacts to disseminate data. Therefore, it is important that protocols transfer useful data when contacts do occur. Specifically, in a data- centric network, nodes benefit from receiving data relevant to their interests. To this end, we study five strategies to select and order the data to be exchanged during a limited contact, and measure their ability to promptly and efficiently deliver highly relevant data.

    Our trace-driven experiments on an emulation testbed suggest that nodes benefit in the short-term from ordering data transfers to satisfy local interests. However, this can lead to suboptimal longterm system performance. Restricting sharing based on matching nodes’ interests can lead to segregation of the network, and limit useful dissemination of data. A non-local understanding of other nodes’ interests is necessary to effectively move data across the network. If ordering of transfers for data relevance is not explicitly considered performance is comparable to random, which limits the delivery of individually relevant data. 

    sted, utgiver, år, opplag, sider
    Zürich: ACM Press, 2012
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-171587 (URN)
    Konferanse
    ACM MobiOpp
    Prosjekter
    ResumeNet
    Tilgjengelig fra: 2012-03-22 Laget: 2012-03-22 Sist oppdatert: 2014-06-30
    4. Resilience and Opportunistic Forwarding: Beyond Average Value Analysis
    Åpne denne publikasjonen i ny fane eller vindu >>Resilience and Opportunistic Forwarding: Beyond Average Value Analysis
    Vise andre…
    2014 (engelsk)Inngår i: Computer Communications, ISSN 0140-3664, E-ISSN 1873-703X, Vol. 48, nr SI, s. 111-120Artikkel i tidsskrift (Fagfellevurdert) Published
    Abstract [en]

    Opportunistic networks are systems with highly distributed operation, relying on the altruistic cooperation of highly heterogeneous, and not always software and hardware-compatible, user nodes. Moreover, the absence of central coordination and control makes them vulnerable to malicious attacks. In this paper, we study the resilience of popular forwarding protocols to a representative set of challenges to their normal operation. These include jamming locally disturbing message transfer between nodes, hardware/software failures and incompatibility among nodes rendering contact opportunities useless, and free-riding phenomena. We first formulate and promote the metric envelope concept as a tool for assessing the resilience of opportunistic forwarding schemes. Metric envelopes depart from the standard practice of average value analysis and explicitly account for the differentiated challenge impact due to node heterogeneity (device capabilities, mobility) and attackers’ intelligence. We then propose heuristics to generate worst- and best-case challenge realization scenarios and approximate the lower and upper bounds of the metric envelopes. Finally, we demonstrate the methodology in assessing the resilience of three popular forwarding protocols in the presence of the three challenges, and under a comprehensive range of mobility patterns. The metric envelope approach provides better insights into the level of protection path diversity and message replication provide against different challenges, and enables more informed choices in opportunistic forwarding when network resilience becomes important.

    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-222822 (URN)10.1016/j.comcom.2014.04.004 (DOI)000337883200010 ()
    Prosjekter
    ResumeNet, WISENET
    Forskningsfinansiär
    EU, FP7, Seventh Framework Programme, FP7-224619
    Merknad

    Special Issue

    Tilgjengelig fra: 2014-04-17 Laget: 2014-04-14 Sist oppdatert: 2017-12-05bibliografisk kontrollert
  • 314.
    Björdal, Gustav
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Flener, Pierre
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Pearson, Justin
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Generating compound moves in local search by hybridisation with complete search2019Inngår i: Integration of Constraint Programming, Artificial Intelligence, and Operations Research / [ed] L.-M. Rousseau and K. Stergiou, Springer, 2019, Vol. 11494, s. 95-111Konferansepaper (Fagfellevurdert)
    Abstract [en]

    A black-box local-search backend to a solving-technology-independent modelling language, such as MiniZinc, automatically infers from the structure of a declarative model for a satisfaction or optimisation problem a combination of a neighbourhood, heuristic, and meta-heuristic. These ingredients are then provided to a local-search solver, but are manually designed in a handcrafted local-search algorithm. However, such a backend can perform poorly due to model structure that is inappropriate for local search, for example when it considers moves modifying only variables that represent auxiliary information. Towards overcoming such inefficiency, we propose compound-move generation, an extension to local-search solvers that uses a complete-search solver in order to augment moves modifying non-auxiliary variables so that they also modify auxiliary ones. Since compound-move generation is intended to be applied to such models, we discuss how to identify them.

    We present several refinements of compound-move generation and show its very positive impact on several third-party models. This helps reduce the unavoidable gap between black-box local search and local-search algorithms crafted by experts.

  • 315.
    Björdal, Gustav
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Flener, Pierre
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Pearson, Justin
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Stuckey, Peter J.
    Faculty of Information Technology, Monash University, Melbourne, Australia.
    Exploring declarative local-search neighbourhoods with constraint programming2019Inngår i: Principles and Practice of Constraint Programming / [ed] Thomas Schiex and Simon de Givry, Switzerland: Springer, 2019, Vol. 11802, s. 37-53Konferansepaper (Fagfellevurdert)
    Abstract [en]

    Using constraint programming (CP) to explore a local-search neighbourhood was first tried in the mid 1990s. The advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a CP model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. That research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of CP-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a CP model of the neighbourhood. This enables us to lift any CP solver into a local-search backend to MiniZinc. Our prototype is competitive with CP, CBLS, and LNS backends to MiniZinc.

  • 316.
    Björdal, Gustav
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Flener, Pierre
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Pearson, Justin
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Stuckey, Peter J.
    Tack, Guido
    Declarative local-search neighbourhoods in MiniZinc2018Inngår i: PROCEEDINGS OF THE 2018 IEEE 30TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI), IEEE Computer Society, 2018, s. 98-105Konferansepaper (Fagfellevurdert)
    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.

  • 317.
    Björdal, Gustav
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Monette, Jean-Noël
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Flener, Pierre
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Pearson, Justin
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    A constraint-based local search backend for MiniZinc2015Inngår i: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 20, nr 3, s. 325-345Artikkel i tidsskrift (Fagfellevurdert)
  • 318.
    Björklund, H
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. SERGEI VOROBYOV.
    Petersson, V
    Vorobyov, S
    Experiments with Iterative Improvement Algorithms on Completely Unimodal Hypercubes2001Inngår i: Information Technology/Uppsala University TR 2001-017Rapport (Annet vitenskapelig)
  • 319.
    Björklund, Henrik
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datalogi. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Combinatorial Optimization for Infinite Games on Graphs2005Doktoravhandling, med artikler (Annet vitenskapelig)
    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.

    Delarbeid
    1. A discrete subexponential algorithm for parity games
    Åpne denne publikasjonen i ny fane eller vindu >>A discrete subexponential algorithm for parity games
    2003 Inngår i: STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, 2003, s. 663-674Kapittel i bok, del av antologi (Annet vitenskapelig) Published
    Identifikatorer
    urn:nbn:se:uu:diva-92509 (URN)3-540-00623-0 (ISBN)
    Tilgjengelig fra: 2005-01-18 Laget: 2005-01-18bibliografisk kontrollert
    2. Complexity of model checking by iterative improvement: the pseudo-Boolean framework
    Åpne denne publikasjonen i ny fane eller vindu >>Complexity of model checking by iterative improvement: the pseudo-Boolean framework
    2003 Inngår i: Perspectives of Systems Informatics: 5th International Andrei Ershov Memorial Conference, 2003, s. 381-394Kapittel i bok, del av antologi (Annet vitenskapelig) Published
    Identifikatorer
    urn:nbn:se:uu:diva-92510 (URN)3-540-20813-5 (ISBN)
    Tilgjengelig fra: 2005-01-18 Laget: 2005-01-18bibliografisk kontrollert
    3. Memoryless determinacy of parity and mean payoff games: a simple proof
    Åpne denne publikasjonen i ny fane eller vindu >>Memoryless determinacy of parity and mean payoff games: a simple proof
    2004 Inngår i: Theoretical Computer Science, ISSN 0304-3975, Vol. 310, s. 365-378Artikkel i tidsskrift (Fagfellevurdert) Published
    Identifikatorer
    urn:nbn:se:uu:diva-92511 (URN)
    Tilgjengelig fra: 2005-01-18 Laget: 2005-01-18bibliografisk kontrollert
    4. A combinatorial strongly subexponential algorithm for mean payoff games
    Åpne denne publikasjonen i ny fane eller vindu >>A combinatorial strongly subexponential algorithm for mean payoff games
    2004 Inngår i: Mathematical Foundations of Computer Science 2004, 2004, s. 673-685Kapittel i bok, del av antologi (Annet vitenskapelig) Published
    Identifikatorer
    urn:nbn:se:uu:diva-92512 (URN)3-540-22823-3 (ISBN)
    Tilgjengelig fra: 2005-01-18 Laget: 2005-01-18bibliografisk kontrollert
    5. The controlled linear programming problem: DIMACS Technical Report 2004-41, September 2004
    Åpne denne publikasjonen i ny fane eller vindu >>The controlled linear programming problem: DIMACS Technical Report 2004-41, September 2004
    Manuskript (Annet vitenskapelig)
    Identifikatorer
    urn:nbn:se:uu:diva-92513 (URN)
    Tilgjengelig fra: 2005-01-18 Laget: 2005-01-18 Sist oppdatert: 2010-01-13bibliografisk kontrollert
  • 320.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Sandberg, Sven
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Vorobyov, Sergei
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games2004Rapport (Annet (populærvitenskap, debatt, mm))
  • 321.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
    Sandberg, Sven
    Vorobyov, Sergei
    Memoryless determinacy of parity and mean payoff games: a simple proof2004Inngår i: Theoretical Computer Science, ISSN 0304-3975, Vol. 310, nr 3, s. 365-378Artikkel i tidsskrift (Fagfellevurdert)
  • 322.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Sandberg, Sven
    Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Vorobyov, Sergei
    Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
    Memoryless Determinacy of Parity and Mean Payoff Games: A Simple Proof2004Inngår i: Theoretical Computer Science, Vol. 310, nr 1-3, s. 365-378Artikkel i tidsskrift (Annet (populærvitenskap, debatt, mm))
  • 323.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Sandberg, Sven
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Vorobyov, Sergei
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
    Randomized Subexponential Algorithms for Infinite Games2004Rapport (Annet (populærvitenskap, debatt, mm))
    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.

  • 324.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Svensson, Ola
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Vorobyov, Sergei
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi. datalogi.
    Controlled Linear Programming for Infinite Games2004Rapport (Annet (populærvitenskap, debatt, mm))
  • 325.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Vorobyov, Sergei
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games2007Inngår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 155, nr 2, s. 210-229Artikkel i tidsskrift (Fagfellevurdert)
  • 326.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
    Vorobyov, Sergei
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
    Two Adversary Lower Bounds for Parity Games2002Rapport (Annet vitenskapelig)
    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

  • 327.
    Björklund, Henrik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
    Vorobyov, Sergei
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
    Sandberg, Sven
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
    Optimization on Completely Unimodal Hypercubes2002Rapport (Annet vitenskapelig)
    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

  • 328. Blaheta, Radim
    et al.
    Kohut, Roman
    Neytcheva, Maya
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för teknisk databehandling. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Numerisk analys.
    Starý, Jirí
    Schwarz methods for discrete elliptic and parabolic problems with an application to nuclear waste repository modelling2007Inngår i: Mathematics and Computers in Simulation, ISSN 0378-4754, E-ISSN 1872-7166, Vol. 76, s. 18-27Artikkel i tidsskrift (Fagfellevurdert)
  • 329. Blaheta, Radim
    et al.
    Margenov, Svetozar
    Neytcheva, Maya
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för teknisk databehandling. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Numerisk analys.
    Aggregation-based multilevel preconditioning of non-conforming FEM elasticity problems2006Inngår i: Applied Parallel Computing: State of the Art in Scientific Computing, Berlin: Springer-Verlag , 2006, s. 847-856Konferansepaper (Fagfellevurdert)
  • 330. Blaheta, Radim
    et al.
    Margenov, Svetozar
    Neytcheva, Maya
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för teknisk databehandling. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Numerisk analys.
    Robust optimal multilevel preconditioners for non-conforming finite element systems2005Inngår i: Numerical Linear Algebra with Applications, ISSN 1070-5325, E-ISSN 1099-1506, Vol. 12, s. 495-514Artikkel i tidsskrift (Fagfellevurdert)
  • 331. Blaheta, Radim
    et al.
    Margenov, Svetozar
    Neytcheva, Maya
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för teknisk databehandling. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Numerisk analys.
    Uniform estimate of the constant in the strengthened CBS inequality for anisotropic non-conforming FEM systems2004Inngår i: Numerical Linear Algebra with Applications, ISSN 1070-5325, E-ISSN 1099-1506, Vol. 11, s. 309-326Artikkel i tidsskrift (Fagfellevurdert)
  • 332. Blaheta, Radim
    et al.
    Margenov, Svetozar
    Neytcheva, Maya
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för teknisk databehandling. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Numerisk analys.
    Uniform estimate of the constant in the strengthened CBS inequality for anisotropic non-conforming FEM systems2002Rapport (Annet vitenskapelig)
  • 333.
    Blamey, Ben
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för beräkningsvetenskap. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Tillämpad beräkningsvetenskap.
    Wrede, Fredrik
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för beräkningsvetenskap. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Tillämpad beräkningsvetenskap.
    Karlsson, Johan
    Hellander, Andreas
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för beräkningsvetenskap. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Tillämpad beräkningsvetenskap.
    Toor, Salman
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för beräkningsvetenskap. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Tillämpad beräkningsvetenskap.
    Adapting the secretary hiring problem for optimal hot–cold tier placement under top-K workloads2019Inngår i: Proc. 19th International Symposium on Cluster, Cloud, and Grid Computing, Los Alamitos, CA: IEEE Computer Society, 2019, s. 576-583Konferansepaper (Fagfellevurdert)
  • 334.
    Blom, Johan
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datorteknik. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Model-Based Protocol Testing in an Erlang Environment2016Doktoravhandling, monografi (Annet vitenskapelig)
    Abstract [en]

    Testing is the dominant technique for quality assurance of software systems. It typically consumes considerable resources in development projects, and is often performed in an ad hoc manner. This thesis is concerned with model-based testing, which is an approach to make testing more systematic and more automated. The general idea in model-based testing is to start from a formal model, which captures the intended behavior of the software system to be tested. On the basis of this model, test cases can be generated in a systematic way. Since the model is formal, the generation of test suites can be automated and with adequate tool support one can automatically quantify to which degree they exercise the tested software.

    Despite the significant improvements on model-based testing in the last 20 years, acceptance by industry has so far been limited. A number of commercially available tools exist, but still most testing in industry relies on manually constructed test cases.

    This thesis address this problem by presenting a methodology and associated tool support, which is intended to be used for model-based testing of communication protocol implementations in industry. A major goal was to make the developed tool suitable for industrial usage, implying that we had to consider several problems that typically are not addressed by the literature on model-based testing. The thesis presents several technical contributions to the area of model-based testing, including

    - a new specification language based on the functional programming language Erlang,

    - a novel technique for specifying coverage criteria for test suite generation, and

    - a technique for automatically generating test suites.

    Based on these developments, we have implemented a complete tool chain that generates and executes complete test suites, given a model in our specification language. The thesis also presents a substantial industrial case study, where our technical contributions and the implemented tool chain are evaluated. Findings from the case study include that test suites generated using (model) coverage criteria have at least as good fault-detection capability as equally large random test suites, and that model-based testing could discover faults in previously well-tested software where previous testing had employed a relaxed validation of requirements.

  • 335.
    Blomqvist, Johanna
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Using XGBoost to classify theBeihang Keystroke Dynamics Database2018Independent thesis Advanced level (professional degree), 20 poäng / 30 hpOppgave
    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

  • 336.
    Bloom, Thomas F.
    et al.
    Univ Cambridge, Dept Pure Math & Math Stat, Cambridge, England.
    Sisask, Olof
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Matematiska institutionen.
    Logarithmic bounds for Roth's theorem via almost-periodicity2019Inngår i: DISCRETE ANALYSIS, ISSN 2397-3129, artikkel-id 4Artikkel i tidsskrift (Fagfellevurdert)
    Abstract [en]

    We give a new proof of logarithmic bounds for Roth's theorem on arithmetic progressions, namely that if A subset of {1, 2,..., N} is free of three- term progressions, then vertical bar A vertical bar <= N/(logN)(1-o(1)). Unlike previous proofs, this is almost entirely done in physical space using almost-periodicity.

  • 337.
    Boano, Carlo Alberto
    et al.
    University of Lübeck.
    Wennerström, Hjalmar
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Zúñiga, Marco Antonio
    TU Delft.
    Brown, James
    Lancaster University.
    Keppitiyagama, Chamath
    Swedish Institute of Computer Science.
    Oppermann, Felix Jonathan
    University of Lübeck.
    Roedig, Utz
    Lancaster University.
    Nordén, Lars-Åke
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Voigt, Thiemo
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Römer, Kay
    University of Lübeck.
    Hot Packets: A systematic evaluation of the effect of temperature on low power wireless transceivers2013Inngår i: Proc. 5th Extreme Conference on Communication, New York: ACM Press, 2013, s. 7-12Konferansepaper (Fagfellevurdert)
    Abstract [en]

    Temperature is known to have a significant effect on the performance of radio transceivers: the higher the temperature, the lower the quality of links. Analysing this effect is particularly important in sensor networks because several applications are exposed to harsh environmental conditions. Daily or hourly changes in temperature can dramatically reduce the throughput, increase the delay, or even lead to network partitions. A few studies have quantified the impact of temperature on low-power wireless links, but only for a limited temperature range and on a single radio transceiver. Building on top of these preliminary observations, we design a low-cost experimental infrastructure to vary the onboard temperature of sensor nodes in a repeatable fashion, and we study systematically the impact of temperature on various sensornet platforms. We show that temperature affects transmitting and receiving nodes differently, and that all platforms follow a similar trend that can be captured in a simple first-order model. This work represents an initial stepping stone aimed at predicting the performance of a network considering the particular temperature profile of a given environment.

  • 338.
    Bohlin, Therese
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Soleimanifard, Siavash
    Inferring Compact Models of Communication Protocol Entities2010Inngår i: Leveraging Applications of Formal Methods, Verification, and Validation: Part I / [ed] Margaria, Tiziana; Steffen, Bernhard, Berlin: Springer-Verlag , 2010, s. 658-672Konferansepaper (Fagfellevurdert)
    Abstract [en]

    Our overall goal is to support model-based approaches to verification and validation of communication protocols by techniques that automatically generate models of communication protocol entities from observations of their external behavior, using techniques based on regular inference (aka automata learning). In this paper, we address the problem that existing regular inference techniques produce "flat" state machines, whereas practically useful protocol models structure the internal state in terms of control locations and state variables, and describes dynamic behavior in a suitable (abstract) programming notation. We present a technique for introducing structure of an unstructured finite-state machine by introducing state variables and program-like descriptions of dynamic behavior, given a certain amount of user guidance. Our technique groups states with "similar control behavior" into control locations, and obtain program-like descriptions by means of decision tree generation. We have applied parts of our approach to an executable state machine specification of the Mobile Arts Advanced Mobile Location Center (A-MLC) protocol and evaluated the results by comparing them to the original specification.

  • 339.
    Boivie, Inger
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för människa-datorinteraktion. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Människa-datorinteraktion.
    A Fine Balance: Addressing Usability and Users’ Needs in the Development of IT Systems for the Workplace2005Doktoravhandling, med artikler (Annet vitenskapelig)
    Abstract [en]

    IT systems with poor usability are a serious problem in many workplaces. Many workers, particularly office workers, spend a large part of their workday at the computer, and usability problems can cause frustration and impact negatively on productivity. This thesis discusses some of the problems associated with addressing usability and users’ needs in IT systems development.

    Usability issues and users’ needs are often marginalised or even abandoned in systems development. Technical issues and deadlines are given precedence, while usability activities and user activities are cut back or cancelled. Research shows that there are various obstacles to usability and user involvement, including difficulties with understanding the usability concept, insufficient usability expertise and a lack of time and resources.

    This thesis presents a number of studies that look at the problem from different angles. The main question is why usability and users’ needs are marginalised in bespoke systems development, where IT systems are built for a specific work context. The research presented in this thesis also addresses user-centred systems design as a way of integrating usability issues and users’ needs into systems development. The thesis concludes with a discussion about different ways of viewing and representing the users’ work: the systems theoretical view and the view of work as a social process. The former emphasises the formal aspects of work and views users as components in an overall system, whereas the latter focuses on work as a social process and people as active agents. The discussion concludes with the argument that the conflict between these two views is played out in the systems development process, which may help explain some of the difficulties that arise when working with usability and users’ needs.

    Delarbeid
    1. The Lonesome Cowboy: A Study of the Usability Designer Role in Systems Development
    Åpne denne publikasjonen i ny fane eller vindu >>The Lonesome Cowboy: A Study of the Usability Designer Role in Systems Development
    2006 (engelsk)Inngår i: Interacting with computers, ISSN 0953-5438, E-ISSN 1873-7951, Vol. 18, nr 4, s. 601-634Artikkel i tidsskrift (Fagfellevurdert) Published
    Abstract [en]

    This paper reports on an evaluation of the usability designer role as applied in two Swedish systems development organisations. The role was initially defined by us, but evolved in these two organisations. We conducted interviews with usability designers, project managers and a user representative. Our main research question was whether or not the introduction of a usability designer has been successful in terms of changes in the systems development process and the impact the role has had on products, projects and organisations. To some extent, the role has met our expectations and intentions for instance, in helping the usability designers shift their focus towards design, and assume some kind of "users' advocate" role. But in other ways, the role "failed". The usability designers in our study are still facing the kind of problems and obstacles that usability professionals have always had to deal with.

    Emneord
    user-centred systems design; UCSD; usability; usability practitioner; usability professional; software development
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-76432 (URN)10.1016/j.intcom.2005.10.003 (DOI)000238876500005 ()
    Tilgjengelig fra: 2006-03-21 Laget: 2006-03-21 Sist oppdatert: 2018-01-13bibliografisk kontrollert
    2. Making a Difference: A Survey of the Usability Profession in Sweden
    Åpne denne publikasjonen i ny fane eller vindu >>Making a Difference: A Survey of the Usability Profession in Sweden
    Vise andre…
    2004 Inngår i: Proceedings of NordiCHI 2004, 2004, s. 207-215Kapittel i bok, del av antologi (Annet vitenskapelig) Published
    Identifikatorer
    urn:nbn:se:uu:diva-93521 (URN)
    Tilgjengelig fra: 2005-09-30 Laget: 2005-09-30bibliografisk kontrollert
    3. Usability professionals: current practices and future development
    Åpne denne publikasjonen i ny fane eller vindu >>Usability professionals: current practices and future development
    2006 (engelsk)Inngår i: Interacting with computers, ISSN 0953-5438, E-ISSN 1873-7951, Vol. 18, nr 4, s. 568-600Artikkel i tidsskrift (Fagfellevurdert) Published
    Abstract [en]

    The usability concept has now received such a wide recognition in information technology (IT) development that working with usability can be regarded as a profession in its own right. In recent research projects, we have surveyed and studied usability work on an individual level in a number of Swedish development organisations, including success factors and obstacles. What we have seen relates to the individual usability professional and her background and experiences, the organisation in which she operates, the development process, communication and communication means, and finally the attitudes and basic values held by the people involved.

    In this paper, we compile and reflect on selected findings from different studies on usability work in practical systems1 development in a number of Swedish organisations. We discuss our findings from a practical point of view and relate them to the research of others within the international HCI community. Finally, we discuss some issues we consider important for the future development of the practice of usability that we believe is of interest to the international community of usability professionals.

    Emneord
    Usability, Design, User-centred design, Organisation, Software development, Practice, Role, Profession
    HSV kategori
    Identifikatorer
    urn:nbn:se:uu:diva-76433 (URN)10.1016/j.intcom.2005.10.005 (DOI)000238876500004 ()
    Tilgjengelig fra: 2006-03-21 Laget: 2006-03-21 Sist oppdatert: 2018-01-13bibliografisk kontrollert
    4. Key Principles for User-Centred Systems Design
    Åpne denne publikasjonen i ny fane eller vindu >>Key Principles for User-Centred Systems Design
    Vise andre…
    2003 Inngår i: Behaviour & Information Technology, Vol. 22, nr 6, s. 397 – 409-Artikkel i tidsskrift (Fagfellevurdert) Published
    Identifikatorer
    urn:nbn:se:uu:diva-93523 (URN)
    Forskningsfinansiär
    Tilgjengelig fra: 2005-09-30 Laget: 2005-09-30 Sist oppdatert: 2010-11-22bibliografisk kontrollert
    5. Why Usability Gets Lost or Usability in In-house Software Development
    Åpne denne publikasjonen i ny fane eller vindu >>Why Usability Gets Lost or Usability in In-house Software Development
    2003 Inngår i: Interacting with Computers, Vol. 15, nr 4, s. 623-639Artikkel i tidsskrift (Fagfellevurdert) Published
    Identifikatorer
    urn:nbn:se:uu:diva-93524 (URN)
    Tilgjengelig fra: 2005-09-30 Laget: 2005-09-30bibliografisk kontrollert
    6. Addressing Users' Health Issues in Software Development: An Exploratory Study
    Åpne denne publikasjonen i ny fane eller vindu >>Addressing Users' Health Issues in Software Development: An Exploratory Study
    2003 Inngår i: Behaviour & Information Technology, Vol. 22, nr 6, s. 411-420Artikkel i tidsskrift (Fagfellevurdert) Published
    Identifikatorer
    urn:nbn:se:uu:diva-93525 (URN)
    Tilgjengelig fra: 2005-09-30 Laget: 2005-09-30bibliografisk kontrollert
    7. From Piles to Tiles: Designing for Overview and Control in Case Handling Systems
    Åpne denne publikasjonen i ny fane eller vindu >>From Piles to Tiles: Designing for Overview and Control in Case Handling Systems
    2004 Inngår i: Conference Proceedings of OZCHI 2004, 2004, s. 161-170Kapittel i bok, del av antologi (Annet vitenskapelig) Published
    Identifikatorer
    urn:nbn:se:uu:diva-93526 (URN)
    Tilgjengelig fra: 2005-09-30 Laget: 2005-09-30bibliografisk kontrollert
  • 340. Bongo, Lars Ailo
    et al.
    Ciegis, Raimondas
    Frasheri, Neki
    Gong, Jing
    Kimovski, Dragi
    Kropf, Peter
    Margenov, Svetozar
    Mihajlovic, Milan
    Neytcheva, Maya
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för beräkningsvetenskap. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Numerisk analys.
    Rauber, Thomas
    Rünger, Gudula
    Trobec, Roman
    Wuyts, Roel
    Wyrzykowski, Roman
    Applications for ultrascale computing2015Inngår i: Supercomputing Frontiers and Innovations, ISSN 2409-6008, Vol. 2, nr 1, s. 19-48Artikkel i tidsskrift (Fagfellevurdert)
  • 341.
    Borgh, Joakim
    et al.
    Ericsson Res, Stockholm, Sweden.
    Ngai, Edith
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ohlman, Börje
    Ericsson Res, Stockholm, Sweden.
    Malik, Adeel Mohammad
    Ericsson Res, Stockholm, Sweden.
    Employing attribute-based encryption in systems with resource constrained devices in an information-centric networking context2017Inngår i: 2017 Global Internet of Things Summit (GIoTS), IEEE, 2017, s. 397-402Konferansepaper (Annet vitenskapelig)
    Abstract [en]

    Attribute-Based Encryption (ABE) is considered to be one of the most promising ways to be enforce access control in Information-Centric Networking (ICN). As the Internet of Things (IoT) is being considered as one of the primary use cases for ICN it raises the question of the compatibility between IoT and ABE. An important part of the IoT is the resource constrained devices, for them there is a challenge to perform the computationally expensive operations required for ABE. In this paper we consider ABE in sensor networks and discuss the strengths and weaknesses of a system solution where the ABE operations are performed on the sensors. To properly discuss these concerns we have implemented two ABE schemes, a Single-authority ABE (SA-CP-ABE) scheme and a Multi-authority ABE (MA-CP-ABE) scheme. Results regarding the execution time, RAM usage, data overhead and battery consumption of these implementations on a sensor are presented. We conclude that it is possible, already today, to perform ABE on sensors for smaller policies. The main limitation in deploying ABE in sensors is the RAM size of the sensors.

  • 342.
    Borgström, Johannes
    Department of Software Engineering and Theoretical Computer Science, Technische Universität Berlin, Germany.
    A Complete Symbolic Bisimilarity for an Extended Spi Calculus2009Inngår i: Electronical Notes in Theoretical Computer Science, ISSN 1571-0661, E-ISSN 1571-0661, Vol. 242, nr 3, s. 3-20Artikkel i tidsskrift (Fagfellevurdert)
    Abstract [en]

    Several symbolic notions of bisimilarity have been defined for the spi calculus and the applied pi calculus. In this paper, we treat a spi calculus with a general constructor-destructor message algebra, and define a symbolic bisimilarity that is both sound and complete with respect to its concrete counterpart. 

  • 343.
    Borgström, Johannes
    EPFL.
    Equivalences and Calculi for Formal Verification of Cryptographic Protocols2008Doktoravhandling, monografi (Annet vitenskapelig)
    Abstract [en]

    Security protocols are essential to the proper functioning of any distributed system running over an insecure network but often have flaws that can be exploited even without breaking the cryptography. Formal cryptography, the assumption that the cryptographic primitives are flawless, facilitates the construction of formal models and verification tools. Such models are often based on process calculi, small formal languages for modelling communicating systems.

    The spi calculus, a process calculus for the modelling and formal verification of cryptographic protocols, is an extension of the pi calculus with cryptography. In the spi calculus, security properties can be formulated as equations on process terms, so no external formalism is needed. Moreover, the contextual nature of observational process equivalences takes into account any attacker/environment that can be expressed in the calculus.

    We set out to address the problem of automatic verification of observational equivalence in an extension of the spi calculus: A channel-passing calculus with a more general expression language.

    As a first step, we study existing non-contextual proof techniques for a particular canonical contextual equivalence. In contrast to standard process calculi, reasoning on cryptographic processes must take into account the partial knowledge of the environment about transmitted messages. In the setting of the spi calculus, several notions of environment-sensitive bisimulation has been developed to treat this environment knowledge. We exhibit distinguishing examples between several of these notions, including ones previously believed to coincide. We then give a general framework for comparison of environment-sensitive relations, based on a comparison of the corresponding kinds of environment and notions of environment consistency. Within this framework we perform an exhaustive comparison of the different bisimulations, where every possible relation that is not proven is disproven.

    For the second step, we consider the question of which expression languages are suitable. Extending the expression language to account for more sophisticated cryptographic primitives or other kinds of data terms quickly leads to decidability issues. Two important problems in this area are the knowledge problem and an indistinguishability problem called static equivalence. It is known that decidability of static equivalence implies decidability of knowledge in many cases; we exhibit an expression language where knowledge is decidable but static equivalence is not. We then define a class of constructor-destructor expression languages and prove that environment consistency over any such language directly corresponds to static equivalence in a particular extension thereof. We proceed to place some loose constraints on deterministic expression evaluation, and redefine the spi calculus in this more general setting.

    Once we have chosen an expression language, we encounter a third problem, which is inherent in the operational semantics of message-passing process calculi: The possibility to receive arbitrary messages gives rise to infinite branching on process input. To mitigate this problem, we define a symbolic semantics, where the substitution of received messages for input variables never takes place. Instead, input variables are only subject to logical constraints. We then use this symbolic semantics to define a symbolic bisimulation that is sound and complete with respect to its concrete counterpart, extending the possibilities for automated bisimulation checkers.

  • 344.
    Borgström, Johannes
    EPFL.
    Static Equivalence is Harder than Knowledge2006Inngår i: Electronical Notes in Theoretical Computer Science, ISSN 1571-0661, E-ISSN 1571-0661, Vol. 154, nr 3, s. 45-57Artikkel i tidsskrift (Fagfellevurdert)
    Abstract [en]

    There are two main ways of defining secrecy of cryptographic protocols. The first version checks if the adversary can learn the value of a secret parameter. In the second version, one checks if the adversary can notice any difference between protocol runs with different values of the secret parameter.

    We give a new proof that when considering more complex equational theories than partially invertible functions, these two kinds of secrecy are not equally difficult to verify. More precisely, we identify a message language equipped with a convergent rewrite system such that after a completed protocol run, the first problem mentioned above (adversary knowledge) is decidable but the second problem (static equivalence) is not. The proof is by reduction of the ambiguity problem for context-free grammars. 

  • 345.
    Borgström, Johannes
    et al.
    Microsoft Research, Cambridge.
    Bhargavan, Karthikeyan
    Microsoft Research, Cambridge.
    Gordon, Andrew D
    Microsoft Research, Cambridge.
    A Compositional Theory for STM Haskell2009Inngår i: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell, ACM Press , 2009, s. 69-80Konferansepaper (Fagfellevurdert)
    Abstract [en]

    We address the problem of reasoning about Haskell programs that use Software Transactional Memory (STM). As a motivating example, we consider Haskell code for a concurrent non-deterministic tree rewriting algorithm implementing the operational semantics of the ambient calculus. The core of our theory is a uniform model, in the spirit of process calculi, of the run-time state of multi-threaded STM Haskell programs. The model was designed to simplify both local and compositional reasoning about STM programs. A single reduction relation captures both pure functional computations and also effectful computations in the STM and I/O monads. We state and prove liveness, soundness, completeness, safety, and termination properties relating source processes and their Haskell implementation. Our proof exploits various ideas from concurrency theory, such as the bisimulation technique, but in the setting of a widely used programming language rather than an abstract process calculus. Additionally, we develop an equational theory for reasoning about STM Haskell programs, and establish for the first time equations conjectured by the designers of STM Haskell. We conclude that using a pure functional language extended with STM facilitates reasoning about concurrent implementation code. 

  • 346.
    Borgström, Johannes
    et al.
    EPFL.
    Briais, Sebastien
    EPFL.
    Nestmann, Uwe
    EPFL.
    Symbolic Bisimulation in the Spi Calculus2004Inngår i: CONCUR 2004: Concurrency theory, proceedings / [ed] P. Gardner and N. Yoshida, Berlin Heidelberg: Springer Berlin/Heidelberg, 2004, Vol. 3170, s. 161-176Konferansepaper (Fagfellevurdert)
    Abstract [en]

    The spi calculus is an executable model for the description and analysis of cryptographic protocols. Security objectives like secrecy and authenticity can be formulated as equations between spi calculus terms, where equality is interpreted as a contextual equivalence. One problem with verifying contextual equivalences for message-passing process calculi is the infinite branching on process input. In this paper, we propose a general symbolic semantics for the spi calculus, where an input prefix gives rise to only one transition. To avoid infinite quantification over contexts, non-contextual concrete bisimulations approximating barbed equivalence have been defined. We propose a symbolic bisimulation that is sound with respect to barbed equivalence, and brings us closer to automated bisimulation checks.

  • 347.
    Borgström, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Chen, Juan
    Microsoft Research.
    Swamy, Nikhil
    Microsoft Research.
    Verified Stateful Programs with Substructural State and Hoare Types2011Inngår i: Proc. 5th ACM Workshop on Programming Languages Meets Program Verification, New York: ACM Press , 2011, s. 15-26Konferansepaper (Fagfellevurdert)
  • 348.
    Borgström, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Crafa, Silvia
    Proc. Combined 21st International Workshop on Expressiveness in Concurrency (EXPRESS 2014) and 11th Workshop on Structural Operational Semantics (SOS 2014)2014Konferanseproceedings (Fagfellevurdert)
  • 349.
    Borgström, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Dal Lago, Ugo
    Gordon, Andrew D.
    Szymczak, Marcin
    A Lambda-Calculus Foundation for Universal Probabilistic Programming2016Inngår i: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 51, nr 9, s. 33-46Artikkel i tidsskrift (Fagfellevurdert)
  • 350.
    Borgström, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    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 learning2013Inngår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 9, nr 3, s. 11-Artikkel i tidsskrift (Fagfellevurdert)
    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.

45678910 301 - 350 of 2118
RefereraExporteraLink til resultatlisten
Permanent link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf