Ändra sökning
Avgränsa sökresultatet
1234567 101 - 150 av 50642
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 101.
    Abdlbari, Abdulbari
    Södertörns högskola, Institutionen för naturvetenskap, miljö och teknik.
    Parkeringsapplikationen: Utveckling av en mobilapplikation för iPhone.2013Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    Denna rapport beskriver tillvägagångssätt för framtagning av en mobilapplikation. Genom att använda mig av en enkätundersökning och användartester har jag tagit fram ett designdokument på en parkeringsapplikation för iPhone 4-modellen. Syftet med applikationen är bland annat att hjälpa bilförare att hitta laglig parkering för att därmed göra vägarna säkrare för alla och hjälpa bilförarna att slippa parkeringsböter.

  • 102.
    Abdlwafa, Alan
    et al.
    KTH, Skolan för datavetenskap och kommunikation (CSC).
    Edman, Henrik
    KTH, Skolan för datavetenskap och kommunikation (CSC).
    Distributed Graph Mining: A study of performance advantages in distributed data mining paradigms when processing graphs using PageRank on a single node cluster2015Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
    Abstract [en]

    Distributed data mining is a relatively new area within computer science that is steadily growing, emerging from the demands of being able to gather and process various distributed data by utilising clusters. This report presents the properties of graph structured data and what paradigms to use for efficiently processing the data type, based on comprehensive theoretical studies applied on practical tests performed on a single node cluster. The results in the study showcase the various performance aspects of processing graph data, using different open source paradigm frameworks and amount of shards used on input. A conclusion to be drawn from this study is that there are no real performance advantages to using distributed data mining paradigms specifically developed for graph data on single machines. 

  • 103.
    Abdollahi, Kamran
    et al.
    Computer and Science Department Iran University of Science and Technology Tehran, Iran.
    Shams Shafigh, Alireza
    Computer and Science Department Iran University of Science and Technology Tehran, Iran.
    Kassler, Andreas
    Karlstads universitet, Fakulteten för ekonomi, kommunikation och IT, Avdelningen för datavetenskap. Karlstads universitet, Fakulteten för ekonomi, kommunikation och IT, Centrum för HumanIT.
    Improving Performance of On Demand Multicast Routing by deleting lost join query packet2010Ingår i: Proceedings of The Sixth Advanced International Conference on Telecommunications - AICT 2010, IEEE conference proceedings, 2010, s. 316-322Konferensbidrag (Refereegranskat)
    Abstract [en]

    A Mobile ad hoc network is a collection of wireless nodes that dynamically organize themselves to form a network without the need for any fixed infrastructure or centralized administration. The network topology dynamically changes frequently in an unpredictable manner since nodes are free to move. Support for multicasting is essential in such environment as it is considered to be an efficient way to deliver information from source nodes to many client nodes. A problem with multicast routing algorithms is their efficiency as their forwarding structure determines the overall network resource consumption makes them significantly less efficient than unicast routing algorithms. In this research, we improve the performance of the popular ODMRP multicast routing protocol by restricting the domain of join query packets, which have been lost. This is achieved by augmenting the join query packets with minimum extra information (one field), which denotes the number of the visited node from previous forwarding group. Simulation results show, that our mechanisms significantly reduce the control traffic and thus the overall latency and power consumption in the network.

  • 104.
    Abdolmajid Ahmad, Bookan
    Linköpings universitet, Institutionen för datavetenskap. Linköpings universitet, Tekniska högskolan.
    Programmering av generativ konst i C# .Net2014Självständigt arbete på grundnivå (kandidatexamen), 180 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    Detta examensarbete utfördes på IDA (Institutionen för datavetenskap) vid Linköpings universitet. 

    Syftet med det här examensarbetet var att utveckla ett program som skulle skapa förutsättningar för generativ konst med hjälp av MyPaint som är ett digitalt rit/målarverktyg. Metoden gick ut på att registrera vad användaren skapat för komponenter, dvs. musinteraktioner och kortkommandon, och därefter använda dem algoritmiskt.

    Examensarbetet resulterades i ett program (SharpArt), som fångar musinteraktioner samt simulerar tangentbordstryckningar (kortkommandon) från och till Mypaint, vilket i sin tur skapar komponenter som används algoritmiskt. Programmet kan även positionera objektet på canvasen enligt det önskade koordinatvärdet.

  • 105.
    Abdul Khaliq, Ali
    et al.
    Örebro universitet, Institutionen för naturvetenskap och teknik.
    Pecora, Federico
    Örebro universitet, Institutionen för naturvetenskap och teknik.
    Saffiotti, Alessandro
    Örebro universitet, Institutionen för naturvetenskap och teknik.
    Point-to-point safe navigation of a mobile robot using stigmergy and RFID technology2016Ingår i: 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Institute of Electrical and Electronics Engineers (IEEE), 2016, s. 1497-1504, artikel-id 7759243Konferensbidrag (Refereegranskat)
    Abstract [en]

    Reliable autonomous navigation is still a challenging problem for robots with simple and inexpensive hardware. A key difficulty is the need to maintain an internal map of the environment and an accurate estimate of the robot’s position in this map. Recently, a stigmergic approach has been proposed in which a navigation map is stored into the environment, on a grid of RFID tags, and robots use it to optimally reach predefined goal points without the need for internal maps. While effective,this approach is limited to a predefined set of goal points. In this paper, we extend this approach to enable robots to travel to any point on the RFID floor, even if it was not previously identified as a goal location, as well as to keep a safe distance from any given critical location. Our approach produces safe, repeatable and quasi-optimal trajectories without the use of internal maps, self localization, or path planning. We report experiments run in a real apartment equipped with an RFID floor, in which a service robot either reaches or avoids a user who wears slippers equipped with an RFID tag reader.

  • 106.
    Abdulahad, Bassam
    et al.
    Linköpings universitet, Institutionen för datavetenskap.
    Lounis, Georgios
    Linköpings universitet, Institutionen för datavetenskap.
    A user interface for the ontology merging tool SAMBO2004Självständigt arbete på grundnivå (yrkesexamen)Studentuppsats
    Abstract [en]

    Ontologies have become an important tool for representing data in a structured manner. Merging ontologies allows for the creation of ontologies that later can be composed into larger ontologies as well as for recognizing patterns and similarities between ontologies. Ontologies are being used nowadays in many areas, including bioinformatics. In this thesis, we present a desktop version of SAMBO, a system for merging ontologies that are represented in the languages OWL and DAML+OIL. The system has been developed in the programming language JAVA with JDK (Java Development Kit) 1.4.2. The user can open a file locally or from the network and can merge ontologies using suggestions generated by the SAMBO algorithm. SAMBO provides a user-friendly graphical interface, which guides the user through the merging process.

  • 107.
    Abdulaziz Ali Haseeb, Mohamed
    KTH, Skolan för datavetenskap och kommunikation (CSC), Robotik, perception och lärande, RPL.
    Passive gesture recognition on unmodified smartphones using Wi-Fi RSSI2017Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    Smarta telefoner bärs idag av hundratals miljoner människor runt om i världen, och används för att utföra en mängd olika uppgifter, så som grundläggande kommunikation, internetsökning och online-inköp. På grund av begränsningar i storlek och energilagring är människa-telefon-gränssnitten dock i hög grad begränsade till de förhållandevis små skärmarna och enkla knappsatser.

     

    Industrin och forskarsamhället arbetar för att hitta vägar för att förbättra och bredda gränssnitten genom att antingen använda befintliga resurser såsom mikrofoner, kameror och tröghetssensorer, eller genom att införa nya specialiserade sensorer i telefonerna, som t.ex. kompakta radarenheter för gestigenkänning.

     

    Det begränsade strömbehovet hos radiofrekvenssignaler (RF) inspirerade oss till att undersöka om dessa kunde användas för att känna igen gester och aktiviteter i närheten av telefoner. Denna rapport presenterar en lösning för att känna igen gester med hjälp av ett s.k. recurrent neural network (RNN). Till skillnad från andra Wi-Fi-baserade lösningar kräver denna lösning inte en förändring av vare sig hårvara eller operativsystem, och ingenkänningen genomförs utan att inverka på den normala driften av andra applikationer på telefonen.

     

    Den utvecklade lösningen når en genomsnittlig noggranhet på 78% för detektering och klassificering av tre olika handgester, i ett antal olika konfigurationer vad gäller telefon och Wi-Fi-sändare. Rapporten innehåller även en analys av flera olika egenskaper hos den föreslagna lösningen, samt förslag till vidare arbete.

  • 108.
    Abdulhomeed, Bashar
    Örebro universitet, Handelshögskolan vid Örebro Universitet.
    Contemporary Research on e-democracy: A Literature Review2013Självständigt arbete på avancerad nivå (masterexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
  • 109.
    Abdulla, Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Delzanno, Giorgio
    Henda, Ben
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Monotonic Abstraction: on Efficient Verification of Parameterized Systems2009Ingår i: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 20, nr 5, s. 779-801Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We introduce the simple and efficient method of monotonic abstraction to prove safety properties for parameterized systems with linear topologies. A process in the system is a finite-state automaton, where the transitions are guarded by both local and global conditions. Processes may communicate via broadcast, rendez-vous and shared variables over finite domains. The method of monotonic abstraction derives an over-approximation of the induced transition system that allows the use of a simple class of regular expressions as a symbolic representation. Compared to traditional regular model checking methods, the analysis does not require the manipulation of transducers, and hence its simplicity and efficiency. We have implemented a prototype that works well on several mutual exclusion algorithms and cache coherence protocols

  • 110.
    Abdulla, Muntazar
    KTH, Skolan för informations- och kommunikationsteknik (ICT).
    Cu-tråd som elektrisk ledare i CIGS-tunnfilmssolceller för att sänka silvermängden utan att förlora verkningsgrad2015Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    Solcellsbranschen är större än någonsin tidigare och fortsätter växa samtidigt som konkurrensen mellan solcellstillverkare ökar, detta är något som pressar ner priserna på solceller och minskar lönsamheten för tillverkarna. Därför fokuserar detta projekt på hur man kan sänka mängden silver i solcellen utan att förlora verkningsgrad. Detta genomförs genom att arbeta som en problemlösare ihop med egna idéer. Genom att dra nytta av fördelarna med koppartrådar och skapa ett nytt solcellsmönster är detta möjligt då silver utgör 1/5 av tillverkningskostnaden. Projektet domineras av praktiskt arbete med fokus på innovation av standardsolcellen. Resultatet visade att man kan sänka silverpasta mängden med upp till 70 % i varje solcell genom att ta fram ett nytt silvertryck med mycket mindre silver ihop med koppartrådar. Det användes silver-belagda koppartrådar som ledare för att leda ut ström från ytan med fördelarna att det är tunna och blockerar därför solljuset mindre. Resultaten gav en verkningsgrad på 10-11% vilket är i nivå med produktionssolcellsmodulerna på Midsummer. Systemet bevisades även stabilt.

  • 111.
    Abdulla, PA
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. DEPARTMENT OF COMPUTER SYSTEMS.
    Boasson, L
    Bouajjani, A
    Effective Lossy Queue Languages.2001Ingår i: ICALP'2001, 28th Int. Colloquium on Automata, Languages and Programmming., 2001Konferensbidrag (Refereegranskat)
  • 112.
    Abdulla, PA
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. DEPARTMENT OF COMPUTER SYSTEMS.
    Jonsson, B
    Channel Abstractions in Protocol Verification2001Ingår i: CONCUR'2001, 12th Int. Conf. on Concurrency Theory, 2001Konferensbidrag (Refereegranskat)
  • 113.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
    Bouajjani, Ahmed
    Jonnson, Bengt
    Nilsson, Marcus
    Handling Global Conditions in Parameterized System Verification1999Ingår i: Proc. 11th Int. Conf. on Computer Aided Verification / [ed] Nicolas Halbwachs, Doron Peled, Berlin: Springer Verlag , 1999, s. 134-145Konferensbidrag (Refereegranskat)
    Abstract [en]

    We consider symbolic verification for a class of parameterized systems, where a system consists of a linear array of processes, and where an action of a process may in general be guarded by both local conditions restricting the state of the process about to perform the action, and global conditions defining the context in which the action is enabled. Such actions are present, e.g., in idealized versions of mutual exclusion protocols, such as the bakery and ticket algorithms by Lamport, Burn’s protocol, Dijkstra’s algorithm, and Szymanski’s algorithm. The presence of both local and global conditions makes the parameterized versions of these protocols infeasible to analyze fully automatically, using existing model checking methods for parameterized systems. In all these methods the actions are guarded only by local conditions involving the states of a finite set of processes. We perform verification using a standard symbolic reachability algorithm enhanced by an operation to accelerate the search of the state space. The acceleration operation computes the effect of an arbitrary number of applications of an action, rather than a single application. This is crucial for convergence of the analysis e.g. when applying the algorithm to the above protocols. We illustrate the use of our method through an application to Szymanski’s algorithm.

  • 114.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Cyriac, Aiswarya
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Chennai Math Inst, Madras, Tamil Nadu, India..
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Data Communicating Processes with Unreliable Channels2016Ingår i: Proceedings Of The 31St Annual ACM-IEEE Symposium On Logic In Computer Science (LICS 2016), 2016, s. 166-175Konferensbidrag (Refereegranskat)
    Abstract [en]

    We extend the classical model of lossy channel systems by considering systems that operate on a finite set of variables ranging over an infinite data domain. Furthermore, each message inside a channel is equipped with a data item representing its value. Although we restrict the model by allowing the variables to be only tested for (dis-)equality, we show that the state reachability problem is undecidable. In light of this negative result, we consider bounded-phase reachability, where the processes are restricted to performing either send or receive operations during each phase. We show decidability of state reachability in this case by computing a symbolic encoding of the set of system configurations that are reachable from a given configuration.

  • 115.
    Abdulla, Parosh A.
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Delzanno, Giorgio
    Univ Genoa, DIBRIS, Genoa, Italy..
    Parameterized verification2016Ingår i: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1433-2779, E-ISSN 1433-2787, Vol. 18, nr 5, s. 469-473Artikel i tidskrift (Övrigt vetenskapligt)
    Abstract [en]

    The goal of parameterized verification is to prove the correctness of a system specification regardless of the number of its components. The problem is of interest in several different areas: verification of hardware design, multithreaded programs, distributed systems, and communication protocols. The problem is undecidable in general. Solutions for restricted classes of systems and properties have been studied in areas like theorem proving, model checking, automata and logic, process algebra, and constraint solving. In this introduction to the special issue, dedicated to a selection of works from the Parameterized Verification workshop PV '14 and PV '15, we survey some of the works developed in this research area.

  • 116.
    Abdulla, Parosh A.
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Delzanno, Giorgio
    Univ Genoa, Genoa, Italy..
    Montali, Marco
    Free Univ Bolzano, Bolzano, Italy..
    Well Structured Transition Systems with History2015Ingår i: Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180, E-ISSN 2075-2180, nr 193, s. 115-128Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We propose a formal model of concurrent systems in which the history of a computation is explicitly represented as a collection of events that provide a view of a sequence of configurations. In our model events generated by transitions become part of the system configurations leading to operational semantics with historical data. This model allows us to formalize what is usually done in symbolic verification algorithms. Indeed, search algorithms often use meta-information, e.g., names of fired transitions, selected processes, etc., to reconstruct (error) traces from symbolic state exploration. The other interesting point of the proposed model is related to a possible new application of the theory of well-structured transition systems (wsts). In our setting wsts theory can be applied to formally extend the class of properties that can be verified using coverability to take into consideration (ordered and unordered) historical data. This can be done by using different types of representation of collections of events and by combining them with wsts by using closure properties of well-quasi orderings.

  • 117.
    Abdulla, Parosh
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Aronis, Stavros
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Sagonas, Konstantinos
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Comparing source sets and persistent sets for partial order reduction2017Ingår i: Models, Algorithms, Logics and Tools: Essays dedicated to Kim Guldstrand Larsen on the occasion of his 60th birthday, Springer, 2017, s. 516-536Kapitel i bok, del av antologi (Övrigt vetenskapligt)
  • 118.
    Abdulla, Parosh
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Aronis, Stavros
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Sagonas, Konstantinos
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Optimal dynamic partial order reduction2014Ingår i: Proc. 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New York: ACM Press, 2014, s. 373-384Konferensbidrag (Refereegranskat)
    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.

  • 119.
    Abdulla, Parosh
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Aronis, Stavros
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Sagonas, Konstantinos
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Source Sets: A Foundation for Optimal Dynamic Partial Order Reduction2017Ingår i: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 64, nr 4, artikel-id 25Artikel i tidskrift (Refereegranskat)
    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.

  • 120. Abdulla, Parosh Aziz
    Carrying Probabilities to the Infinite World2011Ingår i: CONCUR'2011, 22nd International Conference on Concurrency Theory., 2011Konferensbidrag (Refereegranskat)
  • 121.
    Abdulla, Parosh Aziz
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Forcing monotonicity in parameterized verification: From multisets to words2010Ingår i: SOFSEM 2010: Theory and Practice of Computer Science, Berlin: Springer-Verlag , 2010, s. 1-15Konferensbidrag (Refereegranskat)
  • 122.
    Abdulla, Parosh Aziz
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Regular model checking2012Ingår i: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1385-4879, E-ISSN 1571-8115, Vol. 14, nr 2, s. 109-118Artikel i tidskrift (Refereegranskat)
  • 123.
    Abdulla, Parosh Aziz
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. DEPARTMENT OF COMPUTER SYSTEMS.
    Using (Timed) Petri Nets for Verification of Parametrized (Timed) Systems2001Ingår i: VEPAS'2001, Verification of Parameterized Systems, 2001Konferensbidrag (Refereegranskat)
  • 124.
    Abdulla, Parosh Aziz
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Well (and better) quasi-ordered transition systems2010Ingår i: Bulletin of Symbolic Logic, ISSN 1079-8986, E-ISSN 1943-5894, Vol. 16, nr 4, s. 457-515Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper, we give a step by step introduction to the theory of well quasi-ordered transition systems. The framework combines two concepts, namely (i) transition systems which are monotonic wrt. a well-quasi ordering; and (ii) a scheme for symbolic backward reachability analysis. We describe several models with infinite-state spaces, which can be analyzed within the framework, e.g., Petri nets, lossy channel systems, timed automata, timed Petri nets, and multiset rewriting systems. We will also present better quasi-ordered transition systems which allow the design of efficient symbolic representations of infinite sets of states.

  • 125.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Aronis, Stavros
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Sagonas, Konstantinos
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Stateless model checking for TSO and PSO2015Ingår i: Tools and Algorithms for the Construction and Analysis of Systems: TACAS 2015, Springer Berlin/Heidelberg, 2015, s. 353-367Konferensbidrag (Refereegranskat)
  • 126.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Aronis, Stavros
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Sagonas, Konstantinos
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
    Stateless model checking for TSO and PSO2017Ingår i: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 54, nr 8, s. 789-818Artikel i tidskrift (Refereegranskat)
  • 127.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Bouajjani, Ahmed
    Ngo, Tuan Phong
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    A load-buffer semantics for total store ordering2018Ingår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 14, nr 1, artikel-id 9Artikel i tidskrift (Refereegranskat)
  • 128.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Bouajjani, Ahmed
    Ngo, Tuan Phong
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    The benefits of duality in verifying concurrent programs under TSO2016Ingår i: 27th International Conference on Concurrency Theory: CONCUR 2016, Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2016, s. 5:1-15Konferensbidrag (Refereegranskat)
  • 129.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Cederberg, Jonathan
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Analysis of message passing programs using SMT-solvers2013Ingår i: Automated Technology for Verification and Analysis: ATVA 2013, Springer Berlin/Heidelberg, 2013, s. 272-286Konferensbidrag (Refereegranskat)
  • 130.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Cederberg, Jonathan
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Timed lossy channel systems2012Ingår i: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2012, Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2012, s. 374-386Konferensbidrag (Refereegranskat)
  • 131.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Cederberg, Jonathan
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Modi, Subham
    Rezine, Othmane
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Saini, Gaurav
    MPass: An efficient tool for the analysis of message-passing programs2015Ingår i: Formal Aspects of Component Software, Springer, 2015, s. 198-206Konferensbidrag (Refereegranskat)
  • 132.
    Abdulla, Parosh Aziz
    et al.
    Department of Information Technology, Uppsala University, Sweden.
    Atig, Mohamed Faouzi
    Department of Information Technology, Uppsala University, Sweden.
    Chen, Yu-Fang
    Institute of Information Science, Academia Sinica, Taiwan.
    Holik, Lukas
    Faculty of Information Technology, Brno University of Technology, Czech Republic.
    Rezine, Ahmed
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Rümmer, Philipp
    Department of Information Technology, Uppsala University, Sweden.
    Stenman, Jari
    Department of Information Technology, Uppsala University, Sweden.
    String Constraints for Verification2014Ingår i: 26th International Conference on Computer Aided Verification (CAV 2014), Vienna, Austria, Jul. 9-12, 2014., Berlin: Springer, 2014, s. 150-166Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present a decision procedure for a logic that combines (i) word equations over string variables denoting words of arbitrary lengths, together with (ii) constraints on the length of words, and on (iii) the regular languages to which words belong. Decidability of this general logic is still open. Our procedure is sound for the general logic, and a decision procedure for a particularly rich fragment that restricts the form in which word equations are written. In contrast to many existing procedures, our method does not make assumptions about the maximum length of words. We have developed a prototypical implementation of our decision procedure, and integrated it into a CEGAR-based model checker for the analysis of programs encoded as Horn clauses. Our tool is able to automatically establish the correctness of several programs that are beyond the reach of existing methods.

  • 133.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Holík, Lukás
    Rezine, Ahmed
    Rümmer, Philipp
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Stenman, Jari
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Norn: An SMT solver for string constraints2015Ingår i: Computer Aided Verification: Part I, Springer, 2015, s. 462-469Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present version 1.0 of the Norn SMT solver for string constraints. Norn is a solver for an expressive constraint language, including word equations, length constraints, and regular membership queries. As a feature distinguishing Norn from other SMT solvers, Norn is a decision procedure under the assumption of a set of acyclicity conditions on word equations, without any restrictions on the use of regular membership.

  • 134.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Automatic fence insertion in integer programs via predicate abstraction2012Ingår i: Static Analysis, Berlin: Springer-Verlag , 2012, s. 164-180Konferensbidrag (Refereegranskat)
  • 135.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Sweden.
    Atig, Mohamed Faouzi
    Uppsala University, Sweden.
    Chen, Yu-Fang
    Academia Sinica, Taiwan.
    Leonardsson, Carl
    Uppsala University, Sweden.
    Rezine, Ahmed
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Automatic fence insertion in integer programs via predicate abstraction2012Ingår i: Static Analysis: 19th International Symposium, SAS 2012, Deauville, France, September 11-13, 2012. Proceedings / [ed] Antoine Miné, David Schmidt, Springer Berlin/Heidelberg, 2012, s. 164-180Konferensbidrag (Refereegranskat)
    Abstract [en]

    We propose an automatic fence insertion and verification framework for concurrent programs running under relaxed memory. Unlike previous approaches to this problem, which allow only variables of finite domain, we target programs with (unbounded) integer variables. The problem is difficult because it has two different sources of infiniteness: unbounded store buffers and unbounded integer variables. Our framework consists of three main components: (1) a finite abstraction technique for the store buffers, (2) a finite abstraction technique for the integer variables, and (3) a counterexample guided abstraction refinement loop of the model obtained from the combination of the two abstraction techniques. We have implemented a prototype based on the framework and run it successfully on all standard benchmarks together with several challenging examples that are beyond the applicability of existing methods.

  • 136.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Counter-Example Guided Fence Insertion under TSO2012Ingår i: Tools and Algorithms for the Construction and Analysis of Systems, Berlin: Springer-Verlag , 2012, s. 204-219Konferensbidrag (Refereegranskat)
  • 137.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Sweden.
    Atig, Mohamed Faouzi
    Uppsala University, Sweden.
    Chen, Yu-Fang
    Academia Sinica, Taiwan.
    Leonardsson, Carl
    Uppsala University, Sweden.
    Rezine, Ahmed
    Linköpings universitet, Institutionen för datavetenskap, ESLAB - Laboratoriet för inbyggda system. Linköpings universitet, Tekniska högskolan.
    Counter-Example Guided Fence Insertion under TSO2012Ingår i: TACAS 2012, Berlin, Heidelberg: Springer , 2012Konferensbidrag (Refereegranskat)
    Abstract [en]

    We give a sound and complete fence insertion procedure for concurrentfinite-state programs running under the classical TSO memory model. Thismodel allows “write to read” relaxation corresponding to the addition of an unboundedstore buffer between each processor and the main memory. We introducea novel machine model, called the Single-Buffer (SB) semantics, and show thatthe reachability problem for a program under TSO can be reduced to the reachabilityproblem under SB. We present a simple and effective backward reachabilityanalysis algorithm for the latter, and propose a counter-example guided fence insertionprocedure. The procedure is augmented by a placement constraint thatallows the user to choose places inside the program where fences may be inserted.For a given placement constraint, we automatically infer all minimal setsof fences that ensure correctness. We have implemented a prototype and run itsuccessfully on all standard benchmarks together with several challenging examplesthat are beyond the applicability of existing methods.

  • 138.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Chen, Yu-Fang
    Academia Sinica.
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Ahmed
    Linköping University.
    MEMORAX, a Precise and Sound Tool for Automatic Fence Insertion under TSO2013Ingår i: Tools and Algorithms for the Construction and Analysis of Systems, Springer Berlin/Heidelberg, 2013, s. 530-536Konferensbidrag (Refereegranskat)
  • 139.
    Abdulla, Parosh Aziz
    et al.
    Uppsala University, Sweden.
    Atig, Mohamed Faouzi
    Uppsala University, Sweden.
    Chen, Yu-Fang
    Academia Sinica, Taiwan.
    Leonardsson, Carl
    Uppsala University, Sweden.
    Rezine, Ahmed
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Memorax, a Precise and Sound Tool for Automatic Fence Insertion under TSO2013Ingår i: Tools and Algorithms for the Construction and Analysis of Systems: 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings, Springer Berlin/Heidelberg, 2013, s. 530-536Konferensbidrag (Refereegranskat)
    Abstract [en]

    We introduce MEMORAX, a tool for the verification of control state reachability (i.e., safety properties) of concurrent programs manipulating finite range and integer variables and running on top of weak memory models. The verification task is non-trivial as it involves exploring state spaces of arbitrary or even infinite sizes. Even for programs that only manipulate finite range variables, the sizes of the store buffers could grow unboundedly, and hence the state spaces that need to be explored could be of infinite size. In addition, MEMORAX in- corporates an interpolation based CEGAR loop to make possible the verification of control state reachability for concurrent programs involving integer variables. The reachability procedure is used to automatically compute possible memory fence placements that guarantee the unreachability of bad control states under TSO. In fact, for programs only involving finite range variables and running on TSO, the fence insertion functionality is complete, i.e., it will find all minimal sets of memory fence placements (minimal in the sense that removing any fence would result in the reachability of the bad control states). This makes MEMORAX the first freely available, open source, push-button verification and fence insertion tool for programs running under TSO with integer variables.

  • 140.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Delzanno, Giorgio
    Podelski, Andreas
    Push-down automata with gap-order constraints2013Ingår i: Fundamentals of Software Engineering: FSEN 2013, Springer Berlin/Heidelberg, 2013, s. 199-216Konferensbidrag (Refereegranskat)
  • 141.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ganjei, Zeinab
    Rezine, Ahmed
    Zhu, Yunyun
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Verification of Cache Coherence Protocols wrt. Trace Filters2015Ingår i: Proc. 15th Conference on Formal Methods in Computer-Aided Design, Piscataway, NJ: IEEE , 2015, s. 9-16Konferensbidrag (Refereegranskat)
  • 142.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Jonsson, Bengt
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Stateless model checking for POWER2016Ingår i: Computer Aided Verification: Part II, Springer, 2016, s. 134-156Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present the first framework for efficient application of stateless model checking (SMC) to programs running under the relaxed memory model of POWER. The framework combines several contributions. The first contribution is that we develop a scheme for systematically deriving operational execution models from existing axiomatic ones. The scheme is such that the derived execution models are well suited for efficient SMC. We apply our scheme to the axiomatic model of POWER from [8]. Our main contribution is a technique for efficient SMC, called Relaxed Stateless Model Checking (RSMC), which systematically explores the possible inequivalent executions of a program. RSMC is suitable for execution models obtained using our scheme. We prove that RSMC is sound and optimal for the POWER memory model, in the sense that each complete program behavior is explored exactly once. We show the feasibility of our technique by providing an implementation for programs written in C/pthreads.

  • 143.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Kara, Ahmet
    Rezine, Othmane
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Verification of buffered dynamic register automata2015Ingår i: Networked Systems: NETYS 2015, Springer, 2015, s. 15-31Konferensbidrag (Refereegranskat)
  • 144.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Kara, Ahmet
    Rezine, Othmane
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Verification of Dynamic Register Automata2014Ingår i: Leibniz International Proceedings in Informatics: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014), 2014Konferensbidrag (Refereegranskat)
    Abstract [en]

    We consider the verification problem for Dynamic Register Automata (Dra). Dra extend classical register automata by process creation. In this setting, each process is equipped with a finite number of registers in which the process IDs of other processes can be stored. A process can communicate with processes whose IDs are stored in its registers and can send them the content of its registers. The state reachability problem asks whether a Dra reaches a configuration where at least one process is in an error state. We first show that this problem is in general undecidable. This result holds even when we restrict the analysis to configurations where the maximal length of the simple paths in their underlying (un)directed communication graphs are bounded by some constant. Then we introduce the model of degenerative Dra which allows non-deterministic reset of the registers. We prove that for every given Dra, its corresponding degenerative one has the same set of reachable states. While the state reachability of a degenerative Dra remains undecidable, we show that the problem becomes decidable with nonprimitive-recursive complexity when we restrict the analysis to strongly bounded configurations, i.e. configurations whose underlying undirected graphs have bounded simple paths. Finally, we consider the class of strongly safe Dra, where all the reachable configurations are assumed to be strongly bounded. We show that for strongly safe Dra, the state reachability problem becomes decidable. 

  • 145.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Kaxiras, Stefanos
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorarkitektur och datorkommunikation.
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ros, Alberto
    Zhu, Yunyun
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Fencing programs with self-invalidation and self-downgrade2016Ingår i: Formal Techniques for Distributed Objects, Components, and Systems, Springer, 2016, s. 19-35Konferensbidrag (Refereegranskat)
  • 146.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Kaxiras, Stefanos
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorarkitektur och datorkommunikation.
    Leonardsson, Carl
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ros, Alberto
    Zhu, Yunyun
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Mending fences with self-invalidation and self-downgrade2018Ingår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 14, nr 1, artikel-id 6Artikel i tidskrift (Refereegranskat)
  • 147.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Lång, Magnus
    Ngo, Tuan Phong
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Precise and sound automatic fence insertion procedure under PSO2015Ingår i: Networked Systems: NETYS 2015, Springer, 2015, s. 32-47Konferensbidrag (Refereegranskat)
  • 148.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Meyer, Roland
    Salehi, Mehdi Seyed
    What's decidable about availability languages?2015Ingår i: Proc. 35th IARCS Conference on Foundation of Software Technology and Theoretical Computer Science, Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2015, s. 192-205Konferensbidrag (Refereegranskat)
  • 149.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Ngo, Tuan-Phong
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    The Best of Both Worlds: Trading efficiency and optimality in fence insertion for TSO2015Ingår i: Programming Languages and Systems: ESOP 2015, Springer Berlin/Heidelberg, 2015, s. 308-332Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present a method for automatic fence insertion in concurrent programs running under weak memory models that provides the best known trade-off between efficiency and optimality. On the one hand, the method can efficiently handle complex aspects of program behaviors such as unbounded buffers and large numbers of processes. On the other hand, it is able to find small sets of fences needed for ensuring correctness of the program. To this end, we propose a novel notion of correctness, called persistence, that compares the behavior of the program under the weak memory semantics with that under the classical interleaving (SC) semantics. We instantiate our framework for the Total Store Ordering (TSO) memory model, and give an algorithm that reduces the fence insertion problem under TSO to the reachability problem for programs running under SC. Furthermore, we provide an abstraction scheme that substantially increases scalability to large numbers of processes. Based on our method, we have implemented a tool and run it successfully on a wide range benchmarks.

  • 150.
    Abdulla, Parosh Aziz
    et al.
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Atig, Mohamed Faouzi
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Rezine, Othmane
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Stenman, Jari
    Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
    Budget-bounded model-checking pushdown systems2014Ingår i: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 45, nr 2, s. 273-301Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We address the verification problem for concurrent programs modeled as multi-pushdown systems (MPDS). In general, MPDS are Turing powerful and hence come along with undecidability of all basic decision problems. Because of this, several subclasses of MPDS have been proposed and studied in the literature (Atig et al. in LNCS, Springer, Berlin, 2005; La Torre et al. in LICS, IEEE, 2007; Lange and Lei in Inf Didact 8, 2009; Qadeer and Rehof in TACAS, LNCS, Springer, Berlin, 2005). In this paper, we propose the class of bounded-budget MPDS, which are restricted in the sense that each stack can perform an unbounded number of context switches only if its depth is below a given bound, and a bounded number of context switches otherwise. We show that the reachability problem for this subclass is Pspace-complete and that LTL-model-checking is Exptime-complete. Furthermore, we propose a code-to-code translation that inputs a concurrent program and produces a sequential program such that running under the budget-bounded restriction yields the same set of reachable states as running . Moreover, detecting (fair) non-terminating executions in can be reduced to LTL-Model-Checking of . By leveraging standard sequential analysis tools, we have implemented a prototype tool and applied it on a set of benchmarks, showing the feasibility of our translation.

1234567 101 - 150 av 50642
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf