uu.seUppsala universitets publikationer
Ändra sökning
Avgränsa sökresultatet
14151617 801 - 838 av 838
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 801.
    You, Lei
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Yuan, Di
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Joint CoMP-Cell Selection and Resource Allocation in Fronthaul-Constrained C-RAN2017Ingår i: Proc. 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, IEEE, 2017Konferensbidrag (Refereegranskat)
  • 802.
    You, Lei
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Yuan, Di
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    User-centric Performance Optimization with Remote Radio Head Cooperation in C-RAN2017Manuskript (preprint) (Övrigt vetenskapligt)
  • 803.
    You, Lei
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Yuan, Di
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Lei, Lei
    Sun, Sumei
    Chatzinotas, Symeon
    Ottersten, Björn
    Resource optimization with load coupling in multi-cell NOMA2018Ingår i: IEEE Transactions on Wireless Communications, ISSN 1536-1276, E-ISSN 1558-2248, Vol. 17, nr 7, s. 4735-4749Artikel i tidskrift (Refereegranskat)
  • 804.
    You, Lei
    et al.
    Linkoping Univ, Dept Sci & Technol, S-60174 Linkoping, Sweden..
    Yuan, Di
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi. Linkoping Univ, Dept Sci & Technol, S-60174 Linkoping, Sweden..
    Pappas, Nikolaos
    Linkoping Univ, Dept Sci & Technol, S-60174 Linkoping, Sweden..
    Varbrand, Peter
    Linkoping Univ, Dept Sci & Technol, S-60174 Linkoping, Sweden..
    Energy-Aware Wireless Relay Selection in Load-Coupled OFDMA Cellular Networks2017Ingår i: IEEE Communications Letters, ISSN 1089-7798, E-ISSN 1558-2558, Vol. 21, nr 1, s. 144-147Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We investigate transmission energy minimization via optimizing wireless relay selection in orthogonal-frequency-division multiple access networks. We take into account the impact of the load of cells on transmission energy. We prove the NP-hardness of the energy-aware wireless relay selection problem. To tackle computational complexity, a partial optimality condition is derived for providing insights in respect of designing an effective and efficient algorithm. Numerical results show the resulting algorithm achieves high energy performance.

  • 805.
    Zeitler, Erik
    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.
    Scalable Parallelization of Expensive Continuous Queries over Massive Data Streams2011Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    Numerous applications in for example science, engineering, and financial analysis increasingly require online analysis over streaming data. These data streams are often of such a high rate that saving them to disk is not desirable or feasible. Therefore, search and analysis must be performed directly over the data in motion. Such on-line search and analysis can be expressed as continuous queries (CQs) that are defined over the streams. The result of a CQ is a stream itself, which is continuously updated as new data appears in the queried stream(s). In many cases, the applications require non-trivial analysis, leading to CQs involving expensive processing. To provide scalability of such expensive CQs over high-volume streams, the execution of the CQs must be parallelized.

    In order to investigate different approaches to parallel execution of CQs, a parallel data stream management system called SCSQ was implemented for this Thesis. Data and queries from space physics and traffic management applications are used in the evaluations, as well as synthetic data and the standard data stream benchmark; the Linear Road Benchmark. Declarative parallelization functions are introduced into the query language of SCSQ, allowing the user to specify customized parallelization. In particular, declarative stream splitting functions are introduced, which split a stream into parallel sub-streams, over which expensive CQ operators are continuously executed in parallel.

    Naïvely implemented, stream splitting becomes a bottleneck if the input streams are of high volume, if the CQ operators are massively parallelized, or if the stream splitting conditions are expensive. To eliminate this bottleneck, different approaches are investigated to automatically generate parallel execution plans for stream splitting functions. This Thesis shows that by parallelizing the stream splitting itself, expensive CQs can be processed at stream rates close to network speed. Furthermore, it is demonstrated how parallelized stream splitting allows orders of magnitude higher stream rates than any previously published results for the Linear Road Benchmark.

     

    Delarbeten
    1. Processing High-Volume Stream Queries on a Supercomputer
    Öppna denna publikation i ny flik eller fönster >>Processing High-Volume Stream Queries on a Supercomputer
    2006 (Engelska)Ingår i: Processing High-Volume Stream Queries on a Supercomputer, 2006, s. 147-Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-20450 (URN)0-7695-2571-7 (ISBN)
    Tillgänglig från: 2006-12-22 Skapad: 2006-12-22 Senast uppdaterad: 2018-01-12
    2. Using stream queries to measure communication performance of a parallel computing environment
    Öppna denna publikation i ny flik eller fönster >>Using stream queries to measure communication performance of a parallel computing environment
    2007 (Engelska)Ingår i: Proc. 1st International Workshop on Distributed Event Processing, Systems and Applications (DEPSA’07), 2007Konferensbidrag, Publicerat paper (Refereegranskat)
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-10187 (URN)
    Tillgänglig från: 2008-02-04 Skapad: 2008-02-04 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
    3. Highly Scalable Trip Grouping for Large Scale Collective Transportation Systems
    Öppna denna publikation i ny flik eller fönster >>Highly Scalable Trip Grouping for Large Scale Collective Transportation Systems
    2008 (Engelska)Ingår i: Proc. 11th International Conference on Extending Database Technology, EDBT 2008, 2008Konferensbidrag, Publicerat paper (Refereegranskat)
    Abstract [en]

    Transportation–related problems, like road congestion, park-ing, and pollution are increasing in most cities. In order toreduce traffic, recent work has proposed methods for vehiclesharing, for example for sharing cabs by grouping “closeby”cab requests and thus minimizing transportation cost andutilizing cab space. However, the methods proposed so fardo not scale to large data volumes, which is necessary tofacilitate large scale collective transportation systems, e.g.,ride–sharing systems for large cities.This paper presents highly scalable “trip grouping” algo-rithms, that generalize previous techniques and support in-put rates that can be orders of magnitude larger. The follow-ing three contributions make the grouping algorithms scal-able. First, the basic grouping algorithm is expressed as acontinuous stream query in a data stream management sys-tem to allow for very large flows of requests. Second, follow-ing the divide–and–conquer paradigm, four space–partition-ing policies for dividing the input data stream into sub–streams are developed and implemented using continuousstream queries. Third, using the partitioning policies, par-allel implementations of the grouping algorithm in a paral-lel computing environment are described. Extensive experi-mental results show that the parallel implementation usingsimple adaptive partitioning methods can achieve speed–upsof several orders of magnitudes without significantly effect-ing the quality of the grouping.

    Nationell ämneskategori
    Datavetenskap (datalogi) Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-103534 (URN)
    Projekt
    iStreams
    Tillgänglig från: 2009-05-19 Skapad: 2009-05-19 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
    4. Scalable Splitting of Massive Data Streams
    Öppna denna publikation i ny flik eller fönster >>Scalable Splitting of Massive Data Streams
    2010 (Engelska)Ingår i: Database Systems for Advanced Applications: Part II / [ed] Kitagawa H., Ishikawa Y., Li Q., Watanabe C., Berlin: Springer-Verlag , 2010, s. 184-198Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Ort, förlag, år, upplaga, sidor
    Berlin: Springer-Verlag, 2010
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 5982
    Nyckelord
    distributed stream systems, parallelization, query optimization
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-136403 (URN)10.1007/978-3-642-12098-5_15 (DOI)000278934800015 ()978-3-642-12097-8 (ISBN)
    Konferens
    15th International Conference, DASFAA 2010, Tsukuba, Japan, April 1-4, 2010
    Projekt
    iStreamseSSENCE
    Tillgänglig från: 2010-12-14 Skapad: 2010-12-13 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
    5. Massive scale-out of expensive continuous queries
    Öppna denna publikation i ny flik eller fönster >>Massive scale-out of expensive continuous queries
    2011 (Engelska)Ingår i: 36th International Conference on Very Large Data Bases: VLDB 2010, 2011Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Nationell ämneskategori
    Datavetenskap (datalogi) Datavetenskap (datalogi)
    Forskningsämne
    Datavetenskap med inriktning mot databasteknik
    Identifikatorer
    urn:nbn:se:uu:diva-152251 (URN)
    Projekt
    iStreams
    Tillgänglig från: 2011-04-27 Skapad: 2011-04-27 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
  • 806.
    Zeitler, Erik
    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. CSD.
    Working with Stella2006Ingår i: Astronnews, ISSN 1871-6644, nr 1, s. 12-13Artikel i tidskrift (Övrig (populärvetenskap, debatt, mm))
  • 807.
    Zeitler, Erik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Risch, Tore
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Massive scale-out of expensive continuous queries2011Ingår i: 36th International Conference on Very Large Data Bases: VLDB 2010, 2011Konferensbidrag (Refereegranskat)
    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.

  • 808.
    Zeitler, Erik
    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. CSD.
    Risch, Tore
    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. CSD.
    Processing High-Volume Stream Queries on a Supercomputer2006Ingår i: Processing High-Volume Stream Queries on a Supercomputer, 2006, s. 147-Konferensbidrag (Refereegranskat)
    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.

  • 809.
    Zeitler, Erik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Risch, Tore
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Scalable Splitting of Massive Data Streams2010Ingår i: Database Systems for Advanced Applications: Part II / [ed] Kitagawa H., Ishikawa Y., Li Q., Watanabe C., Berlin: Springer-Verlag , 2010, s. 184-198Konferensbidrag (Refereegranskat)
    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.

  • 810.
    Zeitler, Erik
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Risch, Tore
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Using stream queries to measure communication performance of a parallel computing environment2007Ingår i: Proc. 1st International Workshop on Distributed Event Processing, Systems and Applications (DEPSA’07), 2007Konferensbidrag (Refereegranskat)
  • 811.
    Zeljić, Aleksandar
    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, Datalogi.
    From Machine Arithmetic to Approximations and back again: Improved SMT Methods for Numeric Data Types2017Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    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.

    Delarbeten
    1. Deciding bit-vector formulas with mcSAT
    Öppna denna publikation i ny flik eller fönster >>Deciding bit-vector formulas with mcSAT
    2016 (Engelska)Ingår i: Theory and Applications of Satisfiability Testing: SAT 2016, Springer, 2016, s. 249-266Konferensbidrag, Publicerat paper (Refereegranskat)
    Ort, förlag, år, upplaga, sidor
    Springer, 2016
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9710
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-305182 (URN)10.1007/978-3-319-40970-2_16 (DOI)000387430600016 ()978-3-319-40969-6 (ISBN)
    Konferens
    SAT 2016, July 5–8, Bordeaux, France
    Projekt
    UPMARC
    Tillgänglig från: 2016-06-11 Skapad: 2016-10-12 Senast uppdaterad: 2018-01-14Bibliografiskt granskad
    2. An approximation framework for solvers and decision procedures
    Öppna denna publikation i ny flik eller fönster >>An approximation framework for solvers and decision procedures
    2017 (Engelska)Ingår i: Journal of automated reasoning, ISSN 0168-7433, E-ISSN 1573-0670, Vol. 58, nr 1, s. 127-147Artikel i tidskrift (Refereegranskat) Published
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-305180 (URN)10.1007/s10817-016-9393-1 (DOI)000392387400006 ()
    Projekt
    UPMARC
    Tillgänglig från: 2016-11-10 Skapad: 2016-10-12 Senast uppdaterad: 2018-01-14Bibliografiskt granskad
    3. Exploring Approximations for Floating-Point Arithmetic using UppSAT
    Öppna denna publikation i ny flik eller fönster >>Exploring Approximations for Floating-Point Arithmetic using UppSAT
    (Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
    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).

    Nyckelord
    SAT, SMT, approximations, model construction, floating-point arithmetic
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Forskningsämne
    Datavetenskap
    Identifikatorer
    urn:nbn:se:uu:diva-334564 (URN)
    Tillgänglig från: 2017-11-24 Skapad: 2017-11-24 Senast uppdaterad: 2018-01-13
  • 812.
    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 universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    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 Caching2019Ingår i: IEEE Internet of Things Journal, ISSN 2327-4662, Vol. 6, nr 3, s. 4283-4294Artikel i tidskrift (Refereegranskat)
    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.

  • 813.
    Zhu, Minpeng
    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.
    Scalable Queries over Log Database Collections2016Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    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.

    Delarbeten
    1. Querying Combined Cloud-Based and Relational Databases
    Öppna denna publikation i ny flik eller fönster >>Querying Combined Cloud-Based and Relational Databases
    2011 (Engelska)Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Nyckelord
    cloud data repository; relational database; data integration; Bigtable;
    Nationell ämneskategori
    Data- och informationsvetenskap
    Identifikatorer
    urn:nbn:se:uu:diva-275026 (URN)10.1109/CSC.2011.6138543 (DOI)
    Konferens
    2011 International Conference on Cloud and Service Computing (CSC)
    Tillgänglig från: 2016-01-28 Skapad: 2016-01-28 Senast uppdaterad: 2018-01-10
    2. Scalable Numerical SPARQL Queries over Relational Databases
    Öppna denna publikation i ny flik eller fönster >>Scalable Numerical SPARQL Queries over Relational Databases
    2014 (Engelska)Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Nationell ämneskategori
    Data- och informationsvetenskap
    Identifikatorer
    urn:nbn:se:uu:diva-275027 (URN)
    Konferens
    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
    Tillgänglig från: 2016-01-28 Skapad: 2016-01-28 Senast uppdaterad: 2018-01-10
    3. Scalable queries over log database collections
    Öppna denna publikation i ny flik eller fönster >>Scalable queries over log database collections
    2015 (Engelska)Ingår i: Data Science, Springer, 2015, s. 173-185Konferensbidrag, Publicerat paper (Refereegranskat)
    Ort, förlag, år, upplaga, sidor
    Springer, 2015
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9147
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-274784 (URN)10.1007/978-3-319-20424-6_17 (DOI)000364104600017 ()978-3-319-20423-9 (ISBN)
    Konferens
    BICOD 2015, July 6–8, Edinburgh, UK
    Tillgänglig från: 2015-06-11 Skapad: 2016-01-26 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
    4. Utilizing a NoSQL Data Store for Scalable Log Analysis
    Öppna denna publikation i ny flik eller fönster >>Utilizing a NoSQL Data Store for Scalable Log Analysis
    2015 (Engelska)Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Nationell ämneskategori
    Data- och informationsvetenskap
    Identifikatorer
    urn:nbn:se:uu:diva-275028 (URN)10.1145/2790755.2790772 (DOI)978-1-4503-3414-3 (ISBN)
    Konferens
    19th International Database Engineering & Applications Symposium (IDEAS 2015), Yokohama, Japan, July 13-15, 2015
    Tillgänglig från: 2016-01-28 Skapad: 2016-01-28 Senast uppdaterad: 2018-01-10
  • 814.
    Zhu, Minpeng
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Mahmood, Khalid
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Risch, Tore
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Scalable queries over log database collections2015Ingår i: Data Science, Springer, 2015, s. 173-185Konferensbidrag (Refereegranskat)
  • 815.
    Ågren, Magnus
    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.
    High-level modelling and local search2005Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
    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.

  • 816.
    Ågren, Magnus
    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.
    Set Constraints for Local Search2007Doktorsavhandling, monografi (Övrigt vetenskapligt)
    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.

  • 817.
    Ågren, Magnus
    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.
    Set Variables and Local Search2004Rapport (Övrigt vetenskapligt)
    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.

  • 818.
    Ågren, Magnus
    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.
    Set variables and local search (Abstract)2004Ingår i: 10th International Conference on Principles and Practice of Constraint Programming: CP 2004, 2004, s. 788-Konferensbidrag (Refereegranskat)
  • 819.
    Ågren, Magnus
    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, Datorteknik.
    Generic incremental algorithms for local search2007Ingår i: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 12, nr 3, s. 293-324Artikel i tidskrift (Refereegranskat)
  • 820.
    Ågren, Magnus
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datalogi.
    Flener, Pierre
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datalogi.
    Pearson, Justin
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datorteknik.
    Incremental algorithms for local search from existential second-order logic2005Ingår i: Proceedings of Principles and Practice of Constraint Programming - CP 2005, 2005, s. 47-61Konferensbidrag (Refereegranskat)
    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.

  • 821.
    Ågren, Magnus
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datalogi.
    Flener, Pierre
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datalogi.
    Pearson, Justin
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datorteknik.
    Inferring variable conflicts for local search2006Ingår i: Principles and Practice of Constraint Programming - CP 2006: 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006. Proceedings, 2006Konferensbidrag (Refereegranskat)
    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.

  • 822.
    Ågren, Magnus
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. CSD.
    Flener, Pierre
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. CSD.
    Pearson, Justin
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. DoCS.
    On Constraint-Oriented Neighbours for Local Search2007Rapport (Övrigt vetenskapligt)
  • 823.
    Ågren, Magnus
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. CSD.
    Flener, Pierre
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. CSD.
    Pearson, Justin
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. DoCS.
    Revisiting constraint-directed search2007Ingår i: Proceedings of LSCS'07, the 4th International Workshop on Local Search Techniques in Constraint Satisfaction, 2007Konferensbidrag (Refereegranskat)
  • 824. Ågren, Magnus
    et al.
    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, Datorteknik.
    Revisiting constraint-directed search2009Ingår i: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 207, nr 3, s. 438-457Artikel i tidskrift (Refereegranskat)
  • 825.
    Ågren, Magnus
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datalogi.
    Flener, Pierre
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datalogi.
    Pearson, Justin
    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. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datorteknik.
    Set variables and local search2005Ingår i: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: Second International Conference, CPAIOR 2005, Proceedings, 2005, s. 19-33Konferensbidrag (Refereegranskat)
  • 826.
    Åkerblom, Beatrice
    et al.
    Stockholm University.
    Castegren, Elias
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Wrigstad, Tobias
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Parallel Programming With Arrays in Kappa2018Ingår i: 5th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming, 2018Konferensbidrag (Refereegranskat)
  • 827.
    Åkerblom, Beatrice
    et al.
    Stockholm Univ, Stockholm, Sweden..
    Wrigstad, Tobias
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Measuring Polymorphism in Python Programs2015Ingår i: Proc. 11th Symposium on Dynamic Languages, New York: ACM Press, 2015, s. 114-128Konferensbidrag (Refereegranskat)
    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.

  • 828.
    Åman Pohjola, Johannes
    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.
    Bells and Whistles: Advanced language features in psi-calculi2013Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
    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.

    Delarbeten
    1. Broadcast psi-calculi with an application to wireless protocols
    Öppna denna publikation i ny flik eller fönster >>Broadcast psi-calculi with an application to wireless protocols
    Visa övriga...
    2015 (Engelska)Ingår i: Software and Systems Modeling, ISSN 1619-1366, E-ISSN 1619-1374, Vol. 14, nr 1, s. 201-216Artikel i tidskrift (Refereegranskat) 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.

    Ort, förlag, år, upplaga, sidor
    Springer, 2015
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-205258 (URN)10.1007/s10270-013-0375-z (DOI)000349026100012 ()
    Projekt
    UPMARCProFuN
    Forskningsfinansiär
    Vetenskapsrådet, 2013-4853
    Tillgänglig från: 2013-11-08 Skapad: 2013-08-15 Senast uppdaterad: 2018-01-11Bibliografiskt granskad
    2. Higher-order psi-calculi
    Öppna denna publikation i ny flik eller fönster >>Higher-order psi-calculi
    2014 (Engelska)Ingår i: Mathematical Structures in Computer Science, ISSN 0960-1295, E-ISSN 1469-8072, Vol. 24, nr 2, artikel-id e240203Artikel i tidskrift (Refereegranskat) 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.

    Ort, förlag, år, upplaga, sidor
    Cambridge University Press, 2014
    Nyckelord
    process calculi, psi calculi, isabelle, theorem proving, nominal, higher-order
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-183610 (URN)10.1017/S0960129513000170 (DOI)000343643500003 ()
    Projekt
    UPMARCProFuN
    Forskningsfinansiär
    Stiftelsen för strategisk forskning (SSF)
    Tillgänglig från: 2013-06-24 Skapad: 2012-10-30 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
    3. A Sorted Semantic Framework for Applied Process Calculi (extended abstract)
    Öppna denna publikation i ny flik eller fönster >>A Sorted Semantic Framework for Applied Process Calculi (extended abstract)
    Visa övriga...
    2014 (Engelska)Ingår i: Trustworthy Global Computing: TGC 2013, Springer Berlin/Heidelberg, 2014, s. 103-118Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Ort, förlag, år, upplaga, sidor
    Springer Berlin/Heidelberg, 2014
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 8358
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-203382 (URN)10.1007/978-3-319-05119-2_7 (DOI)978-3-319-05118-5 (ISBN)
    Konferens
    8th International Symposium on Trustworthy Global Computing, August 30-31, 2013, Buenos Aires, Argentina
    Projekt
    UPMARCProFuN
    Forskningsfinansiär
    Stiftelsen för strategisk forskning (SSF), RIT08­0065
    Tillgänglig från: 2014-03-08 Skapad: 2013-07-09 Senast uppdaterad: 2018-01-11
    4. Negative premises in applied process calculi
    Öppna denna publikation i ny flik eller fönster >>Negative premises in applied process calculi
    Visa övriga...
    2013 (Engelska)Rapport (Övrigt vetenskapligt)
    Serie
    Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2013-014
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-229004 (URN)
    Tillgänglig från: 2013-06-20 Skapad: 2014-07-25 Senast uppdaterad: 2018-01-11Bibliografiskt granskad
    5. Bisimulation up-to techniques for psi-calculi
    Öppna denna publikation i ny flik eller fönster >>Bisimulation up-to techniques for psi-calculi
    2016 (Engelska)Ingår i: Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs / [ed] Avigad, J; Chlipala, A, New York: ACM Press, 2016, s. 142-153Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Ort, förlag, år, upplaga, sidor
    New York: ACM Press, 2016
    Nyckelord
    Bisimulation up-to, process calculus, psi-calculi, Isabelle, Nominal Isabelle, nominal logic
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-229008 (URN)10.1145/2854065.2854080 (DOI)000389021600016 ()9781450341271 (ISBN)
    Konferens
    CPP 2016, January 18–19, Saint Petersburg, FL
    Tillgänglig från: 2016-01-18 Skapad: 2014-07-25 Senast uppdaterad: 2018-01-11Bibliografiskt granskad
  • 829.
    Åman Pohjola, Johannes
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datalogi.
    Culling Concurrency Theory: Reusable and trustworthy meta-theory, proof techniques and separation results2016Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    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.

    Delarbeten
    1. Broadcast psi-calculi with an application to wireless protocols
    Öppna denna publikation i ny flik eller fönster >>Broadcast psi-calculi with an application to wireless protocols
    Visa övriga...
    2015 (Engelska)Ingår i: Software and Systems Modeling, ISSN 1619-1366, E-ISSN 1619-1374, Vol. 14, nr 1, s. 201-216Artikel i tidskrift (Refereegranskat) 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.

    Ort, förlag, år, upplaga, sidor
    Springer, 2015
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-205258 (URN)10.1007/s10270-013-0375-z (DOI)000349026100012 ()
    Projekt
    UPMARCProFuN
    Forskningsfinansiär
    Vetenskapsrådet, 2013-4853
    Tillgänglig från: 2013-11-08 Skapad: 2013-08-15 Senast uppdaterad: 2018-01-11Bibliografiskt granskad
    2. Higher-order psi-calculi
    Öppna denna publikation i ny flik eller fönster >>Higher-order psi-calculi
    2014 (Engelska)Ingår i: Mathematical Structures in Computer Science, ISSN 0960-1295, E-ISSN 1469-8072, Vol. 24, nr 2, artikel-id e240203Artikel i tidskrift (Refereegranskat) 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.

    Ort, förlag, år, upplaga, sidor
    Cambridge University Press, 2014
    Nyckelord
    process calculi, psi calculi, isabelle, theorem proving, nominal, higher-order
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-183610 (URN)10.1017/S0960129513000170 (DOI)000343643500003 ()
    Projekt
    UPMARCProFuN
    Forskningsfinansiär
    Stiftelsen för strategisk forskning (SSF)
    Tillgänglig från: 2013-06-24 Skapad: 2012-10-30 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
    3. A Sorted Semantic Framework for Applied Process Calculi
    Öppna denna publikation i ny flik eller fönster >>A Sorted Semantic Framework for Applied Process Calculi
    Visa övriga...
    2016 (Engelska)Ingår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 12, nr 1, s. 1-49, artikel-id 8Artikel i tidskrift (Refereegranskat) 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.

    Nyckelord
    Expressiveness, Pattern matching, Type systems, Theorem proving, pi-calculus, Nominal sets
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Forskningsämne
    Datavetenskap
    Identifikatorer
    urn:nbn:se:uu:diva-262199 (URN)10.2168/LMCS-12(1:8)2016 (DOI)000374769600004 ()
    Projekt
    UPMARC
    Forskningsfinansiär
    Vetenskapsrådet, 2013-4853
    Tillgänglig från: 2016-03-31 Skapad: 2015-09-09 Senast uppdaterad: 2019-02-25Bibliografiskt granskad
    4. Priorities Without Priorities: Representing Preemption in Psi-Calculi
    Öppna denna publikation i ny flik eller fönster >>Priorities Without Priorities: Representing Preemption in Psi-Calculi
    2014 (Engelska)Ingår i: Proc. 21st International Workshop on Expressiveness in Concurrency, and 11th Workshop on Structural Operational Semantics, 2014, s. 2-15Konferensbidrag, Publicerat paper (Refereegranskat)
    Serie
    Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180 ; 160
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-297468 (URN)10.4204/EPTCS.160.2 (DOI)
    Konferens
    EXPRESS/SOS 2014, September 1st, Rome, Italy
    Tillgänglig från: 2014-08-07 Skapad: 2016-06-23 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
    5. Bisimulation up-to techniques for psi-calculi
    Öppna denna publikation i ny flik eller fönster >>Bisimulation up-to techniques for psi-calculi
    2016 (Engelska)Ingår i: Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs / [ed] Avigad, J; Chlipala, A, New York: ACM Press, 2016, s. 142-153Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Ort, förlag, år, upplaga, sidor
    New York: ACM Press, 2016
    Nyckelord
    Bisimulation up-to, process calculus, psi-calculi, Isabelle, Nominal Isabelle, nominal logic
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-229008 (URN)10.1145/2854065.2854080 (DOI)000389021600016 ()9781450341271 (ISBN)
    Konferens
    CPP 2016, January 18–19, Saint Petersburg, FL
    Tillgänglig från: 2016-01-18 Skapad: 2014-07-25 Senast uppdaterad: 2018-01-11Bibliografiskt granskad
    6. The Expressive Power of Monotonic Parallel Composition
    Öppna denna publikation i ny flik eller fönster >>The Expressive Power of Monotonic Parallel Composition
    2016 (Engelska)Ingår i: Programming Languages and Systems, Berlin: Springer, 2016, s. 780-803Konferensbidrag, Publicerat paper (Refereegranskat)
    Ort, förlag, år, upplaga, sidor
    Berlin: Springer, 2016
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9632
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-297465 (URN)10.1007/978-3-662-49498-1_30 (DOI)000401936100030 ()978-3-662-49497-4 (ISBN)
    Konferens
    ESOP 2016, April 3–7, Eindhoven, The Netherlands
    Tillgänglig från: 2016-03-22 Skapad: 2016-06-23 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
  • 830.
    Åman Pohjola, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Borgström, Johannes
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Parrow, Joachim
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Raabjerg, Palle
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Rodhe, Ioana
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Negative premises in applied process calculi2013Rapport (Övrigt vetenskapligt)
  • 831.
    Åman Pohjola, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Parrow, Joachim
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Bisimulation up-to techniques for psi-calculi2016Ingår i: Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs / [ed] Avigad, J; Chlipala, A, New York: ACM Press, 2016, s. 142-153Konferensbidrag (Refereegranskat)
    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.

  • 832.
    Åman Pohjola, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Parrow, Joachim
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Priorities Without Priorities: Representing Preemption in Psi-Calculi2014Ingår i: Proc. 21st International Workshop on Expressiveness in Concurrency, and 11th Workshop on Structural Operational Semantics, 2014, s. 2-15Konferensbidrag (Refereegranskat)
  • 833.
    Åman Pohjola, Johannes
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Parrow, Joachim
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    The Expressive Power of Monotonic Parallel Composition2016Ingår i: Programming Languages and Systems, Berlin: Springer, 2016, s. 780-803Konferensbidrag (Refereegranskat)
  • 834.
    Östlund, Johan
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datalogi.
    Language Constructs for Safe Parallel Programming on Multi-Cores2016Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    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.

    Delarbeten
    1. Ownership, Uniqueness, and Immutability
    Öppna denna publikation i ny flik eller fönster >>Ownership, Uniqueness, and Immutability
    2008 (Engelska)Ingår i: Lecture Notes in Business Information Processing, ISSN 1865-1348, E-ISSN 1865-1356Artikel i tidskrift (Refereegranskat) 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.

    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-266671 (URN)10.1007/978-3-540-69824-1_11 (DOI)
    Konferens
    46th International Conference, TOOLS EUROPE 2008, Zurich, Switzerland, June 30 - July 4, 2008.
    Tillgänglig från: 2015-11-10 Skapad: 2015-11-10 Senast uppdaterad: 2018-01-10
    2. Minimal Ownership for Active Objects
    Öppna denna publikation i ny flik eller fönster >>Minimal Ownership for Active Objects
    2008 (Engelska)Ingår i: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349Artikel i tidskrift (Refereegranskat) 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.

    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-266793 (URN)10.1007/978-3-540-89330-1_11 (DOI)
    Konferens
    6th Asian Symposium, APLAS 2008, Bangalore, India, December 9-11, 2008
    Projekt
    EU project IST-33826 CREDO
    Tillgänglig från: 2015-11-10 Skapad: 2015-11-10 Senast uppdaterad: 2018-01-10
    3. Welterweight Java
    Öppna denna publikation i ny flik eller fönster >>Welterweight Java
    2010 (Engelska)Ingår i: Objects, Models, Components, Patterns / [ed] Vitek, Jan, Berlin: Springer-Verlag , 2010, s. 97-116Konferensbidrag, Publicerat paper (Refereegranskat)
    Ort, förlag, år, upplaga, sidor
    Berlin: Springer-Verlag, 2010
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 6141
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-130897 (URN)10.1007/978-3-642-13953-6_6 (DOI)000286162000006 ()978-3-642-13952-9 (ISBN)
    Konferens
    48th International Conference, TOOLS 2010
    Projekt
    UPMARCFacilitating Concurrent and Parallel Programming in Mainstream Programming Languages
    Tillgänglig från: 2010-09-17 Skapad: 2010-09-17 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
    4. Multiple Aggregate Entry Points for Ownership Types
    Öppna denna publikation i ny flik eller fönster >>Multiple Aggregate Entry Points for Ownership Types
    2012 (Engelska)Ingår i: ECOOP 2012 – Object-Oriented Programming, Springer Berlin/Heidelberg, 2012, s. 156-180Konferensbidrag, Publicerat paper (Refereegranskat)
    Ort, förlag, år, upplaga, sidor
    Springer Berlin/Heidelberg, 2012
    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 7313
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    urn:nbn:se:uu:diva-176660 (URN)10.1007/978-3-642-31057-7_8 (DOI)978-3-642-31056-0 (ISBN)
    Konferens
    26th European Conference on Object-Oriented Programming
    Projekt
    UPMARCFacilitating Concurrent and Parallel Programming in Mainstream Programming Languages
    Tillgänglig från: 2012-06-28 Skapad: 2012-06-21 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
    5. Refined Ownership: Fine-grained controlled internal sharing
    Öppna denna publikation i ny flik eller fönster >>Refined Ownership: Fine-grained controlled internal sharing
    2015 (Engelska)Ingår i: Formal Methods for Multicore Programming, 2015, Vol. 9104, s. 179-210Konferensbidrag, Publicerat paper (Refereegranskat)
    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.

    Serie
    Lecture Notes in Computer Science, ISSN 0302-9743 ; 9104
    Nationell ämneskategori
    Datavetenskap (datalogi)
    Identifikatorer
    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)
    Konferens
    15th International School on Formal Methods for the Design of Computer, Communication, and Software Systems; SFM 2015, June 15–19, Bertinoro, Italy
    Projekt
    UPMARCUPSCALE
    Tillgänglig från: 2015-05-07 Skapad: 2015-11-10 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
  • 835.
    Östlund, Johan
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Brandauer, Stephan
    Wrigstad, Tobias
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    The Joelle Programming Language: Evolving Java Programs Along Two Axes of Parallel Eval2012Konferensbidrag (Övrigt vetenskapligt)
  • 836.
    Östlund, Johan
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Wrigstad, Tobias
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Multiple Aggregate Entry Points for Ownership Types2012Ingår i: ECOOP 2012 – Object-Oriented Programming, Springer Berlin/Heidelberg, 2012, s. 156-180Konferensbidrag (Refereegranskat)
  • 837.
    Östlund, Johan
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Wrigstad, Tobias
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Regions as Owners: A Discussion on Ownership-based Effects in Practice2011Konferensbidrag (Refereegranskat)
  • 838.
    Östlund, Johan
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Wrigstad, Tobias
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Welterweight Java2010Ingår i: Objects, Models, Components, Patterns / [ed] Vitek, Jan, Berlin: Springer-Verlag , 2010, s. 97-116Konferensbidrag (Refereegranskat)
14151617 801 - 838 av 838
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf