Search For:

Displaying 1-50 out of 70 total
FlexPRICE: Flexible Provisioning of Resources in a Cloud Environment
Found in: Cloud Computing, IEEE International Conference on
By Thomas A. Henzinger, Anmol V. Singh, Vasu Singh, Thomas Wies, Damien Zufferey
Issue Date:July 2010
pp. 83-90
Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We claim that, in order to realize the full potential of cloud computing, the user must be presented with a...
 
The Propagation Approach for Computing Biochemical Reaction Networks
Found in: IEEE/ACM Transactions on Computational Biology and Bioinformatics
By Thomas A. Henzinger,Maria Mateescu
Issue Date:March 2013
pp. 310-322
We introduce propagation models (PMs), a formalism able to express several kinds of equations that describe the behavior of biochemical reaction networks. Furthermore, we introduce the propagation abstract data type (PADT), which separates concerns regardi...
 
A Theory of Synchronous Relational Interfaces
Found in: ACM Transactions on Programming Languages and Systems (TOPLAS)
By Ben Lickly, Edward A. Lee, Edward A. Lee, Stavros Tripakis, Stavros Tripakis, Thomas A. Henzinger, Thomas A. Henzinger
Issue Date:July 2011
pp. 1-41
Compositional theories are crucial when designing large and complex systems from smaller components. In this work we propose such a theory for synchronous concurrent systems. Our approach follows so-called interface theories, which use game-theoretic inter...
     
Qualitative concurrent parity games
Found in: ACM Transactions on Computational Logic (TOCL)
By Krishnendu Chatterjee, Luca De Alfaro, Luca De Alfaro, Thomas A. Henzinger, Thomas A. Henzinger
Issue Date:July 2011
pp. 1-51
We consider two-player games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the tw...
     
Quantitative languages
Found in: ACM Transactions on Computational Logic (TOCL)
By Krishnendu Chatterjee, Laurent Doyen, Laurent Doyen, Thomas A. Henzinger, Thomas A. Henzinger
Issue Date:July 2010
pp. 1-38
Quantitative generalizations of classical languages, which assign to each word a real number instead of a Boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to d...
     
Trading Memory for Randomness
Found in: Quantitative Evaluation of Systems, International Conference on
By Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger
Issue Date:September 2004
pp. 206-217
Strategies in repeated games can be classified as to whether or not they use memory and/or randomization. We consider Markov decision processes and 2-player graph games, both of the deterministic and probabilistic varieties. We characterize when memory and...
 
Games with Secure Equilibria
Found in: Logic in Computer Science, Symposium on
By Krishnendu Chatterjee, Thomas A. Henzinger, Marcin Jurdzinski
Issue Date:July 2004
pp. 160-169
In 2-player non-zero-sum games, Nash equilibria capture the options for rational behavior if each player attempts to maximize her payoff. In contrast to classical game theory, we consider lexicographic objectives: first, each player tries to maximize her o...
 
Concurrent Omega-Regular Games
Found in: Logic in Computer Science, Symposium on
By Luca de Alfaro, Thomas A. Henzinger
Issue Date:June 2000
pp. 141
We consider two-player games, which are played on a finite state space for an infinite number of rounds. The games are concurrent, that is, in each round, the two players choose their moves independently and simultaneously; the current state and the two mo...
 
Quantitative Evaluation of BFT Protocols
Found in: Quantitative Evaluation of Systems, International Conference on
By Raluca Halalai,Thomas A. Henzinger,Vasu Singh
Issue Date:September 2011
pp. 255-264
Byzantine Fault Tolerant (BFT) protocols aim to improve the reliability of distributed systems. They enable systems to tolerate arbitrary failures in a bounded number of nodes. BFT protocols are usually proven correct for certain safety and liveness proper...
 
The Complexity of Quantitative Information Flow Problems
Found in: Computer Security Foundations Symposium, IEEE
By Pavol Cerný, Krishnendu Chatterjee, Thomas A. Henzinger
Issue Date:June 2011
pp. 205-217
In this paper, we investigate the computational complexity of quantitative information flow (QIF) problems. Information-theoretic quantitative relaxations of noninterference (based on Shannon entropy)have been introduced to enable more fine-grained reasoni...
 
