432 Works

Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis

Sahar Abbaspour, Alexander Jordan & Florian Brandner
The growing complexity of modern computer architectures increasingly complicates the prediction of the run-time behavior of software. For real-time systems, where a safe estimation of the program's worst-case execution time is needed, time-predictable computer architectures promise to resolve this problem. A stack cache, for instance, allows the compiler to efficiently cache a program's stack, while static analysis of its behavior remains easy. Likewise, its implementation requires little hardware overhead. This work introduces an optimization of...

Do It Yourself networking: an interdisciplinary approach (Dagstuhl Seminar 14042)

Panayotis Antoniadis, Jörg Ott & Andrea Passarella
This report provides a summary of the organization, program, and outcome of the Dagstuhl seminar titled "Do-It-Yourself networking: an interdisciplinary perspective". We first motivate our interest in wireless networks operating outside the public Internet and the selection of the various areas of expertise. Then we describe the process of bringing together a balanced group of representatives from these fields, and the evolution of the seminar over time. An overview of the interactions during the work...

Local Algorithms for Sparse Spanning Graphs

Reut Levi, Dana Ron & Ronitt Rubinfeld
We initiate the study of the problem of designing sublinear-time (local) algorithms that, given an edge (u,v) in a connected graph G=(V,E), decide whether (u,v) belongs to a sparse spanning graph G' = (V,E') of G. Namely, G' should be connected and |E'| should be upper bounded by (1+epsilon)|V| for a given parameter epsilon > 0. To this end the algorithms may query the incidence relation of the graph G, and we seek algorithms whose...

An Overview of Open Information Extraction (Invited talk)

Pablo Gamallo
Open Information Extraction (OIE) is a recent unsupervised strategy to extract great amounts of basic propositions (verb-based triples) from massive text corpora which scales to Web-size document collections. We will introduce the main properties of this extraction method.

List Decoding Group Homomorphisms Between Supersolvable Groups

Alan Guo & Madhu Sudan
We show that the set of homomorphisms between two supersolvable groups can be locally list decoded up to the minimum distance of the code, extending the results of Dinur et al. (Proc. STOC 2008) who studied the case where the groups are abelian. Moreover, when specialized to the abelian case, our proof is more streamlined and gives a better constant in the exponent of the list size. The constant is improved from about 3.5 million...

Inverse Unfold Problem and Its Heuristic Solving

Masanori Nagashima, Tomofumi Kato, Masahiko Sakai & Naoki Nishida
Unfold/fold transformations have been widely studied in various programming paradigms and are used in program transformations, theorem proving, and so on. This paper, by using an example, show that restoring an one-step unfolding is not easy, i.e., a challenging task, since some rules used by unfolding may be lost. We formalize this problem by regarding one-step program transformation as a relation. Next we discuss some issues on a specific framework, called pure-constructor systems, which constitute...

Feature Interactions: The Next Generation (Dagstuhl Seminar 14281)

Sven Apel, Joanne M. Atlee, Luciano Baresi & Pamela Zave
The feature-interaction problem is a major threat to modularity and impairs compositional development and reasoning. A feature interaction occurs when the behavior of one feature is affected by the presence of another feature; often it cannot be deduced easily from the behaviors of the individual features involved. The feature-interaction problem became a crisis in the telecommunications industry in the late 1980s, and researchers responded with formalisms that enable automatic detection of feature interactions, architectures that...

Software Development Analytics (Dagstuhl Seminar 14261)

Harald Gall, Tim Menzies, Laurie Williams & Thomas Zimmermann
This report documents the program and the outcomes of Dagstuhl Seminar 14261 "Software Development Analytics". We briefly summarize the goals and format of the seminar, the results of the break out groups, and a draft of a manifesto for software analytics. The report also includes the abstracts of the talks presented at the seminar.

Unleashing Operational Process Mining (Dagstuhl Seminar 13481)

