366 Works

Tree Automata, (Dis-)Equality Constraints and Term Rewriting: What's New?

Sophie Tison
Connections between Tree Automata and Term Rewriting are now well known. Whereas tree automata can be viewed as a subclass of ground rewrite systems, tree automata are successfully used as decision tools in rewriting theory. Furthermore, applications, including rewriting theory, have influenced the definition of new classes of tree automata. In this talk, we will first present a short and not exhaustive reminder of some fruitful applications of tree automata in rewriting theory. Then, we...

A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation

Ondrej Danek & Martin Maska
In this paper, we propose a modification to the Boykov-Kolmogorov maximum flow algorithm [Boykov, Kolmogorv, IEEE 2004] in order to make the algorithm preserve the topology of an initial interface. This algorithm is being widely used in computer vision and image processing fields for its efficiency and speed when dealing with problems such as graph cut based image segmentation. Using our modification we are able to incorporate a topology prior into the algorithm allowing us...

Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)

Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller & Scott M. Summers
We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of DNA and RNA material) and one operation that destroys all tiles of a particular type (e.g., an RNAse enzyme destroys all RNA tiles). We show that a single use of this destruction operation enables much more efficient construction of arbitrary shapes. In particular, an...

Using non-convex approximations for efficient analysis of timed automata

Frédéric Herbreteau, Dileep Kini, B. Srivathsan & Igor Walukiewicz
The reachability problem for timed automata asks if there exists a path from an initial state to a target state. The standard solution to this problem involves computing the zone graph of the automaton, which in principle could be infinite. In order to make the graph finite, zones are approximated using an extrapolation operator. For reasons of efficiency in current algorithms extrapolation of a zone is always a zone; and in particular it is convex....

Modeling Multiresolution 3D Scalar Fields through Regular Simplex Bisection

Kenneth Weiss & Leila De Floriani
We review modeling techniques for multiresolution three-dimensional scalar fields based on a discretization of the field domain into nested tetrahedral meshes generated through regular simplex bisection. Such meshes are described through hierarchical data structures and their representation is characterized by the modeling primitive used. The primary conceptual distinction among the different approaches proposed in the literature is whether they treat tetrahedra or clusters of tetrahedra, called diamonds, as the modeling primitive. We first focus on...

Energy-Efficient Algorithms (Invited Talk)

Susanne Albers
This presentation surveys algorithmic techniques for energy savings. We address power-down as well as dynamic speed scaling mechanisms.

The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete

Martin Mundhenk & Felix Weiß
We investigate the complexity of the model checking problem for propositional intuitionistic logic. We show that the model checking problem for intuitionistic logic with one variable is complete for logspace-uniform AC^1, and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC^1-completeness for the model checking problem and for the tautology problem.

Definable Operations On Weakly Recognizable Sets of Trees

Jacques Duparc, Alessandro Facchini & Filip Murlak
Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge...

Petri Net Reachability Graphs: Decidability Status of FO Properties

Philippe Darondeau, Stéphane Demri, Roland Meyer & Christophe Morvan
We investigate the decidability and complexity status of model-checking problems on unlabelled reachability graphs of Petri nets by considering first-order, modal and pattern-based languages without labels on transitions or atomic propositions on markings. We consider several parameters to separate decidable problems from undecidable ones. Not only are we able to provide precise borders and a systematic analysis, but we also demonstrate the robustness of our proof techniques.

Frontmatter, Table of Contents, Preface, Conference Organization

Marc Bezem
Frontmatter, Table of Contents, Preface, Conference Organization

Online Privacy: Towards Informational Self-Determination on the Internet (Dagstuhl Perspectives Workshop 11061)

Simone Fischer-Hübner, Chris Hoofnagle, Kai Rannenberg, Michael Waidner, Ioannis Krontiris & Michael Marhöfer
The Dagstuhl Perspectives Workshop "Online Privacy: Towards Informational Self-Determination on the Internet" (11061) has been held in February 6-11, 2011 at Schloss Dagstuhl. 30 participants from academia, public sector, and industry have identified the current status-of-the-art of and challenges for online privacy as well as derived recommendations for improving online privacy. Whereas the Dagstuhl Manifesto of this workshop concludes the results of the working groups and panel discussions, this article presents the talks of this...

Transfinite Update Procedures for Predicative Systems of Analysis

Federico Aschieri
We present a simple-to-state, abstract computational problem, whose solution implies the 1-consistency of various systems of predicative Analysis and offers a way of extracting witnesses from classical proofs. In order to state the problem, we formulate the concept of transfinite update procedure, which extends Avigad's notion of update procedure to the transfinite and can be seen as an axiomatization of learning as it implicitly appears in various computational interpretations of predicative Analysis. We give iterative...

Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Anna Gal & Andrew Mills
Locally decodable codes are error correcting codes with the extra property that, in order to retrieve the correct value of just one position of the input with high probability, it is sufficient to read a small number of positions of the corresponding, possibly corrupted codeword. A breakthrough result by Yekhanin showed that 3-query linear locally decodable codes may have subexponential length. The construction of Yekhanin, and the three query constructions that followed, achieve correctness only...

Node Degree based Improved Hop Count Weighted Centroid Localization Algorithm