Temporal Specifications with Accumulative Values
Found in: Logic in Computer Science, Symposium on
By Udi Boker, Krishnendu Chatterjee, Thomas A. Henzinger, Orna Kupferman
Issue Date:June 2011
pp. 43-52
There is recently a significant effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions, aiming for a general and flexible framework for q...
 
SABRE: A Tool for Stochastic Analysis of Biochemical Reaction Networks
Found in: Quantitative Evaluation of Systems, International Conference on
By Frederic Didier, Thomas A. Henzinger, Maria Mateescu, Verena Wolf
Issue Date:September 2010
pp. 193-194
The importance of stochasticity within biological systems has been shown repeatedly during the last years and has raised the need for efficient stochastic tools. We present SABRE, a tool for stochastic analysis of biochemical reaction networks. SABRE imple...
 
Fast Adaptive Uniformization of the Chemical Master Equation
Found in: High Performance Computational Systems Biology, International Workshop on
By Frederic Didier, Thomas A. Henzinger, Maria Mateescu, Verena Wolf
Issue Date:October 2009
pp. 118-127
Within systems biology there is an increasing interest in the stochastic behavior of biochemical reaction networks. An appropriate stochastic description is provided by the chemical master equation, which represents a continuous-time Markov chain (CTMC). S...
 
Expressiveness and Closure Properties for Quantitative Languages
Found in: Logic in Computer Science, Symposium on
By Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger
Issue Date:August 2009
pp. 199-208
Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the ma...
 
Logical Reliability of Interacting Real-Time Tasks
Found in: Design, Automation and Test in Europe Conference and Exhibition
By Krishnendu Chatterjee, Arkadeb Ghosal, Thomas A. Henzinger, Daniel Iercan, Christoph M. Kirsch, Claudio Pinello, Alberto Sangiovanni-Vincentelli
Issue Date:March 2008
pp. 909-914
We propose the notion of logical reliability for real-time program tasks that interact through periodically updated program variables. We describe a reliability analysis that checks if the given short-term (e.g., single-period) reliability of a program var...
 
The Discipline of Embedded Systems Design
Found in: Computer
By Thomas A. Henzinger, Joseph Sifakis
Issue Date:October 2007
pp. 32-40
The wall between computer science and electrical engineering has kept the potential of embedded systems at bay. It is time to build a new scientific foundation with embedded systems design as the cornerstone, which will ensure a systematic and even-handed ...
 
An Application of Web-Service Interfaces
Found in: Web Services, IEEE International Conference on
By Dirk Beyer, Arindam Chakrabarti, Thomas A. Henzinger, Sanjit A. Seshia
Issue Date:July 2007
pp. 831-838
We present a case study to illustrate our formalism for the specification and verification of the method-invocation behavior of web-service applications constructed from asynchronously interacting multi-threaded distributed components. Our model is express...
 
Strategy Improvement for Concurrent Reachability Games
Found in: Quantitative Evaluation of Systems, International Conference on
By Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger
Issue Date:September 2006
pp. 291-300
<p>A concurrent reachability game is a two-player game played on a graph: at each state, the players simultaneously and independently select moves; the two moves determine jointly a probability distribution over the successor states. The objective fo...
 
Compositional Quantitative Reasoning
Found in: Quantitative Evaluation of Systems, International Conference on
By Krishnendu Chatterjee, Luca de Alfaro, Marco Faella, Thomas A. Henzinger, Rupak Majumdar, Marielle Stoelinga
Issue Date:September 2006
pp. 179-188
<p>We present a compositional theory of system verification, where specifications assign real-numbered costs to systems. These costs can express a wide variety of quantitative system properties, such as resource consumption, price, or a measure of ho...
 
An Interface Algebra for Real-Time Components
Found in: Real-Time and Embedded Technology and Applications Symposium, IEEE
By Thomas A. Henzinger, Slobodan Matic
Issue Date:April 2006
pp. 253-266
We present an assume-guarantee interface algebra for real-time components. In our formalism a component implements a set of task sequences that share a resource. A component interface consists of an arrival rate function and a latency for each task sequenc...
 
