uu.seUppsala University Publications
Change search
Refine search result
14151617 801 - 833 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.
  • 801.
    Zeitler, Erik
    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. CSD.
    Working with Stella2006In: Astronnews, ISSN 1871-6644, no 1, p. 12-13Article in journal (Other (popular scientific, debate etc.))
  • 802.
    Zeitler, Erik
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Risch, Tore
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Massive scale-out of expensive continuous queries2011In: 36th International Conference on Very Large Data Bases: VLDB 2010, 2011Conference paper (Refereed)
    Abstract [en]

    Scalable execution of expensive continuous queries over massive data streams requires input streams to be split into parallel sub-streams. The query operators are continuously executed in parallel over these sub-streams. Stream splitting involves both partitioning and replication of incoming tuples, depending on how the continuous query is parallelized. We provide a stream splitting operator that enables such customized stream splitting. However, it is critical that the stream splitting itself keeps up with input streams of high volume. This is a problem when the stream splitting predicates have some costs. Therefore, to enable customized splitting of high-volume streams, we introduce a parallelized stream splitting operator, called parasplit. We investigate the performance of parasplit using a cost model and experimentally. Based on these results, a heuristic is devised to automatically parallelize the execution of parasplit. We show that the maximum stream rate of parasplit approaches network speed, and that the parallelization is resource efficient. Finally, the scalability of our approach is experimentally demonstrated on the Linear Road Benchmark, showing an order of magnitude higher stream processing rate over previously published results, allowing at least 512 expressways.

  • 803.
    Zeitler, Erik
    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. CSD.
    Risch, Tore
    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. CSD.
    Processing High-Volume Stream Queries on a Supercomputer2006In: Processing High-Volume Stream Queries on a Supercomputer, 2006, p. 147-Conference paper (Refereed)
    Abstract [en]

    Scientific instruments, such as radio telescopes, colliders, sensor networks, and simulators generate very high volumes of data streams that scientists analyze to detect and understand physical phenomena. The high data volume and the need for advanced computations on the streams require substantial hardware resources and scalable stream processing. We address these challenges by developing data stream management technology to support high-volume stream queries utilizing massively parallel computer hardware. We have developed a data stream management system prototype for state-of-the-art parallel hardware. The performance evaluation uses real measurement data from LOFAR, a radio telescope antenna array being developed in the Netherlands.

  • 804.
    Zeitler, Erik
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Risch, Tore
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Scalable Splitting of Massive Data Streams2010In: Database Systems for Advanced Applications: Part II / [ed] Kitagawa H., Ishikawa Y., Li Q., Watanabe C., Berlin: Springer-Verlag , 2010, p. 184-198Conference paper (Refereed)
    Abstract [en]

    Scalable execution of continuous queries over massive data streams often requires splitting input streams into parallel sub-streams over which query operators are executed in parallel. Automatic stream splitting is in general very difficult, as the optimal parallelization may depend on application semantics. To enable application specific stream splitting, we introduce splitstream functions where the user specifies non-procedural stream partitioning and replication. For high-volume streams, the stream splitting itself becomes a performance bottleneck. A cost model is introduced that estimates the performance of splitstream functions with respect to throughput and CPU usage. We implement parallel splitstream functions, and relate experimental results to cost model estimates. Based on the results, a splitstream function called autosplit is proposed, which scales well for high degrees of parallelism, and is robust for varying proportions of stream partitioning and replication. We show how user defined parallelization using autosplit provides substantially improved scalability (L = 64) over previously published results for the Linear Road Benchmark.

  • 805.
    Zeitler, Erik
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Risch, Tore
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Using stream queries to measure communication performance of a parallel computing environment2007In: Proc. 1st International Workshop on Distributed Event Processing, Systems and Applications (DEPSA’07), 2007Conference paper (Refereed)
  • 806.
    Zeljić, Aleksandar
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    From Machine Arithmetic to Approximations and back again: Improved SMT Methods for Numeric Data Types2017Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    Safety-critical systems, especially those found in avionics and automotive industries, rely on machine arithmetic to perform their tasks: integer arithmetic, fixed-point arithmetic or floating-point arithmetic (FPA). Machine arithmetic exhibits subtle differences in behavior compared to the ideal mathematical arithmetic, due to fixed-size representation in memory. Failure of safety-critical systems is unacceptable, due to high-stakes involving human lives or huge amounts of money, time and effort. By formally proving properties of systems, we can be assured that they meet safety requirements. However, to prove such properties it is necessary to reason about machine arithmetic. SMT techniques for machine arithmetic are lacking scalability. This thesis presents approaches that augment or complement existing SMT techniques for machine arithmetic.

    In this thesis, we explore approximations as a means of augmenting existing decision procedures. A general approximation refinement framework is presented, along with its implementation called UppSAT. The framework solves a sequence of approximations. Initially very crude, these approximations are fairly easy to solve. Results of solving approximate constraints are used to either reconstruct a solution of original constraints, obtain a proof of unsatisfiability or to refine the approximation. The framework preserves soundness, completeness, and termination of the underlying decision procedure, guaranteeing that eventually, either a solution is found or a proof that solution does not exist. We evaluate the impact of approximations implemented in the UppSAT framework on the state-of-the-art in SMT for floating-point arithmetic.

    A novel method to reason about the theory of fixed-width bit-vectors called mcBV is presented. It is an instantiation of the model constructing satisfiability calculus, mcSAT, and uses a new lazy representation of bit-vectors that allows both bit- and word-level reasoning. It uses a greedy explanation generalization mechanism capable of more general learning compared to traditional approaches. Evaluation of mcBV shows that it can outperform bit-blasting on several classes of problems.

    List of papers
    1. Deciding bit-vector formulas with mcSAT
    Open this publication in new window or tab >>Deciding bit-vector formulas with mcSAT
    2016 (English)In: Theory and Applications of Satisfiability Testing: SAT 2016, Springer, 2016, p. 249-266Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Springer, 2016
    Series
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9710
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-305182 (URN)10.1007/978-3-319-40970-2_16 (DOI)000387430600016 ()978-3-319-40969-6 (ISBN)
    Conference
    SAT 2016, July 5–8, Bordeaux, France
    Projects
    UPMARC
    Available from: 2016-06-11 Created: 2016-10-12 Last updated: 2018-01-14Bibliographically approved
    2. An approximation framework for solvers and decision procedures
    Open this publication in new window or tab >>An approximation framework for solvers and decision procedures
    2017 (English)In: Journal of automated reasoning, ISSN 0168-7433, E-ISSN 1573-0670, Vol. 58, no 1, p. 127-147Article in journal (Refereed) Published
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-305180 (URN)10.1007/s10817-016-9393-1 (DOI)000392387400006 ()
    Projects
    UPMARC
    Available from: 2016-11-10 Created: 2016-10-12 Last updated: 2018-01-14Bibliographically approved
    3. Exploring Approximations for Floating-Point Arithmetic using UppSAT
    Open this publication in new window or tab >>Exploring Approximations for Floating-Point Arithmetic using UppSAT
    (English)Manuscript (preprint) (Other academic)
    Abstract [en]

    We consider the problem of solving floating-point constraints obtained from software verification. We present UppSAT --- a new implementation of a systematic approximation refinement framework [ZWR17] as an abstract SMT solver. Provided with an approximation and a decision procedure (implemented in an off-the-shelf SMT solver), UppSAT yields an approximating SMT solver. Additionally, UppSAT includes a library of predefined approximation components which can be combined and extended to define new encodings, orderings and solving strategies. We propose that UppSAT can be used as a sandbox for easy and flexible exploration of new approximations. To substantiate this, we explore several approximations of floating-point arithmetic. Approximations can be viewed as a composition of an encoding into a target theory, a precision ordering, and a number of strategies for model reconstruction and precision (or approximation) refinement. We present encodings of floating-point arithmetic into reduced precision floating-point arithmetic, real-arithmetic, and fixed-point arithmetic (encoded into the theory of bit-vectors in practice). In an experimental evaluation, we compare the advantages and disadvantages of approximating solvers obtained by combining various encodings and decision procedures (based on existing, state-of-the-art SMT solvers for floating-point, real, and bit-vector arithmetic).

    Keywords
    SAT, SMT, approximations, model construction, floating-point arithmetic
    National Category
    Computer Sciences
    Research subject
    Computer Science
    Identifiers
    urn:nbn:se:uu:diva-334564 (URN)
    Available from: 2017-11-24 Created: 2017-11-24 Last updated: 2018-01-13
  • 807.
    Zhang, Jiao
    et al.
    Natl Univ Def Technol, Coll Elect Sci, Changsha 410073, Hunan, Peoples R China;Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China.
    Hu, Xiping
    Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China.
    Ning, Zhaolong
    Dalian Univ Technol, Key Lab Ubiquitous Network & Serv Software Liaoni, Sch Software, Dalian 116620, Peoples R China.
    Ngai, Edith
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Zhou, Li
    Natl Univ Def Technol, Coll Elect Sci, Changsha 410073, Hunan, Peoples R China.
    Wei, Jibo
    Natl Univ Def Technol, Coll Elect Sci, Changsha 410073, Hunan, Peoples R China.
    Cheng, Jun
    Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China.
    Hu, Bin
    Lanzhou Univ, Sch Informat Sci & Engn, Lanzhou 410073, Gansu, Peoples R China.
    Leung, Victor C. M.
    Univ British Columbia, Dept Elect & Comp Engn, Vancouver, BC V6T 1Z4, Canada.
    Joint Resource Allocation for Latency-Sensitive Services Over Mobile Edge Computing Networks With Caching2019In: IEEE Internet of Things Journal, ISSN 2327-4662, Vol. 6, no 3, p. 4283-4294Article in journal (Refereed)
    Abstract [en]

    Mobile edge computing (MEC) has risen as a promising paradigm to provide high quality of experience via relocating the cloud server in close proximity to smart mobile devices (SMDs). In MEC networks, the MEC server with computation capability and storage resource can jointly execute the latency-sensitive offloading tasks and cache the contents requested by SMDs. In order to minimize the total latency consumption of the computation tasks, we jointly consider computation offloading, content caching, and resource allocation as an integrated model, which is formulated as a mixed integer nonlinear programming (MINLP) problem. We design an asymmetric search tree and improve the branch and bound method to obtain a set of accurate decisions and resource allocation strategies. Furthermore, we introduce the auxiliary variables to reformulate the proposed model and apply the modified generalized benders decomposition method to solve the MINLP problem in polynomial computation complexity time. Simulation results demonstrate the superiority of the proposed schemes.

  • 808.
    Zhu, Minpeng
    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.
    Scalable Queries over Log Database Collections2016Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    In industrial settings, machines such as trucks, hydraulic pumps, etc. are widely distributed at different geographic locations where sensors on machines produce large volumes of data. The data produced is stored locally in autonomous databases called log databases. The collection of log databases is dynamically changing when new sites are dynamically added or removed from the federation.

    In this application context, an efficient way to search and analyze passed behavior of products in use is desired. To enable scalable queries over collections of distributed and autonomous log databases we developed the FLOQ (Fused LOg database Query processor) system, which provides a global view of the working status of all machines on the sites through a meta-database integrating the dynamic log database collection. A particular challenge in this scenario is a scalable way to process numerical queries that identify anomalies by joining data from the meta-database with data selected from the collection of distributed and autonomous log databases. The Thesis describes the architecture of FLOQ. In particular different strategies to execute numerical queries over log database collections are investigated. FLOQ allows both the meta-database and the log databases to be stored in multiple formats using different kinds of data managers. FLOQ provides general and extensible mechanisms for efficient processing of queries over different kinds of distributed data sources.

    List of papers
    1. Querying Combined Cloud-Based and Relational Databases
    Open this publication in new window or tab >>Querying Combined Cloud-Based and Relational Databases
    2011 (English)Conference paper, Published paper (Refereed)
    Abstract [en]

    An increasing amount of data is stored in cloud repositories, which provide high availability, accessibility, and scalability. However, for security reasons enterprises often need to store the core proprietary data in their own relational databases, while common data to be widely available can be stored in a cloud data repository. For example, the subsidiaries of a global enterprise are located in different geographic places where each subsidiary is likely to maintain its own local database. In such a scenario, data integration among the local databases and the cloud-based data is inevitable. We have developed a system called BigIntegrator to enable general queries that combine data in cloud-based data stores with relational databases. We present the design and working principle of the system. A scenario of querying data from both kinds of data sources is used as illustration. The system is general and extensible to integrate data from different kinds of data sources. A particular challenge being addressed is the limited query capabilities of cloud data stores. BigIntegrator utilizes knowledge of those limitations to produce efficient query execution.

    Keywords
    cloud data repository; relational database; data integration; Bigtable;
    National Category
    Computer and Information Sciences
    Identifiers
    urn:nbn:se:uu:diva-275026 (URN)10.1109/CSC.2011.6138543 (DOI)
    Conference
    2011 International Conference on Cloud and Service Computing (CSC)
    Available from: 2016-01-28 Created: 2016-01-28 Last updated: 2018-01-10
    2. Scalable Numerical SPARQL Queries over Relational Databases
    Open this publication in new window or tab >>Scalable Numerical SPARQL Queries over Relational Databases
    2014 (English)Conference paper, Published paper (Refereed)
    Abstract [en]

    We present an approach for scalable processing of SPARQL queries to RDF views of numerical data stored in relational databases (RDBs). Such queries include numerical expressions, inequalities, comparisons, etc. inside FILTERs. We call such FILTERs numerical expressions and the queries - numerical SPARQL queries. For scalable execution of numerical SPARQL queries over RDBs, numerical operators should be pushed into SQL rather than executing the filters as post-processing outside the RDB; otherwise the query execution is slowed down, since a lot of data is transported from the RDB server and furthermore indexes on the server are not utilized. The NUMTranslator algorithm converts numerical expressions in numerical SPARQL queries into corresponding SQL expressions. We show that NUMTranslator improves substantially the scalability of SPARQL queries based on a benchmark that analyses numerical logs stored in an RDB. We compared the performance of our approach with the performance of other systems processing SPARQL queries to RDF views of RDBs and show that NUMTranslator improves substantially the scalability of numerical queries compared to the other systems’ approaches.

    National Category
    Computer and Information Sciences
    Identifiers
    urn:nbn:se:uu:diva-275027 (URN)
    Conference
    4th International workshop on linked web data management (LWDM 2014) in conjunction with the EDBT/ICDT 2014 Joint Conference, Ath-ens, Greece, March 28, 2014
    Available from: 2016-01-28 Created: 2016-01-28 Last updated: 2018-01-10
    3. Scalable queries over log database collections
    Open this publication in new window or tab >>Scalable queries over log database collections
    2015 (English)In: Data Science, Springer, 2015, p. 173-185Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Springer, 2015
    Series
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9147
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-274784 (URN)10.1007/978-3-319-20424-6_17 (DOI)000364104600017 ()978-3-319-20423-9 (ISBN)
    Conference
    BICOD 2015, July 6–8, Edinburgh, UK
    Available from: 2015-06-11 Created: 2016-01-26 Last updated: 2018-01-10Bibliographically approved
    4. Utilizing a NoSQL Data Store for Scalable Log Analysis
    Open this publication in new window or tab >>Utilizing a NoSQL Data Store for Scalable Log Analysis
    2015 (English)Conference paper, Published paper (Refereed)
    Abstract [en]

    A potential problem for persisting large volume of data logs with a conventional relational database is that loading massive logs produced at high rates is not fast enough due to the strong consistency model and high cost of indexing. As a possible alternative, a modern NoSQL data store, which sacrifices transactional consistency to achieve higher performance and scalability, can be utilized. In this paper, we investigate to what degree a state-of-the-art NoSQL database can achieve high performance persisting and fundamental analyses of large-scale data logs from real world applications. For the evaluation, a state-of-the-art NoSQL database, MongoDB, is compared with a relational DBMS from a major commercial vendor and with a popular open source relational DBMS. MongoDB is chosen as it provides both primary and secondary indexing compared to other popular NoSQL systems. These indexing techniques are essential for scalable processing of queries over large scale data logs. To explore the impact of parallelism on query execution, sharding was investigated for MongoDB. Our results revealed that relaxing the consistency did not provide substantial performance enhancement in persisting large-scale data logs for any of the systems. However, for high-performance loading and analysis of data logs, MongoDB is shown to be a viable alternative compared to relational databases for queries where the choice of an optimal execution plan is not critical.

    National Category
    Computer and Information Sciences
    Identifiers
    urn:nbn:se:uu:diva-275028 (URN)10.1145/2790755.2790772 (DOI)978-1-4503-3414-3 (ISBN)
    Conference
    19th International Database Engineering & Applications Symposium (IDEAS 2015), Yokohama, Japan, July 13-15, 2015
    Available from: 2016-01-28 Created: 2016-01-28 Last updated: 2018-01-10
  • 809.
    Zhu, Minpeng
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Mahmood, Khalid
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Risch, Tore
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Scalable queries over log database collections2015In: Data Science, Springer, 2015, p. 173-185Conference paper (Refereed)
  • 810.
    Ågren, Magnus
    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.
    High-level modelling and local search2005Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    Combinatorial optimisation problems are ubiquitous in our society and appear in such varied guises as DNA sequencing, scheduling, configuration, airline-crew and nurse rostering, combinatorial auctions, vehicle routing, and financial portfolio design. Their efficient solution is crucial to many people and has been the target for much research during the last decades. One successful area of research for solving such problems is constraint programming. Yet, current-generation constraint programming languages are considered by many, especially in industry, to be too low-level, difficult, and large. In this thesis, we argue that solver-independent, high-level relational constraint modelling leads to a simpler and smaller language, to more concise, intuitive, and analysable models, as well as to more efficient and effective model formulation, maintenance, reformulation, and verification. All this can be achieved without sacrificing the possibility of efficient solving, so that even time-pressed modellers can be well assisted. Towards this, we propose the ESRA relational constraint modelling language, showcase its elegance on some real-life problems, and outline a compilation philosophy for such languages.

    In order to compile high-level languages such as ESRA to current generation constraint programming languages, it is essential that as much support as possible is available in these languages. This is already the case in the constructive search area of constraint programming where, e.g., different kinds of domain variables, such as integer variables and set variables, and expressive global constraints are readily available. However, in the local search area of constraint programming, this is not yet the case and, until now, set variables were for example not available. This thesis introduces set variables and set constraints in the local search area of constraint programming and, by doing this, considerably improves the possibilities for using local search. This is true both for modelling and solving problems using constraint-based local search, as well as for using it as a possible target for the compilation of ESRA models. Indeed, many combinatorial optimisation problems have natural models based on set variables and set constraints, three of which are successfully solved in this thesis.

    When a new set constraint is introduced in local search, much effort must be spent on the design and implementation of an appropriate incremental penalty function for the constraint. This thesis introduces a scheme that, from a high-level description of a set constraint in existential second-order logic with counting, automatically synthesises an incremental penalty function for that constraint. The performance of this scheme is demonstrated by solving real-life instances of a financial portfolio design problem that seem unsolvable in reasonable time by constructive search.

  • 811.
    Ågren, Magnus
    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.
    Set Constraints for Local Search2007Doctoral thesis, monograph (Other academic)
    Abstract [en]

    Combinatorial problems are ubiquitous in our society and solving such problems efficiently is often crucial. One technique for solving combinatorial problems is constraint-based local search. Its compositional nature together with its efficiency on large problem instances have made this technique particularly attractive. In this thesis we contribute to simplifying the solving of combinatorial problems using constraint-based local search.

    To provide higher-level modelling options, we introduce set variables and set constraints in local search by extending relevant local search concepts. We also propose a general scheme to follow in order to define what we call natural and balanced constraint measures, and accordingly define such measures for over a dozen set constraints. However, defining such measures for a new constraint is time-consuming and error-prone. To relieve the user from this, we provide generic measures for any set constraint modelled in monadic existential second-order logic. We also theoretically relate these measures to our proposed general scheme, and discuss implementation issues such as incremental algorithms and their worst-case complexities.

    To enable higher-level search algorithms, we introduce constraint-directed neighbourhoods in local search by proposing new constraint primitives for representing such neighbourhoods. Based on a constraint, possibly modelled in monadic existential second-order logic, these primitives return neighbourhoods with moves that are known in advance to achieve a decrease (or preservation, or increase) of the constraint measures, without the need to iterate over any other moves.

    We also present a framework for constraint-based local search where one can model and solve combinatorial problems with set variables and set constraints, use any set constraint modelled in monadic existential second-order logic, as well as use constraint-directed neighbourhoods. Experimental results on three real-life problems show the usefulness in practice of our theoretical results: our running times are comparable to the current state-of-the-art approaches to solving the considered problems.

  • 812.
    Ågren, Magnus
    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.
    Set Variables and Local Search2004Report (Other scientific)
    Abstract [en]

    Many combinatorial (optimisation) problems have natural models based on, or including, set variables and set constraints. This modelling device has been around for quite some time in the constraint programming area, and proved its usefulness in many applications. This paper introduces set variables and set constraints also in the local search area. It presents a way of representing set variables in the local search context, where we deal with concepts like transition functions, neighbourhoods, and penalty costs. Furthermore, some common set constraints and their penalty costs are defined. These constraints are later used to model three problems and some initial experimental results are reported.

  • 813.
    Ågren, Magnus
    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.
    Set variables and local search (Abstract)2004In: 10th International Conference on Principles and Practice of Constraint Programming: CP 2004, 2004, p. 788-Conference paper (Refereed)
  • 814.
    Ågren, Magnus
    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, Computer Systems.
    Generic incremental algorithms for local search2007In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 12, no 3, p. 293-324Article in journal (Refereed)
  • 815.
    Ågren, Magnus
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datalogi.
    Flener, Pierre
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datalogi.
    Pearson, Justin
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datorteknik.
    Incremental algorithms for local search from existential second-order logic2005In: Proceedings of Principles and Practice of Constraint Programming - CP 2005, 2005, p. 47-61Conference paper (Refereed)
    Abstract [en]

    Local search is a powerful and well-established method for solving hard combinatorial problems. Yet, until recently, it has provided very little user support, leading to time-consuming and error-prone implementation tasks. We introduce a scheme that, from a high-level description of a constraint in existential second-order logic with counting, automatically synthesises incremental penalty calculation algorithms. The performance of the scheme is demonstrated by solving real-life instances of a financial portfolio design problem that seem unsolvable in reasonable time by complete search.

  • 816.
    Ågren, Magnus
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datalogi.
    Flener, Pierre
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datalogi.
    Pearson, Justin
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datorteknik.
    Inferring variable conflicts for local search2006In: Principles and Practice of Constraint Programming - CP 2006: 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006. Proceedings, 2006Conference paper (Refereed)
    Abstract [en]

    For efficiency reasons, neighbourhoods in local search are often shrunk by only considering moves modifying variables that actually contribute to the overall penalty. These are known as conflicting variables. We propose a new definition for measuring the conflict of a variable in a model and apply it to the set variables of models expressed in existential second-order logic extended with counting (ESOL+). Such a variable conflict can be automatically and incrementally evaluated. Furthermore, this measure is lower-bounded by an intuitive conflict measure, and upper-bounded by the penalty of the model. We also demonstrate the usefulness of the approach by replacing a built-in global constraint by an ESOL+ version thereof, while still obtaining competitive results.

  • 817.
    Ågren, Magnus
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. CSD.
    Flener, Pierre
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. CSD.
    Pearson, Justin
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS.
    On Constraint-Oriented Neighbours for Local Search2007Report (Other scientific)
  • 818.
    Ågren, Magnus
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. CSD.
    Flener, Pierre
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. CSD.
    Pearson, Justin
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS.
    Revisiting constraint-directed search2007In: Proceedings of LSCS'07, the 4th International Workshop on Local Search Techniques in Constraint Satisfaction, 2007Conference paper (Refereed)
  • 819. Ågren, Magnus
    et al.
    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, Computer Systems.
    Revisiting constraint-directed search2009In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 207, no 3, p. 438-457Article in journal (Refereed)
  • 820.
    Ågren, Magnus
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datalogi.
    Flener, Pierre
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datalogi.
    Pearson, Justin
    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. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datorteknik.
    Set variables and local search2005In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: Second International Conference, CPAIOR 2005, Proceedings, 2005, p. 19-33Conference paper (Refereed)
  • 821.
    Åkerblom, Beatrice
    et al.
    Stockholm University.
    Castegren, Elias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Wrigstad, Tobias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Parallel Programming With Arrays in Kappa2018In: 5th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming, 2018Conference paper (Refereed)
  • 822.
    Åkerblom, Beatrice
    et al.
    Stockholm Univ, Stockholm, Sweden..
    Wrigstad, Tobias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Measuring Polymorphism in Python Programs2015In: Proc. 11th Symposium on Dynamic Languages, New York: ACM Press, 2015, p. 114-128Conference paper (Refereed)
    Abstract [en]

    Following the increased popularity of dynamic languages and their increased use in critical software, there have been many proposals to retrofit static type system to these languages to improve possibilities to catch bugs and improve performance. A key question for any type system is whether the types should be structural, for more expressiveness, or nominal, to carry more meaning for the programmer. For retrofitted type systems, it seems the current trend is using structural types. This paper attempts to answer the question to what extent this extra expressiveness is needed, and how the possible polymorphism in dynamic code is used in practise. We study polymorphism in 36 real-world open source Python programs and approximate to what extent nominal and structural types could be used to type these programs. The study is based on collecting traces from multiple runs of the programs and analysing the polymorphic degrees of targets at more than 7 million call-sites. Our results show that while polymorphism is used in all programs, the programs are to a great extent monomorphic. The polymorphism found is evenly distributed across libraries and program-specific code and occur both during program start-up and normal execution. Most programs contain a few ``megamorphic'' call-sites where receiver types vary widely. The non-monomorphic parts of the programs can to some extent be typed with nominal or structural types, but none of the approaches can type entire programs.

  • 823.
    Åman Pohjola, Johannes
    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.
    Bells and Whistles: Advanced language features in psi-calculi2013Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    Psi-calculi is a parametric framework for process calculi similar to popular pi-calculus extensions such as the explicit fusion calculus, the applied pi-calculus and the spi calculus. Remarkably, machine-checked proofs of standard algebraic and congruence properties of bisimilarity apply to every instance of the framework.

    The contribution of this licentiate thesis is to significantly extend the applicability and expressiveness of psi-calculi by incorporating several advanced language features into the framework: broadcasts, higher-order communication, generalised pattern matching, sorts and priorities. The extensions present several interesting technical challenges, such as negative premises. The machine-checked proofs for standard results about bisimilarity are generalised to each of these new settings, and the proof scripts are freely available online.

    List of papers
    1. Broadcast psi-calculi with an application to wireless protocols
    Open this publication in new window or tab >>Broadcast psi-calculi with an application to wireless protocols
    Show others...
    2015 (English)In: Software and Systems Modeling, ISSN 1619-1366, E-ISSN 1619-1374, Vol. 14, no 1, p. 201-216Article in journal (Refereed) Published
    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.

    Place, publisher, year, edition, pages
    Springer, 2015
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-205258 (URN)10.1007/s10270-013-0375-z (DOI)000349026100012 ()
    Projects
    UPMARCProFuN
    Funder
    Swedish Research Council, 2013-4853
    Available from: 2013-11-08 Created: 2013-08-15 Last updated: 2018-01-11Bibliographically approved
    2. Higher-order psi-calculi
    Open this publication in new window or tab >>Higher-order psi-calculi
    2014 (English)In: Mathematical Structures in Computer Science, ISSN 0960-1295, E-ISSN 1469-8072, Vol. 24, no 2, article id e240203Article in journal (Refereed) Published
    Abstract [en]

    Psi-calculi is a parametric framework for extensions of the pi-calculus; in earlier work we have explored their expressiveness and algebraic theory. In this paper we consider higher-order psi-calculi through a technically surprisingly simple extension of the framework, and show how an arbitrary psi-calculus can be lifted to its higher-order counterpart in a canonical way. We illustrate this with examples and establish an algebraic theory of higher-order psi-calculi. The formal results are obtained by extending our proof repositories in Isabelle/Nominal.

    Place, publisher, year, edition, pages
    Cambridge University Press, 2014
    Keywords
    process calculi, psi calculi, isabelle, theorem proving, nominal, higher-order
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-183610 (URN)10.1017/S0960129513000170 (DOI)000343643500003 ()
    Projects
    UPMARCProFuN
    Funder
    Swedish Foundation for Strategic Research
    Available from: 2013-06-24 Created: 2012-10-30 Last updated: 2018-01-12Bibliographically approved
    3. A Sorted Semantic Framework for Applied Process Calculi (extended abstract)
    Open this publication in new window or tab >>A Sorted Semantic Framework for Applied Process Calculi (extended abstract)
    Show others...
    2014 (English)In: Trustworthy Global Computing: TGC 2013, Springer Berlin/Heidelberg, 2014, p. 103-118Conference paper, Published 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.

    Place, publisher, year, edition, pages
    Springer Berlin/Heidelberg, 2014
    Series
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 8358
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-203382 (URN)10.1007/978-3-319-05119-2_7 (DOI)978-3-319-05118-5 (ISBN)
    Conference
    8th International Symposium on Trustworthy Global Computing, August 30-31, 2013, Buenos Aires, Argentina
    Projects
    UPMARCProFuN
    Funder
    Swedish Foundation for Strategic Research , RIT08­0065
    Available from: 2014-03-08 Created: 2013-07-09 Last updated: 2018-01-11
    4. Negative premises in applied process calculi
    Open this publication in new window or tab >>Negative premises in applied process calculi
    Show others...
    2013 (English)Report (Other academic)
    Series
    Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2013-014
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-229004 (URN)
    Available from: 2013-06-20 Created: 2014-07-25 Last updated: 2018-01-11Bibliographically approved
    5. Bisimulation up-to techniques for psi-calculi
    Open this publication in new window or tab >>Bisimulation up-to techniques for psi-calculi
    2016 (English)In: Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs / [ed] Avigad, J; Chlipala, A, New York: ACM Press, 2016, p. 142-153Conference paper, Published paper (Refereed)
    Abstract [en]

    Psi-calculi is a parametric framework for process calculi similar to popular pi-calculus extensions such as the explicit fusion calculus, the applied pi-calculus and the spi calculus. Remarkably, machine-checked proofs of standard algebraic and congruence properties of bisimilarity apply to all calculi within the framework. Bisimulation up-to techniques are methods for reducing the size of relations needed in bisimulation proofs. In this paper, we show how these bisimulation proof methods can be adapted to psi-calculi. We formalise all our definitions and theorems in Nominal Isabelle, and show examples where the use of up to-techniques yields drastically simplified proofs of known results. We also prove new structural laws about the replication operator.

    Place, publisher, year, edition, pages
    New York: ACM Press, 2016
    Keywords
    Bisimulation up-to, process calculus, psi-calculi, Isabelle, Nominal Isabelle, nominal logic
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-229008 (URN)10.1145/2854065.2854080 (DOI)000389021600016 ()9781450341271 (ISBN)
    Conference
    CPP 2016, January 18–19, Saint Petersburg, FL
    Available from: 2016-01-18 Created: 2014-07-25 Last updated: 2018-01-11Bibliographically approved
  • 824.
    Åman Pohjola, Johannes
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Culling Concurrency Theory: Reusable and trustworthy meta-theory, proof techniques and separation results2016Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    As concurrent systems become ever more complex and ever more ubiquitous, the need to understand and verify them grows ever larger. For this we need formal modelling languages that are well understood, with rigorously verified foundations and proof techniques, applicable to a wide variety of concurrent systems.

    Defining modelling languages is easy; there is a stupefying variety of them in the literature. Verifying their foundations and proof techniques, and developing an understanding of their interrelationship with other modelling languages, is difficult, tedious and error-prone. The contributions of this thesis support these tasks in reusable and trustworthy ways, by results that apply to a wide variety of modelling languages, verified to the highest standards of mathematical rigour in an interactive theorem prover.

    To this end, we extend psi-calculi - a family of process calculi with reusable foundations for formal verification - with several new language features. We prove that the bisimulation meta-theory of psi-calculi carries over to these extended settings. This widens the scope of psi-calculi to important application areas, such as cryptography and wireless communication. We develop bisimulation up-to techniques - powerful proof techniques for showing that two processes exhibit the same observable behaviour - that apply to all psi-calculi. By showing how psi-calculi can encode dynamic priorities under very strong quality criteria, we demonstrate that the expressive power is greater than previously thought. Finally, we develop a simple and widely applicable technique for showing that a process calculus adds expressiveness over another, based on little more than whether parallel components may act independently or not. Many separation results, both novel ones and strengthenings of known results from the literature, emerge as special cases of this technique.

    List of papers
    1. Broadcast psi-calculi with an application to wireless protocols
    Open this publication in new window or tab >>Broadcast psi-calculi with an application to wireless protocols
    Show others...
    2015 (English)In: Software and Systems Modeling, ISSN 1619-1366, E-ISSN 1619-1374, Vol. 14, no 1, p. 201-216Article in journal (Refereed) Published
    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.

    Place, publisher, year, edition, pages
    Springer, 2015
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-205258 (URN)10.1007/s10270-013-0375-z (DOI)000349026100012 ()
    Projects
    UPMARCProFuN
    Funder
    Swedish Research Council, 2013-4853
    Available from: 2013-11-08 Created: 2013-08-15 Last updated: 2018-01-11Bibliographically approved
    2. Higher-order psi-calculi
    Open this publication in new window or tab >>Higher-order psi-calculi
    2014 (English)In: Mathematical Structures in Computer Science, ISSN 0960-1295, E-ISSN 1469-8072, Vol. 24, no 2, article id e240203Article in journal (Refereed) Published
    Abstract [en]

    Psi-calculi is a parametric framework for extensions of the pi-calculus; in earlier work we have explored their expressiveness and algebraic theory. In this paper we consider higher-order psi-calculi through a technically surprisingly simple extension of the framework, and show how an arbitrary psi-calculus can be lifted to its higher-order counterpart in a canonical way. We illustrate this with examples and establish an algebraic theory of higher-order psi-calculi. The formal results are obtained by extending our proof repositories in Isabelle/Nominal.

    Place, publisher, year, edition, pages
    Cambridge University Press, 2014
    Keywords
    process calculi, psi calculi, isabelle, theorem proving, nominal, higher-order
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-183610 (URN)10.1017/S0960129513000170 (DOI)000343643500003 ()
    Projects
    UPMARCProFuN
    Funder
    Swedish Foundation for Strategic Research
    Available from: 2013-06-24 Created: 2012-10-30 Last updated: 2018-01-12Bibliographically approved
    3. A Sorted Semantic Framework for Applied Process Calculi
    Open this publication in new window or tab >>A Sorted Semantic Framework for Applied Process Calculi
    Show others...
    2016 (English)In: 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) Published
    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.

    Keywords
    Expressiveness, Pattern matching, Type systems, Theorem proving, pi-calculus, Nominal sets
    National Category
    Computer Sciences
    Research subject
    Computer Science
    Identifiers
    urn:nbn:se:uu:diva-262199 (URN)10.2168/LMCS-12(1:8)2016 (DOI)000374769600004 ()
    Projects
    UPMARC
    Funder
    Swedish Research Council, 2013-4853
    Available from: 2016-03-31 Created: 2015-09-09 Last updated: 2019-02-25Bibliographically approved
    4. Priorities Without Priorities: Representing Preemption in Psi-Calculi
    Open this publication in new window or tab >>Priorities Without Priorities: Representing Preemption in Psi-Calculi
    2014 (English)In: Proc. 21st International Workshop on Expressiveness in Concurrency, and 11th Workshop on Structural Operational Semantics, 2014, p. 2-15Conference paper, Published paper (Refereed)
    Series
    Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180 ; 160
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-297468 (URN)10.4204/EPTCS.160.2 (DOI)
    Conference
    EXPRESS/SOS 2014, September 1st, Rome, Italy
    Available from: 2014-08-07 Created: 2016-06-23 Last updated: 2018-01-10Bibliographically approved
    5. Bisimulation up-to techniques for psi-calculi
    Open this publication in new window or tab >>Bisimulation up-to techniques for psi-calculi
    2016 (English)In: Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs / [ed] Avigad, J; Chlipala, A, New York: ACM Press, 2016, p. 142-153Conference paper, Published paper (Refereed)
    Abstract [en]

    Psi-calculi is a parametric framework for process calculi similar to popular pi-calculus extensions such as the explicit fusion calculus, the applied pi-calculus and the spi calculus. Remarkably, machine-checked proofs of standard algebraic and congruence properties of bisimilarity apply to all calculi within the framework. Bisimulation up-to techniques are methods for reducing the size of relations needed in bisimulation proofs. In this paper, we show how these bisimulation proof methods can be adapted to psi-calculi. We formalise all our definitions and theorems in Nominal Isabelle, and show examples where the use of up to-techniques yields drastically simplified proofs of known results. We also prove new structural laws about the replication operator.

    Place, publisher, year, edition, pages
    New York: ACM Press, 2016
    Keywords
    Bisimulation up-to, process calculus, psi-calculi, Isabelle, Nominal Isabelle, nominal logic
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-229008 (URN)10.1145/2854065.2854080 (DOI)000389021600016 ()9781450341271 (ISBN)
    Conference
    CPP 2016, January 18–19, Saint Petersburg, FL
    Available from: 2016-01-18 Created: 2014-07-25 Last updated: 2018-01-11Bibliographically approved
    6. The Expressive Power of Monotonic Parallel Composition
    Open this publication in new window or tab >>The Expressive Power of Monotonic Parallel Composition
    2016 (English)In: Programming Languages and Systems, Berlin: Springer, 2016, p. 780-803Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Berlin: Springer, 2016
    Series
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9632
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-297465 (URN)10.1007/978-3-662-49498-1_30 (DOI)000401936100030 ()978-3-662-49497-4 (ISBN)
    Conference
    ESOP 2016, April 3–7, Eindhoven, The Netherlands
    Available from: 2016-03-22 Created: 2016-06-23 Last updated: 2018-01-10Bibliographically approved
  • 825.
    Åman Pohjola, Johannes
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Borgström, 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.
    Raabjerg, Palle
    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.
    Negative premises in applied process calculi2013Report (Other academic)
  • 826.
    Åman Pohjola, Johannes
    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.
    Bisimulation up-to techniques for psi-calculi2016In: Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs / [ed] Avigad, J; Chlipala, A, New York: ACM Press, 2016, p. 142-153Conference paper (Refereed)
    Abstract [en]

    Psi-calculi is a parametric framework for process calculi similar to popular pi-calculus extensions such as the explicit fusion calculus, the applied pi-calculus and the spi calculus. Remarkably, machine-checked proofs of standard algebraic and congruence properties of bisimilarity apply to all calculi within the framework. Bisimulation up-to techniques are methods for reducing the size of relations needed in bisimulation proofs. In this paper, we show how these bisimulation proof methods can be adapted to psi-calculi. We formalise all our definitions and theorems in Nominal Isabelle, and show examples where the use of up to-techniques yields drastically simplified proofs of known results. We also prove new structural laws about the replication operator.

  • 827.
    Åman Pohjola, Johannes
    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.
    Priorities Without Priorities: Representing Preemption in Psi-Calculi2014In: Proc. 21st International Workshop on Expressiveness in Concurrency, and 11th Workshop on Structural Operational Semantics, 2014, p. 2-15Conference paper (Refereed)
  • 828.
    Åman Pohjola, Johannes
    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.
    The Expressive Power of Monotonic Parallel Composition2016In: Programming Languages and Systems, Berlin: Springer, 2016, p. 780-803Conference paper (Refereed)
  • 829.
    Östlund, Johan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Language Constructs for Safe Parallel Programming on Multi-Cores2016Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    The last decade has seen the transition from single-core processors to multi-cores and many-cores. This move has by and large shifted the responsibility from chip manufacturers to programmers to keep up with ever-increasing expectations on performance. In the single-core era, improvements in hardware capacity could immediately be leveraged by an application: faster machine - faster program. In the age of the multi-cores, this is no longer the case. Programs must be written in specific ways to utilize available parallel hardware resources.

    Programming language support for concurrent and parallel programming is poor in most popular object-oriented programming languages. Shared memory, threads and locks is the most common concurrency model provided. Threads and locks are hard to understand, error-prone and inflexible; they break encapsulation - the very foundation of the object-oriented approach. This makes it hard to break large complex problems into smaller pieces which can be solved independently and composed to make a whole. Ubiquitous parallelism and object-orientation, seemingly, do not match.

    Actors, or active objects, have been proposed as a concurrency model better fit for object-oriented programming than threads and locks. Asynchronous message passing between actors each with a logical thread of control preserves encapsulation as objects themselves decide when messages are executed. Unfortunately most implementations of active objects do not prevent sharing of mutable objects across actors. Sharing, whether on purpose or by accident, exposes objects to multiple threads of control, destroying object encapsulation.

    In this thesis we show techniques for compiler-enforced isolation of active objects, while allowing sharing and zero-copy communication of mutable data in the cases where it is safe to do so. We also show how the same techniques that enforce isolation can be utilized internal to an active object to allow data race-free parallel message processing and data race-free structured parallel computations. This overcomes the coarse-grained nature of active object parallelism without compromising safety.

    List of papers
    1. Ownership, Uniqueness, and Immutability
    Open this publication in new window or tab >>Ownership, Uniqueness, and Immutability
    2008 (English)In: Lecture Notes in Business Information Processing, ISSN 1865-1348, E-ISSN 1865-1356Article in journal (Refereed) Published
    Abstract [en]

    Programming in an object-oriented language demands a fine balance between flexibility and control. At one level, objects need to interact freely to achieve our implementation goals. At a higher level, architectural constraints that ensure the system can be understood by new developers and can evolve as requirements change must be met. To resolve this tension, researchers have developed type systems expressing ownership and behavioural restrictions such as immutability. This work reports on our consolidation of the resulting discoveries into a single programming language. Our language, Joe 3 , imposes little additional syntactic overhead, yet can encode powerful patterns such as fractional permissions and the reference modes of Flexible Alias Protection.

    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-266671 (URN)10.1007/978-3-540-69824-1_11 (DOI)
    Conference
    46th International Conference, TOOLS EUROPE 2008, Zurich, Switzerland, June 30 - July 4, 2008.
    Available from: 2015-11-10 Created: 2015-11-10 Last updated: 2018-01-10
    2. Minimal Ownership for Active Objects
    Open this publication in new window or tab >>Minimal Ownership for Active Objects
    2008 (English)In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349Article in journal (Refereed) Published
    Abstract [en]

    Active objects offer a structured approach to concurrency, encapsulating both unshared state and a thread of control. For efficient data transfer, data should be passed by reference whenever possible, but this introduces aliasing and undermines the validity of the active objects. This paper proposes a minimal variant of ownership types that preserves the required race freedom invariant yet enables data transfer by reference between active objects (that is, without copying) in many cases, and a cheap clone operation where copying is necessary. Our approach is general and should be adaptable to several existing active object systems.

    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-266793 (URN)10.1007/978-3-540-89330-1_11 (DOI)
    Conference
    6th Asian Symposium, APLAS 2008, Bangalore, India, December 9-11, 2008
    Projects
    EU project IST-33826 CREDO
    Available from: 2015-11-10 Created: 2015-11-10 Last updated: 2018-01-10
    3. Welterweight Java
    Open this publication in new window or tab >>Welterweight Java
    2010 (English)In: Objects, Models, Components, Patterns / [ed] Vitek, Jan, Berlin: Springer-Verlag , 2010, p. 97-116Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Berlin: Springer-Verlag, 2010
    Series
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 6141
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-130897 (URN)10.1007/978-3-642-13953-6_6 (DOI)000286162000006 ()978-3-642-13952-9 (ISBN)
    Conference
    48th International Conference, TOOLS 2010
    Projects
    UPMARCFacilitating Concurrent and Parallel Programming in Mainstream Programming Languages
    Available from: 2010-09-17 Created: 2010-09-17 Last updated: 2018-01-12Bibliographically approved
    4. Multiple Aggregate Entry Points for Ownership Types
    Open this publication in new window or tab >>Multiple Aggregate Entry Points for Ownership Types
    2012 (English)In: ECOOP 2012 – Object-Oriented Programming, Springer Berlin/Heidelberg, 2012, p. 156-180Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Springer Berlin/Heidelberg, 2012
    Series
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 7313
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-176660 (URN)10.1007/978-3-642-31057-7_8 (DOI)978-3-642-31056-0 (ISBN)
    Conference
    26th European Conference on Object-Oriented Programming
    Projects
    UPMARCFacilitating Concurrent and Parallel Programming in Mainstream Programming Languages
    Available from: 2012-06-28 Created: 2012-06-21 Last updated: 2018-01-12Bibliographically approved
    5. Refined Ownership: Fine-grained controlled internal sharing
    Open this publication in new window or tab >>Refined Ownership: Fine-grained controlled internal sharing
    2015 (English)In: Formal Methods for Multicore Programming, 2015, Vol. 9104, p. 179-210Conference paper, Published paper (Refereed)
    Abstract [en]

    Ownership type systems give a strong notion of separation between aggregates. Objects belonging to different owners cannot be aliased, and thus a mutating operation internal to one object is guaranteed to be invisible to another. This naturally facilitates reasoning about correctness on a local scale, but also proves beneficial for coarse-grained parallelism as noninterference between statements touching different objects is easily established. For fine-grained parallelism, ownership types fall short as owner-based disjointness only allows separation of the innards of different aggregates, which is very coarse-grained. Concretely: ownership types can reason about the disjointness of two different data structures, but cannot reason about the internal structure or disjointness within the data structure, without resorting to static and overly constraining measures. For similar reasons, ownership fails to determine internal disjointness of external pointers to objects that share a common owner. In this paper, we introduce the novel notion of refined ownership which overcomes these limitations by allowing precise local reasoning about a group of objects even though they belong to the same external owner. Using refined ownership, we can statically check determinism of parallel operations on tree-shaped substructures of a data structure, including operations on values external to the structure, without imposing any non-local alias restrictions.

    Series
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9104
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-266673 (URN)10.1007/978-3-319-18941-3_5 (DOI)000362511600005 ()978-3-319-18941-3 (ISBN)978-3-319-18940-6 (ISBN)
    Conference
    15th International School on Formal Methods for the Design of Computer, Communication, and Software Systems; SFM 2015, June 15–19, Bertinoro, Italy
    Projects
    UPMARCUPSCALE
    Available from: 2015-05-07 Created: 2015-11-10 Last updated: 2018-01-10Bibliographically approved
  • 830.
    Östlund, Johan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Brandauer, Stephan
    Wrigstad, Tobias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    The Joelle Programming Language: Evolving Java Programs Along Two Axes of Parallel Eval2012Conference paper (Other academic)
  • 831.
    Östlund, Johan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Wrigstad, Tobias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Multiple Aggregate Entry Points for Ownership Types2012In: ECOOP 2012 – Object-Oriented Programming, Springer Berlin/Heidelberg, 2012, p. 156-180Conference paper (Refereed)
  • 832.
    Östlund, Johan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Wrigstad, Tobias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Regions as Owners: A Discussion on Ownership-based Effects in Practice2011Conference paper (Refereed)
  • 833.
    Östlund, Johan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Wrigstad, Tobias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Welterweight Java2010In: Objects, Models, Components, Patterns / [ed] Vitek, Jan, Berlin: Springer-Verlag , 2010, p. 97-116Conference paper (Refereed)
14151617 801 - 833 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