Rico Radeke & Stefan Türk
Hop-count based weighted centroid localization is a simple and straightforward localization algorithm, which uses anchors with known positions and the hop count to these anchors to estimate the real position of nodes. Especially in sensor networks, where energy restrictions prevent more complex algorithms, this fast and simple algorithm can be used. Unfortunately the localization error of the algorithm can hinder the practical usage. In this paper we will improve the weighted centroid algorithm for hop...

Plan Recognition (Dagstuhl Seminar 11141)

Robert P. Goldman, Christopher W. Geib, Henry Kautz & Tamim Asfour
This Dagstuhl seminar brought together researchers with a wide range of interests and backgrounds related to plan and activity recognition. It featured a substantial set of longer tutorials on aspects of plan and activity recognition, and related topics and useful methods, as a way of establishing a common vocabulary and shared basis of understanding. Building on this shared understanding, individual researchers presented talks about their work in the area. There were also panel discussions which...

A Visual Approach to Analysis of Stress Tensor Fields

Andrea Kratz, Björn Meyer & Ingrid Hotz
We present a visual approach for the exploration of stress tensor fields. In contrast to common tensor visualization methods that only provide a single view to the tensor field, we pursue the idea of providing various perspectives onto the data in attribute and object space. Especially in the context of stress tensors, advanced tensor visualization methods have a young tradition. Thus, we propose a combination of visualization techniques domain experts are used to with statistical...

Real-time traffic control in railway systems

Carlo Manino
Despite the constantly increasing demand of passengers and goods transport in Europe, the share of railway traffic is decreasing. One major reason appears to be congestion, which in turn results in frequent delays and in a general unreliability of the system. This fact has triggered the study of efficient ways to manage railway traffic, both off-line and real-time, by means of optimization and mathematical programming techniques. And yet, to our knowledge, there are only a...

Improved Functional Flow and Reachability Analyses Using Indexed Linear Tree Grammars

Jonathan Kochems & C.H. Luke Ong
The collecting semantics of a program defines the strongest static property of interest. We study the analysis of the collecting semantics of higher-order functional programs, cast as left-linear term rewriting systems. The analysis generalises functional flow analysis and the reachability problem for term rewriting systems, which are both undecidable. We present an algorithm that uses indexed linear tree grammars (ILTGs) both to describe the input set and compute the set that approximates the collecting semantics....

Exploration and Curiosity in Robot Learning and Inference (Dagstuhl Seminar 11131)

Jeremy L. Wyatt, Peter Dayan, Ales Leonardis & Jan Peters
This report documents the program and the outcomes of Dagstuhl Seminar 11131 ``Exploration and Curiosity in Robot Learning and Inference''. This seminar was concerned with answering the question: how should a robot choose its actions and experiences so as to maximise the effectiveness of its learning?}. The seminar brought together workers from three fields: machine learning, robotics and computational neuroscience. The seminar gave an overview of active research, and identified open research problems. In particular...

On Isomorphism Testing of Groups with Normal Hall Subgroups

Youming Qiao, Jayalal Sarma M.N. & Bangsheng Tang
A normal Hall subgroup $N$ of a group $G$ is a normal subgroup with its order coprime with its index. Schur-Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish...

A Reputation-Based Approach to Self-Adaptive Service Selection

Jan Sudeikat, Wolfgang Renz, Ante Vilenica & Winfried Lamersdorf
Service-orientation provides concepts and tools for flexible composition and management of largescale distributed software applications. The automated run-time management of such loosely coupled software systems, however, poses still major challenges and is therefore an active research area, including the use of novel computing paradigms. In this context, the dynamic and adaptive selection of best possible service providers is an important task, which can be addressed by an appropriate middleware layer that allows considering different service...

Dagstuhl Reports, Table of Contents, Volume 1, Issue 8, 2011

Marc Herbstritt
Table of Contents, Frontmatter

Declarative Output by Ordering Text Pieces

Stefan Brass
Most real-world programs must produce output. If a deductive database is used to implement database application programs, it should be possible to specify the output declaratively. There is no generally accepted, completely satisfying solution for this. In this paper we propose to specify an output document by defining the position of text pieces (building blocks of the document). These text pieces are then ordered by their position and concatenated. This way of specifying output fits...

Theory and Applications of Graph Searching Problems (GRASTA 2011) (Dagstuhl Seminar 11071)

Fomin Fedor V., Fraigniaud Pierre, Kreutzer Stephan & Thilikos Dimitrios M.
From February 14, 2012 to February 18, 2012, the Dagstuhl Seminar 11071 ``Theory and Applications of Graph Searching Problems (GRASTA 2011)'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and open problems are put together in this paper. The first section describes the seminar...

Towards the Implementation and Evaluation of Semi-Partitioned Multi-Core Scheduling

Yi Zhang, Nan Guan & Wang Yi
Recent theoretical studies have shown that partitioning-based scheduling has better real-time performance than other scheduling paradigms like global scheduling on multi-cores. Especially, a class of partitioning-based scheduling algorithms (called semi-partitioned scheduling), which allow to split a small number of tasks among different cores, offer very high resource utilization, and appear to be a promising solution for scheduling real-time systems on multi-cores. The major concern about the semi-partitioned scheduling is that due to the task splitting,...

Registration Year

  • 2011
    366

Resource Types

  • Text
    366