Trading End-to-End Latency for Composability
Found in: Real-Time Systems Symposium, IEEE International
By Slobodan Matic, Thomas A. Henzinger
Issue Date:December 2005
pp. 99-110
The periodic resource model for hierarchical, compositional scheduling abstracts task groups by resource requirements. We study this model in the presence of dataflow constraints between the tasks within a group (intragroup dependencies), and between tasks...
 
Robustness of Sequential Circuits
Found in: Application of Concurrency to System Design, International Conference on
By Laurent Doyen, Thomas A. Henzinger, Axel Legay, Dejan Nickovic
Issue Date:June 2010
pp. 77-84
Digital components play a central role in the design of complex embedded systems. These components are interconnected with other, possibly analog, devices and the physical environment. This environment cannot be entirely captured and can provide inaccurate...
 
Mean-Payoff Parity Games
Found in: Logic in Computer Science, Symposium on
By Krishnendu Chatterjee, Thomas A. Henzinger, Marcin Jurdzinski
Issue Date:June 2005
pp. 178-187
Games played on graphs may have qualitative objectives, such as the satisfaction of an ?-regular property, or quantitative objectives, such as the optimization of a realvalued reward. When games are used to model reactive systems with both fairness assumpt...
 
Generating Tests from Counterexamples
Found in: Software Engineering, International Conference on
By Dirk Beyer, Adam J. Chlipala, Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar
Issue Date:May 2004
pp. 326-335
We have extended the software model checker BLAST to automatically generate test suites that guarantee full coverage with respect to a given predicate. More precisely, given a C program and a target predicate p, BLAST determines the set L of program locati...
 
Convertibility verification and converter synthesis: two faces of the same coin
Found in: Computer-Aided Design, International Conference on
By Alberto L. Sangiovanni-Vincentelli, Thomas A. Henzinger, Luca de Alfaro, Roberto Passerone
Issue Date:November 2002
pp. 132-139
An essential problem in component-based design is how to compose components designed in isolation. Several approaches have been proposed for specifying component interfaces that capture behavioral aspects such as interaction protocols, and for verifying in...
 
Formal Specification and Verification of a Dataflow Processor Array
Found in: Computer-Aided Design, International Conference on
By Thomas A. Henzinger, Xiaojun Liu, Shaz Qadeer, Sriram K. Rajamani
Issue Date:November 1999
pp. 494
We describe the formal specification and verification of the VGI parallel DSP chip, which contains 64 compute processors with ~30K gates in each processor. Our effort coincided in time with the
 
Alternating-time Temporal Logic
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Rajeev Alur, Thomas A. Henzinger, Orna Kupferman
Issue Date:October 1997
pp. 100
Temporal logic comes in two varieties: linear-time temporal logic assumes implicit universal quantification over all paths that are generated by system moves; branching-time temporal logic allows explicit existential and universal quantification over all p...
 
Reactive Modules
Found in: Logic in Computer Science, Symposium on
By Rajeev Alur, Thomas A. Henzinger
Issue Date:July 1996
pp. 207
We present a formal model for concurrent systems. The model represents synchronous and asynchronous components in a uniform framework that supports compositional (assume-guarantee) and hierarchical (stepwise refinement) reasoning. While synchronous models ...
 
Automatic Symbolic Verification of Embedded Systems
Found in: IEEE Transactions on Software Engineering
By Rajeev Alur, Thomas A. Henzinger, Pei-Hsin Ho
Issue Date:March 1996
pp. 181-201
<p><b>Abstract</b>—We present a model-checking procedure and its implementation for the automatic verification of embedded systems. The system components are described as <it>Hybrid Automata</it>—communicating machines with fi...
 
Compositional Specifications for ioco Testing
Found in: 2014 IEEE Seventh International Conference on Software Testing, Verification and Validation (ICST)
By Przemyslaw Daca,Thomas A. Henzinger,Willibald Krenn,Dejan Nickovic
Issue Date:March 2014
pp. 373-382
Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to th...
 