Rafael Accorsi, Ernesto Damiani & Wil Van Der Aalst
This report documents the program and the outcomes of Dagstuhl Seminar 13481 "Unleashing Operational Process Mining". Process mining is a young research discipline connecting computational intelligence and data mining on the one hand and process modeling and analysis on the other hand. The goal of process mining is to discover, monitor, diagnose and improve real processes by extracting knowledge from event logs readily available in today's information systems. Process mining bridges the gap between data...

An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits

Vladimir Braverman, Jonathan Katzman, Charles Seidell & Gregory Vorsanger
In this paper, we provide the first optimal algorithm for the remaining open question from the seminal paper of Alon, Matias, and Szegedy: approximating large frequency moments. We give an upper bound on the space required to find a k-th frequency moment of O(n^(1-2/k)) bits that matches, up to a constant factor, the lower bound of Woodruff et. al for constant epsilon and constant k. Our algorithm makes a single pass over the stream and...

Towards Empathic Neurofeedback for Interactive Storytelling

Marc Cavazza, Gabor Aranyi, Fred Charles, Julie Porteous, Stephen Gilroy, Ilana Klovatch, Gilan Jackont, Eyal Soreq, Nimrod Jakob Keynan, Avihay Cohen, Gal Raz & Talma Hendler
Interactive Narrative is a form of digital entertainment based on AI techniques which support narrative generation and user interaction. Despite recent progress in the field, there is still a lack of unified models integrating narrative generation, user response and interaction. This paper addresses this issue by revisiting existing Interactive Narrative paradigms, granting explicit status to users' disposition towards story characters. We introduce a novel Brain-Computer Interface (BCI) design, which attempts to capture empathy for the...

Coloring 3-colorable graphs with o(n^{1/5}) colors

Ken-Ichi Kawarabayashi & Mikkel Thorup
Recognizing 3-colorable graphs is one of the most famous NP-complete problems [Garey, Johnson, and Stockmeyer, STOC'74]. The problem of coloring 3-colorable graphs in polynomial time with as few colors as possible has been intensively studied: O(n^{1/2}) colors [Wigderson, STOC'82], O(n^{2/5}) colors [Blum, STOC'89], O(n^{3/8}) colors [Blum, FOCS'90], O(n^{1/4}) colors [Karger, Motwani and Sudan, FOCS'94], O(n^{3/14})=O(n^0.2142) colors [Blum and Karger, IPL'97], O(n^{0.2111}) colors [Arora, Chlamtac, and Charikar, STOC'06], and O(n^{0.2072}) colors [Chlamtac, FOCS'07]. Recently the authors...

Non-autoreducible Sets for NEXP

Dung T. Nguyen & Alan L. Selman
We investigate autoreducibility properties of complete sets for NEXP under different polynomial-time reductions. Specifically, we show that under some polynomial-time reductions there are complete sets for NEXP that are not autoreducible. We show that settling the question whether every complete set for NEXP under non-adaptative reduction is autoreducible under NOR-truth-table reduction either positively or negatively would lead to major results about the exponential time complexity classes.

Frontmatter, Table of Contents, Preface, Workshop Organization

Stefan Funke & Matús Mihalák
Frontmatter, Table of Contents, Preface, Workshop Organization

A survey of modelling and simulation software frameworks using Discrete Event System Specification

Romain Franceschini, Paul-Antoine Bisgambiglia, Luc Touraille, Paul Bisgambiglia & David Hill
Discrete Event System Specification is an extension of the Moore machine formalism which is used for modelling and analyzing general systems. This hierarchical and modular formalism is time event based and is able to represent any continuous, discrete or combined discrete and continuous systems. Since its introduction by B.P. Zeigler at the beginning of the eighties, most general modelling formalisms able to represent dynamic systems have been subsumed by DEVS. Meanwhile, the modelling and simulation...

Scientific Visualization (Dagstuhl Seminar 14231)

Min Chen, Charles D. Hansen, Penny Rheingans & Gerik Scheuermann
This report documents the program and the outcomes of Dagstuhl Seminar 14231 "Scientific Visualization". It includes a discussion of the motivation and overall organization, an abstract from each of the participants, and a report from each of the working groups.

