While the object-orientation is the most used paradigm for developing general purpose software systems, the use of reactive systems has been growing lately. One of the differences between them is that while the first ...
详细信息
This book constitutes the refereed proceedings of the 22nd European symposium on programming, ESOP 2013, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, which took place ...
详细信息
ISBN:
(数字)9783642370366
ISBN:
(纸本)9783642370359
This book constitutes the refereed proceedings of the 22nd European symposium on programming, ESOP 2013, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, which took place in Rome, Italy, in March 2013.
The 31 papers, presented together with a full-length invited talk, were carefully reviewed and selected from 120 full submissions. The contributions have been organized according to ten topical sections on programming techniques; programming tools; separation logic; gradual typing; shared-memory concurrency and verification; process calculi; taming concurrency; model checking and verification; weak-memory concurrency and verification; and types, inference, and analysis.
We show how the subtype relation of the well-known system F≤, the second-order polymorphic λ-calculus with bounded universal type quantification and subtyping, due to Cardelli, Wegner, Bruce, Longo, Curien, Ghelli [...
详细信息
ISBN:
(纸本)9780897916929
We show how the subtype relation of the well-known system F≤, the second-order polymorphic λ-calculus with bounded universal type quantification and subtyping, due to Cardelli, Wegner, Bruce, Longo, Curien, Ghelli [6, 2, 8], proved undecidable by Pierce [12], can be interpreted in the (weak) monadic second-order theory of one (Buechi), two (Rabin), several, or infinitely many successor functions [13, 14]. These (W)SnS-interpretations show that the undecidable system F≤ possesses consistent decidable extensions, i.e., F≤ is not essentially undecidable (Tarski et. al., 1949, [17]). We demonstrate an infinite class of 'structural' decidable extensions of F≤, which combine traditional subtype inference rules with the above (W)SnS-interpretations. All these extensions, which we call systems F≤SnS, are still more powerful than F≤, but less coarse than the direct (W)SnS-interpretations: F≤ ⊂ F≤SnS ⊂ (W)SnS-interpretations The main distinctive features of the systems F≤SnS are: 1) decidability, 2) closure w.r.t. transitivity;3) structuredness, e.g., they never subtype a functional type to a universal one or vice versa, 4) they all contain the powerful rule for subtyping boundedly quantified types: Γ qq τ1 ≤ σ1 Γ, α ≤ τ1 qq σ2 ≤ τ2÷Γ qq (qqα ≤ σ1 · σ2) ≤ (qqα ≤ τ1 · τ2) (All)
The proceedings contain 51 papers. The special focus in this conference is on Mathematical Foundations of Computer Science. The topics include: Game semantics for programminglanguages;communication complexity;algorit...
ISBN:
(纸本)3540634371
The proceedings contain 51 papers. The special focus in this conference is on Mathematical Foundations of Computer Science. The topics include: Game semantics for programminglanguages;communication complexity;algorithmic techniques and results;positive applications of lattices to cryptography;a tile-based coordination view of asynchronous pi-calculus;communication complexity and sequential computation;lower bounds for a proof system with an exponential speed-up over constant-depth frege systems and over polynomial calculus;computational limitations of stochastic turing machines and arthur-merlin games with small space bounds;learning to perform knowledge-intensive inferences;resolution proofs, exponential bounds, and kolmogorov complexity;the expressiveness of datalog circuits DAC;the complexity of policy evaluation for finite-horizon partially-observable markov decision processes;a category of transition systems and its relations with orthomodular posets;accepting zeno words without time stand still;complexity theoretical results on partitioned nondeterministic binary decision diagrams;specifying computations using hyper transition systems;subtyping calculus of construction;distances between languages and reflexivity of relations;partial characterization of synchronization languages;integrating the specification techniques of graph transformation and temporal logic;on the generation of trees by hyperedge replacement;regulation by valences;simulation as a correct transformation of rewrite systems;on the dilation of interval routing;relating conflict-free stable transition and event models;the giant component threshold for random regular graphs with edge faults;a topological generalization o f propositional linear time temporal logic and complexity of finding short resolution proofs.
The CRIS language and a related temporal logic proof scheme are presented. The CRIS language, based on an extended finite-state machine model, is applied to the formal specification and implementation of logic control...
详细信息
The CRIS language and a related temporal logic proof scheme are presented. The CRIS language, based on an extended finite-state machine model, is applied to the formal specification and implementation of logic control problems and to discrete event control in general. The associated temporal logic framework allows the verification of properties of programs written in CRIS. An example, the control of a jacketed reactor, is presented, which shows the applicability of CRIS language for logic control problems and its related temporal logic framework as a tool for proving program properties.
Current software engineering practice heavily relies on the reliability of software implementation languages and underlying architectures. However, both the currently used languages, as well as the traditional archite...
详细信息
It is known that model checkers can generate test inputs as witnesses for reachability specifications (or, equivalently, as counterexamples for safety properties). While this use of model checkers for testing yields a...
详细信息
ISBN:
(纸本)9783642370366
It is known that model checkers can generate test inputs as witnesses for reachability specifications (or, equivalently, as counterexamples for safety properties). While this use of model checkers for testing yields a theoretically sound test-generation procedure, it scales poorly for computing complex test suites for large sets of test goals, because each test goal requires an expensive run of the model checker. We represent test goals as automata and exploit relations between automata in order to reuse existing reachability information for the analysis of subsequent test goals. Exploiting the sharing of sub-automata in a series of reachability queries, we achieve considerable performance improvements over the standard approach. We show the practical use of our multi-goal reachability analysis in a predicate-abstraction-based test-input generator for the test-specification language FQL.
The proceedings contain 18 papers. The special focus in this conference is on Static Analysis. The topics include: Static analysis of non-interference in expressive low-level languages;static analysis with set-closure...
ISBN:
(纸本)9783662482872
The proceedings contain 18 papers. The special focus in this conference is on Static Analysis. The topics include: Static analysis of non-interference in expressive low-level languages;static analysis with set-closure in secrecy;a binary decision tree abstract domain functor;precise data flow analysis in the presence of correlated method calls;may-happen-in-parallel analysis for asynchronous programs with inter-procedural synchronization;shape analysis for unstructured sharing;synthesizing heap manipulations via integer linear programming;effective soundness-guided reflection analysis;a type system for javascript with fixed object layout;refinement type inference via horn constraint optimization;a simple abstraction of arrays and maps by program translation;property-based polynomial invariant generation using sums-of-squares optimization;a case study on the correspondence between top-down and bottom-up analysis;parallel cost analysis of distributed systems;a forward analysis for recurrent sets and unbounded-time analysis of guarded LTI systems with inputs by abstract acceleration.
The statement S ≤ T in a λ-calculus with subtyping is traditionally interpreted by a semantic coercion function of type qqSqq → qqTqq that extracts the 'T part' of an element of S. If the subtyping relation...
详细信息
ISBN:
(纸本)9780897916929
The statement S ≤ T in a λ-calculus with subtyping is traditionally interpreted by a semantic coercion function of type qqSqq → qqTqq that extracts the 'T part' of an element of S. If the subtyping relation is restricted to covariant positions, this interpretation may be enriched to include both the implicit coercion and an overwriting function put[S,T] Ε qqSqq → qqTqq → qqSqq that updates the T part of an element of S. We give a realizability model and a sound equational theory for a second-order calculus of positive subtyping. Though weaker than familiar calculi of bounded quantification, positive subtyping retains sufficient power to model objects, encapsulation, and message passing. Moreover, inheritance may be implemented very straightforwardly in this setting, using the put functions arising from ordinary subtyping of records in place of the sophisticated systems of record extension and update often used for this purpose. The equational laws relating the behavior of coercions and put functions can be used to prove simple properties of the resulting classes in such a way that proofs for superclasses are 'inherited' by subclasses.
Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #Sat, which asks to count the...
详细信息
ISBN:
(纸本)9783030391973;9783030391966
Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #Sat, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #Sat often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.
暂无评论