Scheduling large jobs by abstraction refinement
Found in: Proceedings of the sixth conference on Computer systems (EuroSys '11)
By Damien Zufferey, Thomas A. Henzinger, Thomas Wies, Vasu Singh
Issue Date:April 2011
pp. 329-342
The static scheduling problem often arises as a fundamental problem in real-time systems and grid computing. We consider the problem of statically scheduling a large job expressed as a task graph on a large number of computing nodes, such as a data center....
     
A marketplace for cloud resources
Found in: Proceedings of the tenth ACM international conference on Embedded software (EMSOFT '10)
By Anmol V. Singh, Damien Zufferey, Thomas A. Henzinger, Thomas Wies, Vasu Singh
Issue Date:October 2010
pp. 1-8
Cloud computing is an emerging paradigm aimed to offer users pay-per-use computing resources, while leaving the burden of managing the computing infrastructure to the cloud provider. We present a new programming and pricing model that gives the cloud user ...
     
An Eclipse Plug-in for Model Checking
Found in: International Conference on Program Comprehension
By Dirk Beyer, Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar
Issue Date:June 2004
pp. 251
While model checking has been successful in uncovering subtle bugs in code, its adoption in software engineering practice has been hampered by the absence of a simple interface to the programmer in an integrated development environment. We describe an inte...
 
Decomposing Refinement Proofs using Assume-Guarantee Reasoning
Found in: Computer-Aided Design, International Conference on
By Thomas A. Henzinger, Shaz Qadeer, Sriram K. Rajamani
Issue Date:November 2000
pp. 245
Model-checking algorithms can be used to verify, formally and automatically, if a low-level description of a design conforms with a high-level description. However, for designs with very large state spaces, prior to the application of an algorithm, the ref...
 
Battery transition systems
Found in: Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '14)
By Arjun Radhakrishna, Thomas A. Henzinger, Udi Boker
Issue Date:January 2014
pp. 595-606
The analysis of the energy consumption of software is an important goal for quantitative formal methods. Current methods, using weighted transition systems or energy games, model the energy source as an ideal resource whose status is characterized by one n...
     
Distributed queues in shared memory: multicore performance and scalability through quantitative relaxation
Found in: Proceedings of the ACM International Conference on Computing Frontiers (CF '13)
By Ali Sezgin, Ana Sokolova, Andreas Haas, Christoph M. Kirsch, Hannes Payer, Michael Lippautz, Thomas A. Henzinger
Issue Date:May 2013
pp. 1-9
A prominent remedy to multicore scalability issues in concurrent data structure implementations is to relax the sequential specification of the data structure. We present distributed queues (DQ), a new family of relaxed concurrent queue implementations. DQ...
     
The Propagation Approach for Computing Biochemical Reaction Networks
Found in: IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
By Maria Mateescu, Thomas A. Henzinger
Issue Date:March 2013
pp. 310-322
We introduce propagation models (PMs), a formalism able to express several kinds of equations that describe the behavior of biochemical reaction networks. Furthermore, we introduce the propagation abstract data type (PADT), which separates concerns regardi...
     
Quantitative relaxation of concurrent data structures
Found in: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '13)
By Ali Sezgin, Ana Sokolova, Christoph M. Kirsch, Hannes Payer, Thomas A. Henzinger
Issue Date:January 2013
pp. 317-328
There is a trade-off between performance and correctness in implementing concurrent data structures. Better performance may be achieved at the expense of relaxing correctness, by redefining the semantics of data structures. We address such a redefinition o...
     
Quantitative abstraction refinement
Found in: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '13)
By Arjun Radhakrishna, Pavol Cerny, Thomas A. Henzinger
Issue Date:January 2013
pp. 115-128
We propose a general framework for abstraction with respect to quantitative properties, such as worst-case execution time, or power consumption. Our framework provides a systematic way for counter-example guided abstraction refinement for quantitative prop...
     
Conditional model checking: a technique to pass information between verifiers
Found in: Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering (FSE '12)
By Dirk Beyer, M. Erkan Keremoglu, Philipp Wendler, Thomas A. Henzinger
Issue Date:November 2012
pp. 1-11
Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in...
     
Biology as reactivity
Found in: Communications of the ACM
By David Harel, Jasmin Fisher, Thomas A. Henzinger
Issue Date:October 2011
pp. 72-82
Exploring the connection of biology with reactive systems to better understand living systems.
     
From Boolean to quantitative notions of correctness
Found in: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '10)
By Thomas A. Henzinger
Issue Date:January 2010
pp. 40-ff
Classical formalizations of systems and properties are boolean: given a system and a property, the property is either true or false of the system. Correspondingly, classical methods for system analysis determine the truth value of a property, preferably gi...
     
On relational interfaces
Found in: Proceedings of the seventh ACM international conference on Embedded software (EMSOFT '09)
By Ben Lickly, Edward A. Lee, Stavros Tripakis, Thomas A. Henzinger
Issue Date:October 2009
pp. 67-76
In this paper we extend the work of Alfaro, Henzinger et al. on interface theories for component-based design. Existing interface theories often fail to capture functional relations between the inputs and outputs of an interface. For example, a simple sync...
     
Finitary winning in ω-regular games
Found in: ACM Transactions on Computational Logic (TOCL)
By Florian Horn, Krishnendu Chatterjee, Thomas A. Henzinger
Issue Date:October 2009
pp. 1-27
Games on graphs with ω-regular objectives provide a model for the control and synthesis of reactive systems. Every ω-regular objective can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens...
     
Interface theories with component reuse
Found in: Proceedings of the 7th ACM international conference on Embedded software (EMSOFT '08)
By Barbara Jobstmann, Laurent Doyen, Tatjana Petrov, Thomas A. Henzinger
Issue Date:October 2008
pp. 21-27
Interface theories have been proposed to support incremental design and independent implementability. Incremental design means that the compatibility checking of interfaces can proceed for partial system descriptions, without knowing the interfaces of all ...
     
Model checking transactional memories
Found in: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation (PLDI '08)
By Barbara Jobstmann, Rachid Guerraoui, Thomas A. Henzinger, Vasu Singh
Issue Date:June 2008
pp. 1-1
Model checking software transactional memories (STMs) is difficult because of the unbounded number, length, and delay of concurrent transactions and the unbounded size of the memory. We show that, under certain conditions, the verification problem can be r...
     
Logical reliability of interacting real-time tasks
Found in: Proceedings of the conference on Design, automation and test in Europe (DATE '08)
By Alberto Sangiovanni-Vincentelli, Arkadeb Ghosal, Christoph M. Kirsch, Claudio Pinello, Daniel Iercan, Krishnendu Chatterjee, Thomas A. Henzinger
Issue Date:March 2008
pp. 1-30
We propose the notion of logical reliability for real-time program tasks that interact through periodically updated program variables. We describe a reliability analysis that checks if the given short-term (e.g., single-period) reliability of a program var...
     
The embedded machine: Predictable, portable real-time code
Found in: ACM Transactions on Programming Languages and Systems (TOPLAS)
By Christoph M. Kirsch, Thomas A. Henzinger
Issue Date:October 2007
pp. 33-es
The Embedded Machine is a virtual machine that mediates in real time the interaction between software processes and physical processes. It separates the compilation of embedded programs into two phases. The first phase, the platform-independent compiler ph...
     
Path invariants
Found in: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation (PLDI '07)
By Andrey Rybalchenko, Dirk Beyer, Rupak Majumdar, Thomas A. Henzinger
Issue Date:June 2007
pp. 300-309
The success of software verification depends on the ability to find a suitable abstraction of a program automatically. We propose a method for automated abstraction refinement which overcomes some limitations of current predicate discovery schemes. In curr...
     
A hierarchical coordination language for interacting real-time tasks
Found in: Proceedings of the 6th ACM & IEEE International conference on Embedded software (EMSOFT '06)
By Alberto Sangiovanni-Vincentelli, Arkadeb Ghosal, Christoph M. Kirsch, Daniel Iercan, Thomas A. Henzinger
Issue Date:October 2006
pp. 132-141
We designed and implemented a new programming language called Hierarchical Timing Language (HTL) for hard realtime systems. Critical timing constraints are specified within the language,and ensured by the compiler. Programs in HTL are extensible in two dim...
     
 1  2 Next >>