Symbolic Execution as DPLL Modulo Theories

Quoc-Sang Phan
We show how Symbolic Execution can be understood as a variant of the DPLL(T ) algorithm, which is the dominant technique for the Satisfiability Modulo Theories (SMT) problem. In other words, Symbolic Executors are SMT solvers. This view enables us to use an SMT solver, with the ability of generating all models with respect to a set of Boolean atoms, to explore all symbolic paths of a program. This results in a more lightweight approach...

One Time-traveling Bit is as Good as Logarithmically Many

Ryan O'Donnell & A. C. Cem Say
We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On the other hand, Say and Yakaryilmaz showed that computation with just 1 classical CTC bit gives the power of "postselection", thereby upgrading classical randomized computation...

Engineering Graph-Based Models for Dynamic Timetable Information Systems

Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos & Christos Zaroliagis
Many efforts have been done in the last years to model public transport timetables in order to find optimal routes. The proposed models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. The array-based models have been shown to be very effective in terms of query time, while the graph-based models usually answer queries by computing shortest paths, and hence they are suitable to...

New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V Vinodchandran & Lin Forrest Yang
We obtain the following new simultaneous time-space upper bounds for the directed reachability problem. (1) A polynomial-time, O(n^{2/3} * g^{1/3})-space algorithm for directed graphs embedded on orientable surfaces of genus g. (2) A polynomial-time, O(n^{2/3})-space algorithm for all H-minor-free graphs given the tree decomposition, and (3) for K_{3,3}-free and K_5-free graphs, a polynomial-time, O(n^{1/2 + epsilon})-space algorithm, for every epsilon > 0. For the general directed reachability problem, the best known simultaneous time-space upper bound...

Process-Oriented Analysis for Medical Devices

Vasiliki Sfyrla, Josep Carmona & Pascal Henck
Medical Cyber Physical Systems are widely used in modern healthcare environments. Such systems are considered life-critical due to the severity of consequences that faults may cause. Effective methods, techniques and tools for modeling and analyzing medical critical systems are of major importance for ensuring system reliability and patient safety. This work is looking at issues concerning different types of medical industry needs including safety analysis, testing, conformance checking, performance analysis and optimization. We explore the...

A Two-Level Logic Approach to Reasoning About Typed Specification Languages

Mary Southern & Kaustuv Chaudhuri
The two-level logic approach (2LL) to reasoning about computational specifications, as implemented by the Abella theorem prover, represents derivations of a specification language as an inductive definition in a reasoning logic. This approach has traditionally been formulated with the specification and reasoning logics having the same type system, and only the formulas being translated. However, requiring identical type systems limits the approach in two important ways: (1) every change in the specification language's type system...

Multiscale Parameter Tuning of a Semantic Relatedness Algorithm

José Paulo Leal & Teresa Costa
The research presented in this paper builds on previous work that lead to the definition of a family of semantic relatedness algorithms that compute a proximity given as input a pair of concept labels. The algorithms depends on a semantic graph, provided as RDF data, and on a particular set of weights assigned to the properties of RDF statements (types of arcs in the RDF graph). The current research objective is to automatically tune the...

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)

Anna Gal, Michal Koucky, Oded Regev & Rüdiger Reischuk
This report documents the program and the outcomes of Dagstuhl Seminar 14121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in chronological order. The last section contains the abstracts of the talks.

Symbolic Solving of Extended Regular Expression Inequalities

Mathias Keil & Peter Thiemann
This paper presents a new algorithm for the containment problem for extended regular expressions that contain intersection and complement operators and that range over infinite alphabets. The algorithm solves extended regular expressions inequalities symbolically by term rewriting and thus avoids the translation to an expression-equivalent automaton. Our algorithm is based on Brzozowski's regular expression derivatives and on Antimirov's term-rewriting approach to check containment. To deal with large or infinite alphabets effectively, we generalize Brzozowski's derivative...

Registration Year

  • 2014

Resource Types

  • Text