Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
Refine search result
1234567 1 - 50 of 997
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Abbasi, Rosa
    et al.
    Darulova, Eva
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Modular Optimization-Based Roundoff Error Analysis of Floating-Point Programs2023In: Static Analysis: 30th International Symposium, SAS 2023 / [ed] Manuel Hermenegildo, Jose F. Morales, 2023Conference paper (Refereed)
  • 2. Abbasi, Rosa
    et al.
    Schiffl, Jonas
    Darulova, Eva
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. MPI SWS, Saarbrucken, Germany.
    Ulbrich, Mattias
    Ahrendt, Wolfgang
    Combining rule- and SMT-based reasoning for verifying floating-point Java programs in KeY2023In: International Journal on Software Tools for Technology Transfer, ISSN 1433-2779, E-ISSN 1433-2787, Vol. 25, p. 185-204Article in journal (Refereed)
    Abstract [en]

    Deductive verification has been successful in verifying interesting properties of real-world programs. One notable gap is the limited support for floating-point reasoning. This is unfortunate, as floating-point arithmetic is particularly unintuitive to reason about due to rounding as well as the presence of the special values infinity and ‘Not a Number’ (NaN). In this article, we present the first floating-point support in a deductive verification tool for the Java programming language. Our support in the KeY verifier handles floating-point arithmetics, transcendental functions, and potentially rounding-type casts. We achieve this with a combination of delegation to external SMT solvers on the one hand, and KeY-internal, rule-based reasoning on the other hand, exploiting the complementary strengths of both worlds. We evaluate this integration on new benchmarks and show that this approach is powerful enough to prove the absence of floating-point special values—often a prerequisite for correct programs—as well as functional properties, for realistic benchmarks.

    Download full text (pdf)
    fulltext
  • 3.
    Abdulla, Parosh
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Aronis, Stavros
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Comparing source sets and persistent sets for partial order reduction2017In: Models, Algorithms, Logics and Tools: Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday, Springer, 2017, p. 516-536Chapter in book (Other academic)
    Abstract [en]

    Partial order reduction has traditionally been based on persistent sets, ample sets, stubborn sets, or variants thereof. Recently, we have presented a strengthening of this foundation, using source sets instead of persistent/ample/stubborn sets. Source sets subsume persistent sets and are often smaller than persistent sets. We introduced source sets as a basis for Dynamic Partial Order Reduction (DPOR), in a framework which assumes that processes are deterministic and that all program executions are finite. In this paper, show how to use source sets for partial order reduction in a framework which does not impose these restrictions. We also compare source sets with persistent sets, providing some insights into conditions under which source sets and persistent sets do or do not differ.

  • 4.
    Abdulla, Parosh
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Aronis, Stavros
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Optimal dynamic partial order reduction2014In: Proc. 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New York: ACM Press, 2014, p. 373-384Conference paper (Refereed)
    Abstract [en]

    Stateless model checking is a powerful technique for program verification, which however suffers from an exponential growth in the number of explored executions. A successful technique for reducing this number, while still maintaining complete coverage, is Dynamic Partial Order Reduction (DPOR). We present a new DPOR algorithm, which is the first to be provably optimal in that it always explores the minimal number of executions. It is based on a novel class of sets, called source sets, which replace the role of persistent sets in previous algorithms. First, we show how to modify an existing DPOR algorithm to work with source sets, resulting in an efficient and simple to implement algorithm. Second, we extend this algorithm with a novel mechanism, called wakeup trees, that allows to achieve optimality. We have implemented both algorithms in a stateless model checking tool for Erlang programs. Experiments show that source sets significantly increase the performance and that wakeup trees incur only a small overhead in both time and space.

  • 5.
    Abdulla, Parosh
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Aronis, Stavros
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Source Sets: A Foundation for Optimal Dynamic Partial Order Reduction2017In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 64, no 4, article id 25Article in journal (Refereed)
    Abstract [en]

    Stateless model checking is a powerful method for program verification that, however, suffers from an exponential growth in the number of explored executions. A successful technique for reducing this number, while still maintaining complete coverage, is Dynamic Partial Order Reduction (DPOR), an algorithm originally introduced by Flanagan and Godefroid in 2005 and since then not only used as a point of reference but also extended by various researchers. In this article, we present a new DPOR algorithm, which is the first to be provably optimal in that it always explores the minimal number of executions. It is based on a novel class of sets, called source sets, that replace the role of persistent sets in previous algorithms. We begin by showing how to modify the original DPOR algorithm to work with source sets, resulting in an efficient and simple-to-implement algorithm, called source-DPOR. Subsequently, we enhance this algorithm with a novel mechanism, called wakeup trees, that allows the resulting algorithm, called optimal-DPOR, to achieve optimality. Both algorithms are then extended to computational models where processes may disable each other, for example, via locks. Finally, we discuss tradeoffs of the source-and optimal-DPOR algorithm and present programs that illustrate significant time and space performance differences between them. We have implemented both algorithms in a publicly available stateless model checking tool for Erlang programs, while the source-DPOR algorithm is at the core of a publicly available stateless model checking tool for C/pthread programs running on machines with relaxed memory models. Experiments show that source sets significantly increase the performance of stateless model checking compared to using the original DPOR algorithm and that wakeup trees incur only a small overhead in both time and space in practice.

  • 6.
    Abdulla, Parosh
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Lång, Magnus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Ngo, Tuan-Phong
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Optimal stateless model checking for reads-from equivalence under sequential consistency2019In: Proceedings of the ACM on Programming Languages, E-ISSN 2475-1421Article in journal (Refereed)
    Abstract [en]

    We present a new approach for stateless model checking (SMC) of multithreaded programs under Sequential Consistency (SC) semantics.  To combat state-space explosion, SMC is often equipped with a partial-order reduction technique, which defines an equivalence on executions, and only needs to explore one execution in each equivalence class.  Recently, it has been observed that the commonly used equivalence of Mazurkiewicz traces can be coarsened but still cover all program crashes and assertion violations.  However, for this coarser equivalence, which preserves only the reads-from relation from writes to reads, there is no SMC algorithm which is (i) optimal in the sense that it explores precisely one execution in each reads-from equivalence class, and (ii) efficient in the sense that it spends polynomial effort per class.  \end{inparaenum} We present the first SMC algorithm for SC that is both optimal and efficient in practice, meaning that it spends polynomial time per equivalence class on all programs that we have tried.  This is achieved by a novel test that checks whether a given reads-from relation can arise in some execution.  Our experimental results show that Nidhugg/rfsc, although slower than the fastest SMC tools in programs where tools happen to examine the same number of executions, always scales similarly or better than them, and outperforms them by an exponential factor in programs where the reads-from equivalence is coarser than the standard one. We also present two non-trivial use cases where the new equivalence is particularly effective, as well as the significant performance advantage that Nidhugg/rfsc offers compared to state-of-the-art SMC and systematic concurrency testing tools.

    Download full text (pdf)
    fulltext
  • 7.
    Abdulla, Parosh
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Ngo, Tuan-Phong
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Optimal Stateless Model Checking under the Release-Acquire Semantics2018In: Proceedings of the ACM on Programming Languages, E-ISSN 2475-1421, Vol. 2, no OOPSLA, p. 1-29, article id 135Article in journal (Refereed)
    Abstract [en]

    We present a framework for the efficient application of stateless model checking (SMC) to concurrent programs running under the Release-Acquire (RA) fragment of the C/C++11 memory model. Our approach is based on exploring the possible program orders, which define the order in which instructions of a thread are executed, and read-from relations, which specify how reads obtain their values from writes. This is in contrast to previous approaches, which also explore the possible coherence orders, i.e., orderings between conflicting writes. Since unexpected test results such as program crashes or assertion violations depend only on the read-from relation, we avoid a potentially significant source of redundancy. Our framework is based on a novel technique for determining whether a particular read-from relation is feasible under the RA semantics. We define an SMC algorithm which is provably optimal in the sense that it explores each program order and read-from relation exactly once. This optimality result is strictly stronger than previous analogous optimality results, which also take coherence order into account. We have implemented our framework in the tool Tracer. Experiments show that Tracer can be significantly faster than state-of-the-art tools that can handle the RA semantics.

    Download full text (pdf)
    FULLTEXT01
  • 8.
    Abdulla, Parosh
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Meyer Bonneland, Frederik
    Das, Sarbojit
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Lång, Magnus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Tailoring Stateless Model Checking for Event-Driven Multi-Threaded Programs2023In: Automated Technology for Verification and Analysis, 21st International Symposium, ATVA 2023, Singapore, Oct. 2023. Proceedings., 2023Conference paper (Refereed)
  • 9.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Aronis, Stavros
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Leonardsson, Carl
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Stateless model checking for TSO and PSO2015In: Tools and Algorithms for the Construction and Analysis of Systems: TACAS 2015, Springer Berlin/Heidelberg, 2015, p. 353-367Conference paper (Refereed)
  • 10.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Aronis, Stavros
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Leonardsson, Carl
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Sagonas, Konstantinos
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Stateless model checking for TSO and PSO2017In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 54, no 8, p. 789-818Article in journal (Refereed)
  • 11.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Cyriac, Aiswarya
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Atig, Mohamed Faouzi
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Montali, Marco
    Free Univ Bozen Bolzano, Bolzano, Italy.
    Rezine, Othmane
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Recency-Bounded Verification of Dynamic Database-Driven Systems2016In: PODS'16: PROCEEDINGS OF THE 35TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2016, p. 195-210Conference paper (Refereed)
    Abstract [en]

    We propose a formalism to model database-driven systems, called database manipulating systems (DMS). The actions of a DMS modify the current instance of a relational database by adding new elements into the database, deleting tuples from the relations and adding tuples to the relations. The elements which are modified by an action are chosen by (full) first-order queries. DMS is a highly expressive model and can be thought of as a succinct representation of an in finite state relational transition system, in line with similar models proposed in the literature. We propose monadic second order logic (MSO-FO) to reason about sequences of database instances appearing along a run. Unsurprisingly, the linear-time model checking problem of DMS against MSO-FO is undecidable. Towards decidability, we propose under-approximate model checking of DMS, where the under-approximation parameter is the "bound on recency". In a k-recency-bounded run, only the most recent k elements in the current active domain may be modified by an action. More runs can be verified by increasing the bound on recency. Our main result shows that recency-bounded model checking of DMS against MSO-FO is decidable, by a reduction to the satisfiability problem of MSO over nested words.

  • 12. Aceto, Luca
    et al.
    Longo, GiuseppeVictor, BjörnUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    The difference between concurrent and sequential computation2003Collection (editor) (Other (popular science, discussion, etc.))
  • 13. Aceto, Luca
    et al.
    Victor, BjörnUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    EXPRESS'00: 7th International Workshop on Expressiveness in Concurrency2000Conference proceedings (editor) (Other academic)
  • 14.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Wiatr, Pawel
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Routing and scheduling of network flows with deadlines and discrete capacity allocation2020In: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 76, no 1, p. 54-74Article in journal (Refereed)
    Abstract [en]

    Joint scheduling and routing of data flows with deadline constraints in communication networks has been attracting research interest. This type of problem distinguishes from conventional multicommodity flows due to the presence of the time dimension. In this paper, we address a flow routing and scheduling problem with delivery deadline, where the assignment of link capacity occurs in discrete units. Discrete capacity allocation is motivated by applications in communication systems, where it is common to have a base unit of capacity (e.g., wavelength channel in optical communications). We present and prove complexity results of the problem. Next, we give an optimization formulation based on a time slicing approach, which amounts to a discretization of the time into time slices to enable to formulate the deadline constraints. We then derive an effective reformulation of the problem, via which a column generation algorithm is developed. In addition, we propose a simple and fast max-flow-based algorithm. We use a number of networks and traffic scenarios to study various performance aspects of the algorithms.

  • 15.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Accounting for Information Freshness in Scheduling of Content Caching2020In: ICC 2020: 2020 IEEE International Conference on Communications (ICC), 2020Conference paper (Refereed)
    Abstract [en]

    In this paper, we study the problem of optimal scheduling of content placement along time in a base station with limited cache capacity, taking into account jointly the offloading effect and freshness of information. We model offloading based on popularity in terms of the number of requests and information freshness based on the notion of age of information (AoI). The objective is to reduce the load of backhaul links as well as the AoI of contents in the cache via a joint cost function. For the resulting optimization problem, we prove its hardness via a reduction from the Partition problem. Next, via a mathematical reformulation, we derive a solution approach based on column generation and a tailored rounding mechanism. Finally, we provide performance evaluation results showing that our algorithm provides near-optimal solutions.

  • 16.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    BS-assisted Task Offloading for D2D Networks with Presence of User Mobility2019In: 2019 IEEE 89TH VEHICULAR TECHNOLOGY CONFERENCE (VTC2019-SPRING), IEEE , 2019Conference paper (Refereed)
    Abstract [en]

    Task offloading is a key component in mobile edge computing. Offloading a task to a remote server takes communication and networking resources. An alternative is device-to-device (D2D) offloading, where a task of a device is offloaded to some device having computational resource available. The latter requires that the devices are within the range of each other, first for task collection, and later for result gathering. Hence, in mobility scenarios, the performance of D2D offloading will suffer if the contact rates between the devices are low. We enhance the setup to base station (BS) assisted D2D offloading, namely, a BS can act as a relay for task distribution or result collection. However, this would imply additional consumption of wireless resources. The associated cost and the improvement in completion time of task offloading compose a fundamental trade-off. For the resulting optimization problem, we mathematically prove the complexity, and propose an algorithm using Lagrangian duality. The simulation results demonstrate not only that the algorithm has close-to-optimal performance, but also provide structural insights of the optimal trade-off.

  • 17.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    On optimal proactive and retention-aware caching with user mobility2018In: 2018 IEEE 88th Vehicular Technology Conference (VTC-Fall), IEEE, 2018Conference paper (Refereed)
    Abstract [en]

    Caching popular contents at edge devices is an effective solution to alleviate the burden of the backhaul networks. Earlier investigations commonly neglected the storage cost in caching. More recently, retention-aware caching, where both the downloading cost and storage cost are accounted for, is attracting attention. Motivated by this, we address proactive and retention-aware caching problem with the presence of user mobility, optimizing the sum of the two types of costs. More precisely, a cost-optimal caching problem for vehicle-to-vehicle networks is formulated with joint consideration of the impact of the number of vehicles, cache size, storage cost, and content request probability. This is a combinatorial optimization problem. However, we derive a stream of analytical results and they together lead to an algorithm that guarantees global optimum with polynomial-time complexity. Numerical results show significant improvements in comparison to popular caching and random caching.

  • 18.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science. Komar Univ Sci & Technol, Dept Comp Sci, Sulaymaniyah 75105, Iraq.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Optimal Content Caching and Recommendation With Age of Information2024In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 23, no 1, p. 689-704Article in journal (Refereed)
    Abstract [en]

    Content caching at the network edge is an effective way of mitigating backhaul load and improving user experience. Caching efficiency can be enhanced by content recommendation and by keeping the information fresh. By content recommendation, a requested content that is not in the cache can be alternatively satisfied by a related cached content recommended by the system. Information freshness can be quantified by age of information (AoI). This article has the following contributions. First, we address optimal scheduling of cache updates for a time-slotted system accounting for content recommendation and AoI, and to the best of our knowledge, there is no work that has jointly taken into account these aspects. Next, we rigorously prove the problem's NP-hardness. Then, we derive an integer linear formulation, by which the optimal solution can be obtained for small-scale scenarios. On the algorithmic side, our contributions include the development of an effective algorithm based on Lagrangian decomposition, and efficient algorithms for solving the resulting subproblems. Our algorithm computes a bound that can be used to evaluate the performance of any suboptimal solution. We conduct simulations to show the effectiveness of our algorithm.

  • 19.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Optimal scheduling of content caching subject to deadline2020In: IEEE Open Journal of the Communications Society, E-ISSN 2644-125X, Vol. 1, p. 293-307Article in journal (Refereed)
    Abstract [en]

    Content caching at the edge of network is a promising technique to alleviate the burden of backhaul networks. In this paper, we consider content caching along time in a base station with limited cache capacity. As the popularity of contents may vary over time, the contents of cache need to be updated accordingly. In addition, a requested content may have a delivery deadline within which the content needs to be obtained. Motivated by these, we address optimal scheduling of content caching in a time-slotted system under delivery deadline and cache capacity constraints. The objective is to minimize a cost function that captures the load of backhaul links. For our optimization problem, we prove its NP-hardness via a reduction from the Partition problem. For problem solving, via a mathematical reformulation, we develop a solution approach based on repeatedly applying a column generation algorithm and a problem-tailored rounding algorithm. In addition, two greedy algorithms are developed based on existing algorithms from the literature. Finally, we present extensive simulations that verify the effectiveness of our solution approach in obtaining near-to-optimal solutions in comparison to the greedy algorithms. The solutions obtained from our solution approach are within 1.6% from global optimality.

    Download full text (pdf)
    fulltext
  • 20.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
    Sun, Sumei
    Institute for Infocomm Research, Singapore, Singapore;Singapore Institute of Technology, Singapore, Singapore.
    Optimal Scheduling of Age-centric Caching: Tractability and Computation2022In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 21, p. 2939-2954Article in journal (Refereed)
    Abstract [en]

    The notion of age of information (AoI) has become an important performance metric in network and control systems. Information freshness, represented by AoI, naturally arises in the context of caching. We address optimal scheduling of cache updates for a time-slotted system where the contents vary in size. There is limited capacity for the cache for making updates. Each content is associated with a utility function that depends on the AoI and the time duration of absence from the cache. For this combinatorial optimization problem, we present the following contributions. First, we provide theoretical results of problem tractability. Whereas the problem is NP-hard, we prove solution tractability in polynomial time for a special case with uniform content size, by a reformulation using network flows. Second, we derive an integer linear formulation for the problem, of which the optimal solution can be obtained for small-scale scenarios. Next, via a mathematical reformulation, we derive a scalable optimization algorithm using repeated column generation. In addition, the algorithm computes a bound of global optimum, that can be used to assess the performance of any scheduling solution. Performance evaluation of large-scale scenarios demonstrates the strengths of the algorithm in comparison to a greedy schedule. Finally, we extend the applicability of our work to cyclic scheduling.

  • 21.
    Ahani, Ghafour
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Yuan, Di
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Zhao, Yixin
    Nanjing Univ Sci & Technol, Sch Automat, Nanjing 210094, Peoples R China..
    Age-Optimal UAV Scheduling for Data Collection With Battery Recharging2021In: IEEE Communications Letters, ISSN 1089-7798, E-ISSN 1558-2558, Vol. 25, no 4, p. 1254-1258Article in journal (Refereed)
    Abstract [en]

    We study route scheduling of a UAV for data collection from sensor nodes (SNs) with battery recharging. The freshness of the collected information is captured by the metric of age of information (AoI). The objective is to minimize the average AoI cost of all SNs over a scheduling time horizon. We prove that the problem in its general form is NP-hard. Then, for a special case of the problem, we prove that optimum can be computed in polynomial time. Next, we develop an algorithm based on graph labeling. Finally, we show the effectiveness of our algorithm in comparison to greedy scheduling.

  • 22.
    Akram, Muhammad Zain
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    User Preference-Based Evaluation of Counterfactual Explanation Methods2023Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    Explainable AI (XAI) has grown as an important field over the years. As more complicated AI systems are utilised in decision-making situations, the necessity for explanations for such systems is also increasing in order to ensure transparency and stakeholder trust. This study focuses on a specific type of explanation method, namely counterfactual explanations. Counterfactual explanations provide feedback that outlines what changes should be made to the input to reach a different outcome. This study expands on a previous dissertation in which a proof-of-concept tool was created for comparing several counterfactual explanation methods. This thesis investigates the properties of counterfactual explanation methods along with some appropriate metrics. The identified metrics are then used to evaluate and compare the desirable properties of the counterfactual approaches. The proof-of-concept tool is extended with a properties-metrics mapping module, and a user preference-based system is developed, allowing users to evaluate different counterfactual approaches depending on their preferences. This addition to the proof-of-concept tool is a critical step in providing field researchers with a standardised benchmarking tool.

    Download full text (pdf)
    fulltext
  • 23.
    Aldmour, Ismat
    et al.
    Al Baha University, Saudi Arabia.
    Nylén, Aletta
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Impact of cultural and language background on learning Computer Science concepts2014In: Proc. 2nd International Conference on Learning and Teaching in Computing and Engineering, Los Alamitos, CA: IEEE Computer Society, 2014, p. 37-40Conference paper (Refereed)
    Abstract [en]

    Computer science terminology is generally based on words that have a related original meaning in English and rooted in western tradition. Hence, students from other cultures and students that are not native English speakers, will not be helped by language and culture in understanding computer science concepts. In this work, the authors review the interrelationship between language, cultural background, and the learning of computer science. A comparative study is under preparation in which this relationship is to be examined. The study will compare the intuitive understanding of computer science concepts between Saudi student groups of different English language proficiency levels and of different maturity levels. A test has been designed in order to reveal differences in the perception of computer science concepts that can be attributed to such background differences. The study will serve as a starting point for further work on how computer science education can be enhanced for students that are non-native English speakers.

  • 24. Alexander, Perry
    et al.
    Flener, PierreUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. CSD.
    Special Issue on ASE'002003Collection (editor) (Other scientific)
  • 25.
    Alghamdi, Fayiq
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Dimensions of Professionalism: A Study of Computer Science Teaching in Saudi Arabia2020Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    In Saudi Arabia, new computing education programs have been introduced in alignment with the Saudi Vision 2030, which is a plan launched in 2017 to reduce Saudi Arabia's reliance on oil, diversify its economy, and develop its health, education, recreation, infrastructure and tourism. Computer science is a rapidly changing area, which places high demands on teachers in the subject to develop both their subject and pedagogical competence. This thesis explores computer science teachers’ perspectives on professional development from three viewpoints—the Saudi Teaching Competencies Standard, engagement in teachers’ awards and self-directed learning. The thesis examines the efforts of computer science teachers as they develop new pedagogies during their teaching careers as a result of the new regulations. The main question is ‘How do Saudi Arabian computer science teachers develop their teaching professionalism?’ Conclusions draw on the outcomes of four sub-studies. A mixed-methods approach consisting of interviews and questionnaires was used to collect data. The participants comprised 389 computer science teachers from different Saudi Arabian cities with different demographics and different teaching experience. The analysis drew on a theoretical framework that integrates elements of the Theory of Reasoned Action, the Theory of Planned Behaviour and the Adult Learning Theory. A model for pedagogical change was developed and used to understand how and why computer science teachers change their educational pedagogy. The model explains the teachers’ shift in pedagogy and answers the question of how and why computer science teachers adopt a new pedagogical strategy. The studies show that both internal and external factors motivate the study participants to engage in competency development. In the Saudi model, the Saudi Teaching Competencies Standard and awards are external factors as they include a preparatory period of intensive skills development. Teachers' experience from this informs the picture of Saudi teachers' training that is presented in the dissertation. Indeed, the trial participants stated that they mainly used self-directed learning for their competence development, drawing on internal motivation. One reason for this was that they felt that many of the skills development programs offered lacked timeliness and relevance. The studies on which the dissertation is based have been conducted in Saudi Arabia, but the results also provide insights into general challenges associated with regulating teachers' competence and the design of in-service training for teachers. The results clearly point out the importance of teachers' participation in the development of the profession in order for changes to be accepted and incorporated into their profession. Behavior change theories can be used to understand and predict how new regulations and pedagogical strategies will be received, and if they are likely to be accepted or rejected by teachers. These theories, therefore, constitute a useful tool in regulating teaching and the teaching profession.

    List of papers
    1. Computer science teachers perspectives on competencies: A case study in the Kingdom of Saudi Arabia
    Open this publication in new window or tab >>Computer science teachers perspectives on competencies: A case study in the Kingdom of Saudi Arabia
    2018 (English)In: Informatics in Schools. Fundamentals of Computer Science and Software Engineering, Springer, 2018, p. 129-140Conference paper, Published paper (Refereed)
    Abstract [en]

    The Kingdom of Saudi Arabia (KSA) has recently adopted the Saudi Teaching Competencies Standard (STCS). This paper tries to answer how these competencies are achieved, how they are maintained, and what support exists to support teaching CS competently in the KSA. This paper presents the results of an investigation of teacher awareness of, and attitudes to, the STCS in the Kingdom. Through the study reported here, we address an urgent need in the Kingdom to understand teacher preparedness in terms of CS teaching competencies. The study draws on interviews with ten CS teachers in five different cities in the KSA. A thematic coding analysis approach was used. This study explores the CS teaching competencies held by teachers in three areas of CS teaching, focusing on connection to society, professional practice and professional development. The results of the study highlight the CS teaching competencies that CS teachers feel they currently grasp well in the KSA. By enhancing awareness of what teachers currently do well we contribute to the adjustment and improvement of the STCS and help to build a program which addresses the current in-service training needs of CS teachers. The outcomes also help to raise awareness of the challenges of implementing the Computer Education curriculum in KSA schools.

    Place, publisher, year, edition, pages
    Springer, 2018
    Series
    Lecture Notes in Computer Science ; 11169
    National Category
    Computer Sciences Educational Sciences
    Identifiers
    urn:nbn:se:uu:diva-363118 (URN)10.1007/978-3-030-02750-6_10 (DOI)000495445600010 ()978-3-030-02749-0 (ISBN)
    Conference
    ISSEP 2018, October 10–12, Saint Petersburg, Russia
    Available from: 2018-10-11 Created: 2018-10-12 Last updated: 2021-01-13Bibliographically approved
    2. Changing the Educational Epistemologies of Computer Science Teachers: A Case Study of the Kingdom of Saudi Arabia
    Open this publication in new window or tab >>Changing the Educational Epistemologies of Computer Science Teachers: A Case Study of the Kingdom of Saudi Arabia
    2018 (English)In: 2018 IEEE Frontiers in Education Conference (FIE), Piscataway, NJ: IEEE, 2018Conference paper, Published paper (Refereed)
    Abstract [en]

    This paper explores the attitudes of Computer Sci- ence (CS) teachers in the Kingdom of Saudi Arabia (KSA) who are confronted by the Saudi Teaching Competencies Standards (STCS). The STCS is a response to a substantial need to develop both subject-specific pedagogical ability as well as teachers subject area knowledge. The Ministry of Education in the KSA is encouraging teachers to improve their practices to achieve the new quality requirements for education. This paper presents the results of an investigation of CS teachers’ views on educational belief changes in the KSA schools. The paper addresses how and why CS teachers adopt new educational beliefs in their teaching. The paper presents the results of the investigation of the CS teachers views on educational belief changes in the KSA schools and the STCS policy document guidelines. Research in the area of changing educational epistemology in teaching CS identifies six factors that influence teachers, these are personal pedagogical beliefs, peer learning, curriculum, self-directed learning, student feedback and the STCS. A mixed method study approach was adopted in this work. Content analysis has been applied to the interview transcript and thematic coding analysis to the government policy document (STCS). The results provide a valuable case study in the KSA and emphasize the weak relationship between educational epistemology change and the STCS norms. The findings show that the STCS should provide stronger guidance for CS teachers to keep changing beliefs in teaching CS. The STCS should offer supporting official resources to CS teachers to help them in changing their beliefs in regard to teaching CS.

    Place, publisher, year, edition, pages
    Piscataway, NJ: IEEE, 2018
    Series
    Frontiers in Education Conference, ISSN 0190-5848
    National Category
    Computer Sciences Educational Sciences
    Identifiers
    urn:nbn:se:uu:diva-362867 (URN)10.1109/FIE.2018.8659265 (DOI)000468396903022 ()978-1-5386-1174-6 (ISBN)
    Conference
    48th IEEE Frontiers in Education Conference (FIE), San Jose State Univ, San Jose, CA, October 03-06, 2018
    Available from: 2019-03-07 Created: 2018-10-11 Last updated: 2021-01-13Bibliographically approved
    3. Teachers’ Awards: an Incentive for Pedagogical Development in Saudi Arabia
    Open this publication in new window or tab >>Teachers’ Awards: an Incentive for Pedagogical Development in Saudi Arabia
    2019 (English)In: 2019 IEEE Frontiers in Education Conference (FIE), 2019, , p. 6Conference paper, Published paper (Refereed)
    Abstract [en]

    This work-in-progress paper presents a study on how K-12 Computer Science teachers in Saudi Arabia have changed their pedagogy as a result of engaging in one year of professional development leading up to applying for a teacher's award. The results are based on thematic analysis of fourteen interviews with teachers that have been awarded either the `Education Excellence Award' or the `Microsoft Expert in Education'. The study focuses on how preparing for and getting the teaching award has influenced them focusing on changes in their pedagogical development and subsequent practices. The work provides an in-depth description of several aspects of the Saudi Arabian teaching culture. It explores and discusses the affordances of mechanisms used to strengthen pedagogical competence in a teacher community, paying extra attention to awards. This study identifies four main factors that motivate teachers to engage in pedagogical development in teaching Computer Science. The research suggests that awards can be an efficient motivator in establishing a culture of excellence among Computer Science teachers.

    Publisher
    p. 6
    Series
    Frontiers in Education Conference, ISSN 1539-4565, E-ISSN 2377-634X
    National Category
    Computer Sciences
    Research subject
    Computer Science with specialization in Computer Science Education Research
    Identifiers
    urn:nbn:se:uu:diva-397189 (URN)10.1109/FIE43999.2019.9028563 (DOI)000565244800208 ()978-1-7281-1746-1 (ISBN)978-1-7281-1747-8 (ISBN)
    Conference
    49th Annual Frontiers in Education (FIE) Conference, Cincinnati, October 16-19, 2019
    Available from: 2019-11-18 Created: 2020-10-27 Last updated: 2021-01-13Bibliographically approved
    4. Why Computer Science teachers in Saudi Arabia Learn on Their Own: Impulse for Self-Directed Professional Development in CS teaching
    Open this publication in new window or tab >>Why Computer Science teachers in Saudi Arabia Learn on Their Own: Impulse for Self-Directed Professional Development in CS teaching
    (English)Manuscript (preprint) (Other academic)
    Abstract [en]

    The research investigates the self-directed learning of CS teaching among Computer Science (CS) teachers in Saudi Arabia schools as a way of their professional development. The researchers developed a questionnaire with a 42-items inspiring from the previous literature and the purpose of the research question: How CS teachers were influenced by self-directed professional development in CS teaching? The questionnaires evaluated by the virtual honesty, Factor analysis and Alpha-Cronbach. Then, it distributed to 16 education offices and responses were received from 352 participants. The data shows that CS female teachers are more engaged in self-directed learning than CS male teachers. Also, the participants agreed on the total of average scores of the survey on learners’ self-directedness in the workplaces and self- reflection, planning, reasons and professional development for CS teachers. The recommendation made supported the CS teaching internet material recourses and make them easy and accessibility for all CS teachers community.

    National Category
    Computer Sciences
    Research subject
    Computer Science with specialization in Computer Science Education Research
    Identifiers
    urn:nbn:se:uu:diva-398747 (URN)
    Available from: 2019-12-10 Created: 2019-12-10 Last updated: 2021-01-13Bibliographically approved
    Download full text (pdf)
    fulltext
    Download (jpg)
    presentationsbild
  • 26.
    Alghamdi, Fayiq
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research. Al-Baha University .
    Why Computer Science teachers in Saudi Arabia Learn on Their Own: Impulse for Self-Directed Professional Development in CS teachingManuscript (preprint) (Other academic)
    Abstract [en]

    The research investigates the self-directed learning of CS teaching among Computer Science (CS) teachers in Saudi Arabia schools as a way of their professional development. The researchers developed a questionnaire with a 42-items inspiring from the previous literature and the purpose of the research question: How CS teachers were influenced by self-directed professional development in CS teaching? The questionnaires evaluated by the virtual honesty, Factor analysis and Alpha-Cronbach. Then, it distributed to 16 education offices and responses were received from 352 participants. The data shows that CS female teachers are more engaged in self-directed learning than CS male teachers. Also, the participants agreed on the total of average scores of the survey on learners’ self-directedness in the workplaces and self- reflection, planning, reasons and professional development for CS teachers. The recommendation made supported the CS teaching internet material recourses and make them easy and accessibility for all CS teachers community.

  • 27.
    Alghamdi, Fayiq
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research. Al-Baha University, Al Baha, Saudi Arabia.
    Why do female students choose to study CS in the Kingdom of Saudi Arabia?2017In: Proc. 5th International Conference on Learning and Teaching in Computing and Engineering, IEEE Computer Society, 2017, p. 49-53Conference paper (Refereed)
    Abstract [en]

    We know that female students in computer science, CS, are fewer than male students in Western countries. What is not well understood is the high rate of Saudi female students in CS. This article explores why female students choose to study CS in the Kingdom of Saudi Arabia, KSA. Data was collected through structured interviews with ten female students in three different universities in the KSA. The content analysis approach was used. This study determines the students' experiences in studying CS. The findings of this study are a first step in paying more attention to the system of women's education in the KSA. Motivation and expectation regarding CS were investigated. Results showed that the reasons behind the engagement of Saudi female students in CS are government support, family influence, and a stable workplace. The results could help to improve the CS curriculum and program of preparation for CS teachers in the KSA.

    Download full text (pdf)
    fulltext
  • 28.
    Alghamdi, Fayiq
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Women in computing in Saudi Arabia2016In: Proc. 3rd ACM-W Europe Celebration of Women in Computing, 2016, , p. 4p. 1-3Conference paper (Other academic)
    Download full text (pdf)
    fulltext
  • 29.
    Alghamdi, Fayiq
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Nylén, Aletta
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Pears, Arnold
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Changing the Educational Epistemologies of Computer Science Teachers: A Case Study of the Kingdom of Saudi Arabia2018In: 2018 IEEE Frontiers in Education Conference (FIE), Piscataway, NJ: IEEE, 2018Conference paper (Refereed)
    Abstract [en]

    This paper explores the attitudes of Computer Sci- ence (CS) teachers in the Kingdom of Saudi Arabia (KSA) who are confronted by the Saudi Teaching Competencies Standards (STCS). The STCS is a response to a substantial need to develop both subject-specific pedagogical ability as well as teachers subject area knowledge. The Ministry of Education in the KSA is encouraging teachers to improve their practices to achieve the new quality requirements for education. This paper presents the results of an investigation of CS teachers’ views on educational belief changes in the KSA schools. The paper addresses how and why CS teachers adopt new educational beliefs in their teaching. The paper presents the results of the investigation of the CS teachers views on educational belief changes in the KSA schools and the STCS policy document guidelines. Research in the area of changing educational epistemology in teaching CS identifies six factors that influence teachers, these are personal pedagogical beliefs, peer learning, curriculum, self-directed learning, student feedback and the STCS. A mixed method study approach was adopted in this work. Content analysis has been applied to the interview transcript and thematic coding analysis to the government policy document (STCS). The results provide a valuable case study in the KSA and emphasize the weak relationship between educational epistemology change and the STCS norms. The findings show that the STCS should provide stronger guidance for CS teachers to keep changing beliefs in teaching CS. The STCS should offer supporting official resources to CS teachers to help them in changing their beliefs in regard to teaching CS.

  • 30.
    Alghamdi, Fayiq
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Nylén, Aletta
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Pears, Arnold
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Teachers’ Awards: an Incentive for Pedagogical Development in Saudi Arabia2019In: 2019 IEEE Frontiers in Education Conference (FIE), 2019, , p. 6Conference paper (Refereed)
    Abstract [en]

    This work-in-progress paper presents a study on how K-12 Computer Science teachers in Saudi Arabia have changed their pedagogy as a result of engaging in one year of professional development leading up to applying for a teacher's award. The results are based on thematic analysis of fourteen interviews with teachers that have been awarded either the `Education Excellence Award' or the `Microsoft Expert in Education'. The study focuses on how preparing for and getting the teaching award has influenced them focusing on changes in their pedagogical development and subsequent practices. The work provides an in-depth description of several aspects of the Saudi Arabian teaching culture. It explores and discusses the affordances of mechanisms used to strengthen pedagogical competence in a teacher community, paying extra attention to awards. This study identifies four main factors that motivate teachers to engage in pedagogical development in teaching Computer Science. The research suggests that awards can be an efficient motivator in establishing a culture of excellence among Computer Science teachers.

  • 31.
    Alghamdi, Fayiq
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Pears, Arnold
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Nylén, Aletta
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Education Research.
    Computer science teachers perspectives on competencies: A case study in the Kingdom of Saudi Arabia2018In: Informatics in Schools. Fundamentals of Computer Science and Software Engineering, Springer, 2018, p. 129-140Conference paper (Refereed)
    Abstract [en]

    The Kingdom of Saudi Arabia (KSA) has recently adopted the Saudi Teaching Competencies Standard (STCS). This paper tries to answer how these competencies are achieved, how they are maintained, and what support exists to support teaching CS competently in the KSA. This paper presents the results of an investigation of teacher awareness of, and attitudes to, the STCS in the Kingdom. Through the study reported here, we address an urgent need in the Kingdom to understand teacher preparedness in terms of CS teaching competencies. The study draws on interviews with ten CS teachers in five different cities in the KSA. A thematic coding analysis approach was used. This study explores the CS teaching competencies held by teachers in three areas of CS teaching, focusing on connection to society, professional practice and professional development. The results of the study highlight the CS teaching competencies that CS teachers feel they currently grasp well in the KSA. By enhancing awareness of what teachers currently do well we contribute to the adjustment and improvement of the STCS and help to build a program which addresses the current in-service training needs of CS teachers. The outcomes also help to raise awareness of the challenges of implementing the Computer Education curriculum in KSA schools.

  • 32.
    Alhalaweh, Amjad
    et al.
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Alzghoul, Ahmad
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Bergström, Christel A. S.
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Molecular Drivers of Crystallization Kinetics for Drugs in Supersaturated Aqueous Solutions2019In: Journal of Pharmaceutical Sciences, ISSN 0022-3549, E-ISSN 1520-6017, Vol. 108, no 1, p. 252-259Article in journal (Refereed)
    Abstract [en]

    In this study, we explore molecular properties of importance in solution-mediated crystallization occurring in supersaturated aqueous drug solutions. Furthermore, we contrast the identified molecular properties with those of importance for crystallization occurring in the solid state. A literature data set of 54 structurally diverse compounds, for which crystallization kinetics from supersaturated aqueous solutions and in melt-quenched solids were reported, was used to identify molecular drivers for crystallization kinetics observed in solution and contrast these to those observed for solids. The compounds were divided into fast, moderate, and slow crystallizers, and in silico classification was developed using a molecular K-nearest neighbor model. The topological equivalent of Grav3 (related to molecular size and shape) was identified as the most important molecular descriptor for solution crystallization kinetics; the larger this descriptor, the slower the crystallization. Two electrotopological descriptors (the atom-type E-state index for -Caa groups and the sum of absolute values of pi Fukui(+) indices on C) were found to separate the moderate and slow crystallizers in the solution. The larger these descriptors, the slower the crystallization. With these 3 descriptors, the computational model correctly sorted the crystallization tendencies from solutions with an overall classification accuracy of 77% (test set).

    Download full text (pdf)
    FULLTEXT01
  • 33.
    Alhalaweh, Amjad
    et al.
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Alzghoul, Ahmad
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Kaialy, Waseem
    Mahlin, Denny
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Bergström, Christel A. S.
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Computational predictions of glass-forming ability and crystallization tendency of drug molecules2014In: Molecular Pharmaceutics, ISSN 1543-8384, E-ISSN 1543-8392, Vol. 11, no 9, p. 3123-3132Article in journal (Refereed)
    Abstract [en]

    Amorphization is an attractive formulation technique for drugs suffering from poor aqueous solubility as a result of their high lattice energy. Computational models that can predict the material properties associated with amorphization, such as glass-forming ability (GFA) and crystallization behavior in the dry state, would be a time-saving, cost-effective, and material-sparing approach compared to traditional experimental procedures. This article presents predictive models of these properties developed using support vector machine (SVM) algorithm. The GFA and crystallization tendency were investigated by melt-quenching 131 drug molecules in situ using differential scanning calorimetry. The SVM algorithm was used to develop computational models based on calculated molecular descriptors. The analyses confirmed the previously suggested cutoff molecular weight (MW) of 300 for glass-formers, and also clarified the extent to which MW can be used to predict the GFA of compounds with MW < 300. The topological equivalent of Grav3_3D, which is related to molecular size and shape, was a better descriptor than MW for GFA; it was able to accurately predict 86% of the data set regardless of MW. The potential for crystallization was predicted using molecular descriptors reflecting Hückel pi atomic charges and the number of hydrogen bond acceptors. The models developed could be used in the early drug development stage to indicate whether amorphization would be a suitable formulation strategy for improving the dissolution and/or apparent solubility of poorly soluble compounds.

  • 34.
    Alhalaweh, Amjad
    et al.
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Alzghoul, Ahmad
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Mahlin, Denny
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Bergström, Christel A. S.
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Physical stability of drugs after storage above and below the glass transition temperature: Relationship to glass-forming ability2015In: International Journal of Pharmaceutics, ISSN 0378-5173, E-ISSN 1873-3476, Vol. 495, no 1, p. 312-317Article in journal (Refereed)
    Abstract [en]

    Amorphous materials are inherently unstable and tend to crystallize upon storage. In this study, we investigated the extent to which the physical stability and inherent crystallization tendency of drugs are related to their glass-forming ability (GFA), the glass transition temperature (T-g) and thermodynamic factors. Differential scanning calorimetry was used to produce the amorphous state of 52 drugs [ 18 compounds crystallized upon heating (Class II) and 34 remained in the amorphous state (Class III)] and to perform in situ storage for the amorphous material for 12 h at temperatures 20 degrees C above or below the T-g. A computational model based on the support vector machine (SVM) algorithm was developed to predict the structure-property relationships. All drugs maintained their Class when stored at 20 degrees C below the T-g. Fourteen of the Class II compounds crystallized when stored above the T-g whereas all except one of the Class III compounds remained amorphous. These results were only related to the glass-forming ability and no relationship to e. g. thermodynamic factors was found. The experimental data were used for computational modeling and a classification model was developed that correctly predicted the physical stability above the T-g. The use of a large dataset revealed that molecular features related to aromaticity and pi-pi interactions reduce the inherent physical stability of amorphous drugs.

    Download full text (pdf)
    fulltext
  • 35. Allignol, Cyril
    et al.
    Barnier, Nicolas
    Flener, Pierre
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Pearson, Justin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Constraint programming for air traffic management: a survey2012In: Knowledge engineering review (Print), ISSN 0269-8889, E-ISSN 1469-8005, Vol. 27, no 3, p. 361-392Article, review/survey (Refereed)
  • 36.
    Alzghoul, Ahmad
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Alhalaweh, Amjad
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Mahlin, Denny
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Bergström, Christel A. S.
    Uppsala University, Disciplinary Domain of Medicine and Pharmacy, Faculty of Pharmacy, Department of Pharmacy.
    Experimental and Computational Prediction of Glass Transition Temperature of Drugs2014In: JOURNAL OF CHEMICAL INFORMATION AND MODELING, ISSN 1549-9596, Vol. 54, no 12, p. 3396-3403Article in journal (Refereed)
    Abstract [en]

    Glass transition temperature (T-g) is an important inherent property of an amorphous solid material which is usually determined experimentally. In this study, the relation between T-g and melting temperature (T-m) was evaluated using a data set of 71 structurally diverse druglike compounds. Further, in silico models for prediction of T-g were developed based on calculated molecular descriptors and linear (multilinear regression, partial least-squares, principal component regression) and nonlinear (neural network, support vector regression) modeling techniques. The models based on T-m predicted T-g with an RMSE of 19.5 K for the test set. Among the five computational models developed herein the support vector regression gave the best result with RMSE of 18.7 K for the test set using only four chemical descriptors. Hence, two different models that predict T-g of drug-like molecules with high accuracy were developed. If T-m is available, a simple linear regression can be used to predict T-g. However, the results also suggest that support vector regression and calculated molecular descriptors can predict T-g with equal accuracy, already before compound synthesis.

  • 37.
    Alzghoul, Ahmad
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Backe, Björn
    Löfstrand, Magnus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Byström, Arne
    Liljedahl, Bengt
    Comparing a knowledge-based and a data-driven method in querying data streams for system fault detection: A hydraulic drive system application2014In: Computers in industry (Print), ISSN 0166-3615, E-ISSN 1872-6194, Vol. 65, no 8, p. 1126-1135Article in journal (Refereed)
    Abstract [en]

    The field of fault detection and diagnosis has been the subject of considerable interest in industry. Fault detection may increase the availability of products, thereby improving their quality. Fault detection and diagnosis methods can be classified in three categories: data-driven, analytically based, and knowledge-based methods.

    In this work, we investigated the ability and the performance of applying two fault detection methods to query data streams produced from hydraulic drive systems. A knowledge-based method was compared to a data-driven method. A fault detection system based on a data stream management system (DSMS) was developed in order to test and compare the two methods using data from real hydraulic drive systems.

    The knowledge-based method was based on causal models (fault trees), and principal component analysis (PCA) was used to build the data-driven model. The performance of the methods in terms of accuracy and speed, was examined using normal and physically simulated fault data. The results show that both methods generate queries fast enough to query the data streams online, with a similar level of fault detection accuracy. The industrial applications of both methods include monitoring of individual industrial mechanical systems as well as fleets of such systems. One can conclude that both methods may be used to increase industrial system availability.

  • 38.
    Alzghoul, Ahmad
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Löfstrand, Magnus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Addressing concept drift to improve system availability by updating one-class data-driven models2015In: Evolving Systems, ISSN 1868-6478, E-ISSN 1868-6486, Vol. 6, no 3, p. 187-198Article in journal (Refereed)
    Abstract [en]

    Data-driven models have been used to detect system faults, thereby increasing industrial system availability. The ability to search data streams while dealing with concept drift are challenges for data-driven models. The objective of this work is to demonstrate a general method to manage concept drift when using one-class data-driven models. The method has been used to develop an automatically retrained and updated polygon-based model. In this paper, the available industrial data allowed for use of one-class data-driven models, and the polygon-based model was selected because it has previously been successful. Possible scenarios that allow one-class data-driven models to be retrained or updated were identified. Based on the identified scenarios, a method to automatically update a polygon-based model online is proposed. The method has been tested and verified using data collected from a Bosch Rexroth Mellansel AB hydraulic drive system. Data representing relevant faults was inserted into the data set in close collaboration with engineers from the company. The results show that the developed polygon-based model method was able to address the concept drift issue and was able to significantly improve the classification accuracy compared to the static polygon-based model. Thereby, the model could significantly improve industrial system availability when applied in the relevant production process. This paper shows that the developed polygon-based model requires small memory space while its updating procedure is simple and fast. Finally, the identified scenarios may be helpful as input for supporting other one-class data-driven models to cope with concept drift, thus increasing the generalizability of the results.

  • 39.
    Amadini, Roberto
    et al.
    University of Melbourne, Melbourne, Australia.
    Flener, Pierre
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Pearson, Justin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Scott, Joseph D.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Stuckey, Peter J.
    University of Melbourne, Melbourne, Australia.
    Tack, Guido
    Monash University, Melbourne, Australia.
    MiniZinc with strings2017In: Logic-Based Program Synthesis and Transformation, Springer, 2017, p. 59-75Conference paper (Refereed)
    Abstract [en]

    Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

  • 40.
    Amini, Sabor
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Using Requirement-Driven Symbolic Execution to Test Implementations of the CoAP and EDHOC Network Protocols2023Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    As the number of Internet of Things devices is increasing rapidly, it is of utmost significance that the implementations of protocols for constrained devices are bug-free. In general implementations of network protocols are error-prone due to their complex nature and ambiguities in the protocol specification. Implementations of network protocols often contain critical errors which could be exploited. To avoid bugs and vulnerabilities, the implementation of network protocols has to adhere to their specifications. The objective of this thesis is to use symbolic execution to test one implementation of the Ephemeral Diffie-Hellman Over COSE (EDHOC) protocol and one implementation of the Constrained Application Protocol (CoAP) against their specifications. The goal is to identify bugs such as crashes, non-conformances, memory errors, and security vulnerabilities that may occur if the implementations are not adhering to their specifications. The methodology to do this consists of three steps: 1) extracting requirements from the protocols Request For Comments and expressing them as formulas, 2) preparing the system under test for symbolic execution and applying the formulas during symbolic execution to detect any paths that violate a requirement, 3) for every path which violates a requirement, the concrete value that the symbolic execution engine provided is used in the unmodified implementation to validate the bug. In total seven non-conformances were found which have been reported to developers. One non-conformance was found in the EDHOC implementation and six were found in the CoAP implementation.

    Download full text (pdf)
    fulltext
  • 41.
    Andersson, Arne
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Balanced Binary Search Trees2005In: Handbook of Data Structures and Applications, CRC Press , 2005, p. 1392-Chapter in book (Other scientific)
  • 42.
    Andersson, Arne
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    General balanced trees1999In: Journal of Algorithms, Vol. 30, p. 1-28Article in journal (Refereed)
    Abstract [en]

    We show that, in order to achieve efficient maintenance of a balanced binary search tree, no shape restriction other than a logarithmic height is required. The obtained class of trees, general balanced trees, may be maintained at a logarithmic amortized cost with no balance information stored in the nodes. Thus, in the case when amortized bounds are sufficient, there is no need for sophisticated balance criteria.

    The maintenance algorithms use partial rebuilding. This is important for certain applications, and has previously been used with weight-balanced trees. We show that the amortized cost incurred by general balanced trees is lower than what has been shown for weight-balanced trees.

  • 43.
    Andersson, Arne
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Searching and Priority Queues in o(log n) Time2005In: Handbook of Data Structures and Applications, CRC Press , 2005, p. 1392-Chapter in book (Other (popular scientific, debate etc.))
  • 44.
    Andersson, Arne
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
    Carlsson, Per
    Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Ygge, Fredrik
    Resource Allocation with Wobbly Functions2002In: Computational Optimization and Applications, ISSN 0926-6003, Vol. 23, no 2, p. 171-200Article in journal (Other scientific)
  • 45.
    Andersson, Arne
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Davidsson, Paul
    Linden, Johan
    Measure-based performance evaluation1999In: Pattern Recognition Letters, Vol. 28Article in journal (Refereed)
    Abstract [en]

    The concept of measure functions for generalization performance is suggested. This concept provides an alternative way of selecting and evaluating learned classifiers, and it allows us to define the learning problem as a computational problem.

  • 46.
    Andersson, Arne
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Hagerup, Torben
    Nilsson, Stefan
    Raman, Rajeev
    Sorting in linear time?1998In: Journal of Computer and System Sciences, Vol. 57, p. 74-93Article in journal (Refereed)
    Abstract [en]

    We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0 .. 2^(w-1) in O(n loglog n) time, for arbitrary w >= log n, a significant improvement over the bound of O(n sqrt(log n)) achieved by the fusion trees of Fredman and Willard. Provided that w >= (log n)^(2+epsilon) for some fixed epsilon>0, the sorting can even be accomplished in linear expected time with a randomized algorithm.

    Both of our algorithms parallelize without loss on a unit-cost PRAM with a word length of w bits. The first one yields an algorithm that uses O(log n) time and O(n loglog n) operations on a deterministic CRCW PRAM. The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w >= (log n)^(2+epsilon) for some fixed epsilon>0.

    Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.

  • 47.
    Andersson, Arne
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Holmström, Jim
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    Willman, Mattias
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
    An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints2005In: Proc. 7th International Conference on E-Commerce Technology, Piscataway, NJ: IEEE , 2005, p. 17-24Conference paper (Refereed)
  • 48.
    Andersson, Arne
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Larsson, N. Jesper
    Swanson, Kurt
    Suffix trees on words1999In: Algorithmica, Vol. 23Article in journal (Refereed)
    Abstract [en]

    We discuss an intrinsic generalization of the suffix tree, designed to index a string of length n which has a natural partitioning into m multi-character substrings or words. This word suffix tree represents only the m suffixes that start at word boundaries. These boundaries are determined by delimiters, whose definition depends on the application.

    Since traditional suffix tree construction algorithms rely heavily on the fact that all suffixes are inserted, construction of a word suffix tree is nontrivial, in particular when only O(m) construction space is allowed. We solve this problem, presenting an algorithm with O(n) expected running time. In general, construction cost is Omega(n) due to the need of scanning the entire input. In applications that require strict node ordering, an additional cost of sorting O(m') characters arises, where m' is the number of distinct words. In either case, this is a significant improvement over previously known solutions.

    Furthermore, when the alphabet is small, we may assume that the $n$ characters in the input string occupy o(n) machine words. We illustrate that this can allow a word suffix tree to be built in sublinear time.

  • 49.
    Andersson, Arne
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
    Miltersen, Peter Bro
    Thorup, Mikkel
    Fusion trees can be implemented with AC0 instructions.1999In: Theoretical Computer Science, Vol. 205, p. 337-344Article in journal (Refereed)
    Abstract [en]

    Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC^o instructions only. More precisely, we show that a subset of {0,...,2^(w-1)} of size n can be maintained using linear space under insertion, deletion, predecessor, and successor queries, with O(log n/loglog n) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are fuinctions in AC^0. The AC^0 instructions used are not all available on today's computers.

  • 50.
    Andersson, Arne
    et al.
    Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
    Petersson, Ola
    Approximate Indexed Lists.1998In: Journal of Algorithms, Vol. 29, no 2Article in journal (Refereed)
    Abstract [en]

    Let the position of a list element in a list be the number of elements preceding it plus one. An indexed list supports the following operations on a list: Insert; delete; return the position of an element; and return the element at a certain position. The order in which the elements appear in the list is completely determined by where the insertions take place; we do not require the presence of any keys that induce the ordering.

    We consider approximate indexed lists, and show that a tiny relaxation in precision of the query operations allows a considerable improvement in time complexity. The new data structure has applications in two other problems; namely, list labeling and subset rank.

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