Skip to main content
main-content

Über dieses Buch

This book constitutes the proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science held in Pec pod Sněžkou, Czech Republic, during January 24-29, 2015. The book features 8 invited talks and 42 regular papers which were carefully reviewed and selected from 101 submissions. The papers are organized in topical sections named: foundations of computer science; software and Web engineering; data, information, and knowledge engineering; and cryptography, security, and verification.

Inhaltsverzeichnis

Frontmatter

Invited Talks

Keynote Talk

What is Computation: An Epistemic Approach

Traditionally, computations are seen as processes that transform information. Definitions of computation subsequently concentrate on a description of the mechanisms that lead to such processes. The bottleneck of this approach is twofold. First, it leads to a definition of computation that is too broad and that precludes a separation of entities that, according to prevailing opinions, do perform computation from those which don’t. Secondly, it also leads to a ‘machine-dependent’ notion of computation, complicating the identification of computational processes. We present an alternative view of computation, viz. that of a knowledge generating process. From this viewpoint, computations create knowledge within the framework of ‘more or less’ formalized epistemic theories. This new perception of computation allows to concentrate upon the meaning of computations – what they do for their designers or users. It also enables one to see the existing development of computers and information technologies in a completely new perspective. It permits the extrapolation of the future of computing towards knowledge generation and accumulation, and the creative exploitation thereof in all areas of life and science. The flux of our ideas on computation bring challenging new problems to the respective research, with wide connotations in the field of artificial intelligence, in cognitive sciences, and in philosophy, epistemology and methodology of science.

Jiří Wiedermann, Jan van Leeuwen

Foundations of Computer Science

Progress (and Lack Thereof) for Graph Coloring Approximation Problems

We examine the known approximation algorithms for the classic graph coloring problem in general graphs, with the aim to extract and restate the core ideas. We also explore a recent edge-weighted generalization motivated by the modeling of interference in wireless networks. Besides examining the current state-of-the-art and the key open questions, we indicate how results for the classical coloring problem can be transferred to the approximation of general edge-weighted graphs.

Magnús M. Halldórsson

Recent Results in Scalable Multi-Party Computation

Secure multi-party computation (MPC) allows multiple parties to compute a known function over inputs held by each party, without any party having to reveal its private input. Unfortunately, traditional MPC algorithms do not scale well to large numbers of parties. In this paper, we describe several recent MPC algorithms that are designed to handle large networks. All of these algorithms rely on recent techniques from the Byzantine agreement literature on forming and using

quorums

. Informally, a quorum is a small set of parties, most of which are trustworthy. We describe the advantages and disadvantages of these scalable algorithms, and we propose new ideas for improving practicality of current techniques. Finally, we conduct simulations to measure bandwidth cost for several current MPC algorithms.

Jared Saia, Mahdi Zamani

Online Bipartite Matching in Offline Time (Abstract)

I will present our (with Bartłomiej Bosek, Dariusz Leniowski and Anna Zych) recent results on the problem of maintaining maximum size matchings in incremental bipartite graphs (FOCS’14). In this problem a bipartite graph

G

between

n

clients and

n

servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation.

As for the number of changes, we propose a greedy algorithm that chooses an augmenting path

π

that minimizes the maximum number of times each server in

π

was used by augmenting paths so far. We show that in this algorithm each server has its client reassigned

$O(\sqrt{n})$

times. This gives an

O

(

n

3/2

) bound on the total number of changes, what gives a progres towards the main open question risen by Chaudhuri

et al.

(INFOCOM’09) who asked to prove

O

(

n

log

n

) upper bound. Next, we argue that the same bound holds in the decremental case. Moreover, we show incremental and decremental algorithms that maintain (1 − 

ε

)-approximate matching with total of

O

(

ε

− 1

n

) reallocations, for any

ε

 > 0.

Finally, we address the question of how to efficiently compute paths given by this greedy algorithm. We show that by introducing proper amortization we can obtain an incremental algorithm that maintains the maximum size matching in total

$O(\sqrt{n}m)$

time. This matches the running time of one of the fastest static maximum matching algorithms that was given by Hopcroft and Karp (SIAM J. Comput ’73). We extend our result to decremental case where we give the same total bound on the running time. Additionally, we show

O

(

ε

− 1

m

) time incremental and decremental algorithms that maintain (1 − 

ε

)-approximate matching for any

ε

 > 0. Observe that this bound matches the running time of the fastest approximate static solution as well.

Piotr Sankowski

Software and Web Engineering

Quo Vadis Explicit-State Model Checking

Model checking has always been the flag ship in the fleet of automated formal verification techniques. It has been in the center of interest of formal verification research community for more than 25 years. Focusing primarily on the well-known state space explosion problem, a decent amount of techniques and methods have been discovered and applied to push further the frontier of systems verifiable with a model checker. Still, the technique as such has not yet been matured enough to become a common part of a software development process, and its penetration into the software industry is actually much slower than it was expected. In this paper we take a closer look at the so called

explicit-state model checking

, we briefly recapitulate recent research achievements in the field, and report on practical experience obtained from using our explicit state model checker

DIVINE

. Our goal is to help the reader understand what is the current position of explicit-state model checking in general practice and what are the strengths and weaknesses of the explicit-state approach after almost three decades of research. Finally, we suggest some research directions to pursue that could shed some light on the future of this formal verification technique.

Jiří Barnat

The Dos and Dont’s of Crowdsourcing Software Development

In 1957, the eminent computer scientist, Edsger W. Dijkstra, sought to record his profession as “Computer Programmer” on his marriage certificate. The Dutch authorities, although probably more progressive than most, refused on the grounds that there was no such profession. Ironically, just a decade later, the term “software crisis” had been coined, as delegates at a NATO Conference in Garmisch [1] reported a common set of problems, namely that software took too long to develop, cost too much to develop, and the software which was eventually delivered did not meet user expectations. Despite the advances in technology over the past 50 years, this remains problematic, as evidenced by the following quote from the US President’s Council of Advisors on Science & Technology (PCAST) in 2012.

Brian Fitzgerald, Klaas-Jan Stol

Data, Information and Knowledge Engineering

Adaptively Approximate Techniques in Distributed Architectures

The wealth of information generated by users interacting with the network and its applications is often under-utilized due to complications in accessing heterogeneous and dynamic data and in retrieving relevant information from sources having possibly unknown formats and structures. Processing complex requests on such information sources is, thus, costly, though not guaranteeing user satisfaction. In such environments, requests are often relaxed and query processing is forced to be adaptive and approximate, either to cope with limited processing resources (QoS-oriented techniques), possibly at the price of sacrificing result quality, or to cope with limited data knowledge and data heterogeneity (QoD-oriented techniques), with the aim of improving the quality of results. While both kinds of approximation techniques have been proposed, most adaptive solutions are QoS-oriented. Additionally, techniques which apply a QoD-oriented approximation in a QoD-oriented adaptive way (called ASAP - Approximate Search with Adaptive Processing - techniques), though demonstrated potentially useful in getting the right compromise between precise and approximate computations, have been largely neglected. In this paper, we first motivate the problem and provide a taxonomy for classifying approximate and adaptive techniques according to the dimensions pointed out above. Then, we show, through some concrete examples, the benefits of using ASAP techniques in two different contexts.

Barbara Catania, Giovanna Guerrini

Back to the Future – Should SQL Surrender to SPARQL?

In this paper, we will take a closer look at the essential differences between two of the most prominent database query languages today, SPARQL and SQL, and at their underlying data models, RDF resp. the relational model (RM). There is an enormous “hype” around SPARQL/RDF at the moment claiming all kinds of advantages of these “newcomers” over the long-established SQL/RM setting. We discover that many of these claims are not justified, at least not as far as data representation and querying is concerned. Our conclusion will be that SQL/RM are well able to serve the same purpose as SPARQL/RDF if treated fairly, and if presenting itself properly. We omit all aspects of navigation over distributed or federated data resources, though, as SQL isn’t (yet) made for this task.

Rainer Manthey

Regular Papers

Foundations of Computer Science

Balancing Energy Consumption for the Establishment of Multi-interface Networks

In heterogeneous networks, devices can communicate by means of multiple interfaces. By choosing which interfaces to activate (switch-on) at each device, several connections might be established. A connection is established when the devices at its endpoints share at least one active interface. Interfaces are associated with a cost defining the percentage of energy consumed to switch-on the corresponding interface.

In this paper, we consider the case where each device is limited to activate at most a fixed number

p

of its available interfaces in order to accomplish the required task. In particular, we consider the so-called Coverage problem. Given a network

G

 = (

V

,

E

), nodes

V

represent devices, edges

E

represent connections that can be established. The aim is to activate at most

p

interfaces at each node in order to establish all the connections defined by

E

. Parameter

p

implies a sort of balanced consumption among devices so that none of them suffers - in terms of consumed energy - for being exploited in the network more than others.

We provide an

$\mathcal{NP}$

-completeness proof for the feasibility of the problem even considering the basic case of

p

 = 2 and unitary costs for all the interfaces. Then we provide optimal algorithms that solve the problem in polynomial time for different graph topologies and general costs associated to the interfaces.

Alessandro Aloisio, Alfredo Navarra

The Maximum k-Differential Coloring Problem

Given an

n

-vertex graph

G

and two positive integers

d

,

k

 ∈ ℕ, the (

d

,

kn

)-differential coloring problem asks for a coloring of the vertices of

G

(if one exists) with distinct numbers from 1 to

kn

(treated as

colors

), such that the minimum difference between the two colors of any adjacent vertices is at least

d

. While it was known that the problem of determining whether a general graph is (2,

n

)-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit (2,

n

)-differential colorings. For practical reasons, we also consider color ranges larger than

n

, i.e.,

k

 > 1. We show that it is NP-complete to determine whether a graph admits a (3,2

n

)-differential coloring. The same negative result holds for the (

$\lfloor2n/3\rfloor,2n$

)-differential coloring problem, even in the case where the input graph is planar.

Michael A. Bekos, Michael Kaufmann, Stephen Kobourov, Sankar Veeramoni

Exact Algorithms for 2-Clustering with Size Constraints in the Euclidean Plane

We study the problem of determining an optimal bipartition {

A

,

B

} of a set

X

of

n

points in ℝ

2

that minimizes the sum of the sample variances of

A

and

B

, under the size constraints |

A

| = 

k

and |

B

| = 

n

 − 

k

. We present two algorithms for such a problem. The first one computes the solution in

$O(n\sqrt[3]{k}\log^2 n)$

time by using known results on convex-hulls and

k

-sets. The second algorithm, for an input

X

 ⊂ ℝ

2

of size

n

, solves the problem for all

$k=1,2,\ldots,\lfloor n/2\rfloor$

and works in

O

(

n

2

log

n

) time.

Alberto Bertoni, Massimiliano Goldwurm, Jianyi Lin

Local Routing in Convex Subdivisions

In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required Θ(log

n

) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and the first local geometric memoryless routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions) when the algorithm has knowledge of the incoming port (the preceding node on the route).

Prosenjit Bose, Stephane Durocher, Debajyoti Mondal, Maxime Peabody, Matthew Skala, Mohammad Abdul Wahid

Nondeterministic Modal Interfaces

Interface theories are employed in the component-based design of concurrent systems. They often emerge as combinations of Interface Automata (IA) and Modal Transition Systems (MTS), e.g., Nyman et al.’s IOMTS, Bauer et al.’s MIO, Raclet et al.’s MI or our MIA. In this paper, we generalise MI to

nondeterministic

interfaces, for which we resolve the longstanding conflict between unspecified inputs being allowed in IA but forbidden in MTS. With this solution we achieve, in contrast to related work, an

associative

parallel composition, a

compositional

preorder, a conjunction on interfaces with

dissimilar alphabets

supporting perspective-based specifications, and a quotienting operator for decomposing

nondeterministic

specifications in a single theory.

Ferenc Bujtor, Sascha Fendrich, Gerald Lüttgen, Walter Vogler

Group Search on the Line

In this paper we consider the

group search problem

, or

evacu- ation problem

, in which

k

mobile entities (

${\cal M}{\cal E}$

s) located on the line perform search for a specific destination. The

${\cal M}{\cal E}$

s are initially placed at the same origin on the line

L

and the target is located at an unknown distance

d

, either to the left or to the right from the origin. All

${\cal M}{\cal E}$

s must

simultaneously

occupy the destination, and the goal is to minimize the time necessary for this to happen. The problem with

k

 = 1 is known as the

cow-path

problem, and the time required for this problem is known to be 9

d

 − 

o

(

d

) in the worst case (when the cow moves at unit speed); it is also known that this is the case for

k

 ≥ 1 unit-speed

${\cal M}{\cal E}$

s. In this paper we present a clear argument for this claim by showing a rather counter-intuitive result. Namely, independent of the number of

${\cal M}{\cal E}$

s, group search cannot be performed faster than in time 9

d

 − 

o

(

d

). We also examine the case of

k

 = 2

${\cal M}{\cal E}$

s with different speeds, showing a surprising result that the bound of 9

d

can be achieved when one

${\cal M}{\cal E}$

has unit speed, and the other

${\cal M}{\cal E}$

moves with speed at least 1/3.

Marek Chrobak, Leszek Gąsieniec, Thomas Gorry, Russell Martin

Online Makespan Scheduling with Sublinear Advice

We study online makespan scheduling with a fixed number of parallel machines. Jobs arrive in an online fashion in consecutive time steps, and must be scheduled both immediately and definitely. In contrast to the number of machines, the number of jobs is not known in advance. This paper focuses on the

advice complexity

of the problem. Basically, we ask how much additional information may help us to obtain solutions of high quality. Our main result is the construction of a (1 + 

ε

)-competitive online algorithm with advice that reads a constant number of advice bits, for any

ε

 > 0; here, “constant” means with respect to the input size, but our bound does depend on the number of machines and

ε

. This result is particularly interesting since it shows some very significant threshold behavior; it is known that, to be a little better, namely optimal, a linear number of advice bits is necessary. We also show that the

advice

can be derived from the input in polynomial time (with respect to the input size).

Jérôme Dohrau

Deterministic Rendezvous in Restricted Graphs

In this paper we consider the problem of synchronous rendezvous in which two anonymous mobile entities (robots)

A

and

B

are expected to meet at the same time and point in a graph

G

 = (

V

,

E

). Most of the work devoted to rendezvous in graphs assumes that robots have access to the same sets of nodes and edges, where the topology of connections may be initially known or unknown. In our work we assume the movement of robots is restricted by the topological properties of the graph space coupled with the intrinsic characteristics of robots preventing them from visiting certain edges in

E

.

We consider three rendezvous models reflecting on restricted maneuverability of robots

A

and

B

. In

Edge Monotonic Model

each robot

X

 ∈ {

A

,

B

} has weight

w

X

and each edge in

E

has a weight restriction. Consequently, a robot

X

is only allowed to traverse edges with weight restrictions greater that

w

X

. In the remaining two models graph

G

is unweighted and the restrictions refer to more arbitrary subsets of traversable nodes and edges. In particular, in

Node Inclusive Model

the set of nodes

V

X

available to robot

X

, for

X

 ∈ {

A

,

B

} satisfies the condition

V

A

 ⊆ 

V

B

or vice versa, and in

Blind Rendezvous Model

the relation between

V

A

and

V

B

is arbitrary. In each model we design and analyze efficient rendezvous algorithms. We conclude with a short discussion on the asynchronous case and related open problems.

Ashley Farrugia, Leszek Gąsieniec, Łukasz Kuszner, Eduardo Pacheco

Fastest, Average and Quantile Schedule

We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the ave- rage schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, ge- nerating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.

Armin Fügenschuh, Konstanty Junosza-Szaniawski, Torsten Klug, Sławomir Kwasiborski, Thomas Schlechte

Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP

Due to the remarkable power of modern SAT solvers, one can efficiently solve NP-complete problems in many practical settings by encoding them into SAT. However, many important problems in various areas of computer science lie beyond NP, and thus we cannot hope for polynomial-time encodings into SAT. Recent research proposed the use of fixed-parameter tractable (fpt) reductions to provide efficient SAT encodings for these harder problems. The parameterized complexity classes ∃ 

k

 ∀ 

*

and ∀ 

k

 ∃ 

*

provide strong theoretical evidence that certain parameterized problems are not fpt-reducible to SAT. Originally, these complexity classes were defined via weighted satisfiability problems for quantified Boolean formulas, extending the general idea for the canonical problems for the Weft Hierarchy.

In this paper, we provide alternative characterizations of ∃ 

k

 ∀ 

*

and ∀ 

k

 ∃ 

*

in terms of first-order logic model checking problems and problems involving alternating Turing machines with appropriate time bounds and bounds on the number of alternations. We also identify parameterized Halting Problems for alternating Turing machines that are complete for these classes.

The alternative characterizations provide evidence for the robustness of the new complexity classes and extend the toolbox for establishing membership results. As an illustration, we consider various parameterizations of the 3-coloring extension problem.

Ronald de Haan, Stefan Szeider

Maximally Permissive Controlled System Synthesis for Modal Logic

We propose a new method for controlled system synthesis on non-deterministic automata, which includes the synthesis for deadlock- freeness, as well as invariant and reachability expressions. Our technique restricts the behavior of a Kripke-structure with labeled transitions, representing the uncontrolled system, such that it adheres to a given requirement specification in an expressive modal logic, while all non-invalidating behavior is retained. This induces maximal permissiveness in the context of supervisory control. Research presented in this paper allows a system model to be constrained according to a broad set of liveness, safety and fairness specifications of desired behavior, and embraces most concepts from Ramadge-Wonham supervisory control, including controllability and marker-state reachability. The synthesis construction is formally verified using the Coq proof assistant.

Alan C. van Hulst, Michel A. Reniers, Wan J. Fokkink

Approximation Hardness of the Cross-Species Conserved Active Modules Detection Problem

Biological network comparison is an essential but algorithmically challenging approach for the analysis of underlying data. A typical example is looking for certain subgraphs in a given network, such as subgraphs that maximize some function of their nodes’ weights. However, the corresponding

maximum-weight connected subgraph

(

mwcs

) problem is known to be hard to approximate. In this contribution, we consider the problem of the simultaneous discovery of maximum weight subgraphs in two networks, whose nodes are matched by a mapping: the

maximum-weight cross-connected subgraphs

(

mwccs

) problem. We provide inapproximability results for this problem. These results indicate that the complexity of the problem is conditioned both by the nature of the mapping function and by the topologies of the two networks. In particular, we show that the problem is inapproximable even when the mapping is an injective function and the input graphs are two binary trees. We also prove that it remains hard to approximate when the mapping is a bijective function and the input graphs are a graph and a binary tree. We further analyze a variant of the

mwcs

problem where the networks’ nodes are assigned both a weight and a contribution value, that we call

maximum-weight ratio-bounded connected subgraph

(

mwrbcs

). We provide a polynomial time algorithm for bounded-degree trees and an efficient dynamic programming solution for cycles. These algorithms allow us to derive a polynomial solution for

mwccs

applicable when (

i

)

mwrbcs

is polynomially solvable for one of the graphs and (

ii

) the set of connected induced subgraphs of the other graph is polynomially enumerable.

Thomas Hume, Hayssam Soueidan, Macha Nikolski, Guillaume Blin

Finding Highly Connected Subgraphs

A popular way of formalizing clusters in networks are

highly connected

subgraphs, that is, subgraphs of

k

vertices that have edge connectivity larger than

k

/2 (equivalently, minimum degree larger than

k

/2). We examine the computational complexity of finding highly connected subgraphs. We first observe that this problem is NP-hard. Thus, we explore possible parameterizations, such as the solution size, number of vertices in the input, the size of a vertex cover in the input, and the number of edges outgoing from the solution (edge isolation), and expose their influence on the complexity of this problem. For some parameters, we find strong intractability results; among the parameters yielding tractability, the edge isolation seems to provide the best trade-off between running time bounds and a small parameter value in relevant instances.

Falk Hüffner, Christian Komusiewicz, Manuel Sorge

Fixing Improper Colorings of Graphs

In this paper we consider a variation of a recoloring problem, called the

r

-Color-Fixing. Let us have some non-proper

r

-coloring

ϕ

of a graph

G

. We investigate the problem of finding a proper

r

-coloring of

G

, which is “the most similar” to

ϕ

, i.e. the number

k

of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any

r

 ≥ 3, but is Fixed Parameter Tractable (FPT), when parametrized by the number of allowed transformations

k

. We provide an

$\mathcal{O}^*(2^n)$

algorithm for the problem (for any fixed

r

) and a linear algorithm for graphs with bounded treewidth. Finally, we investigate the

fixing number

of a graph

G

. It is the maximum possible distance (in the number of transformations) between some non-proper coloring of

G

and a proper one.

Konstanty Junosza-Szaniawski, Mathieu Liedloff, Paweł Rzążewski

Efficient Online Strategies for Renting Servers in the Cloud

When scheduling jobs for systems in the cloud, we often deal with jobs that arrive and depart in an online manner. Each job should be assigned to a server upon arrival. Jobs are annotated with sizes which define the amount of resources that they need. Servers have uniform capacity and, at all times, the total size of jobs assigned to a server should not exceed this capacity. This setting is closely related to the classic bin packing problem. The difference is that, in bin packing, the objective is to minimize the total number of used servers. In the cloud systems, however, the cost for each server is proportional to the length of the time interval it is rented for, and the goal is to minimize the cost involved in renting all used servers. Recently, certain bin packing strategies were considered for renting servers in the cloud [Li et al. SPAA’14]. There, it is proved that all Any-Fit strategies have a competitive ratio of at least

μ

, where

μ

is the max/min interval length ratio of jobs. It is also proved that First Fit has a competitive ratio of 2

μ

 + 13, while Best Fit is not competitive at all. We observe that the lower bound of

μ

extends to all online algorithms. We also prove that, surprisingly, Next Fit algorithm has a competitive ratio of at most 2

μ

 + 1. We also show that a variant of Next Fit achieves a competitive ratio of

K

× max {1,

μ

/(

K

 − 1)} + 1, where

K

is a parameter of the algorithm. In particular, if the value of

μ

is known, the algorithm has a competitive ratio of

μ

 + 2; this improves upon the existing upper bound of

μ

 + 8. Finally, we introduce a simple algorithm called Move To Front (M

tf

) which has a competitive ratio of at most 6

μ

 + 8. We experimentally study the average-case performance of different algorithms and observe that the typical behaviour of M

tf

is better than other algorithms.

Shahin Kamali, Alejandro López-Ortiz

Pal k is Linear Recognizable Online

Given a language

L

that is online recognizable in linear time and space, we construct a linear time and space online recognition algorithm for the language

L

·Pal, where Pal is the language of all nonempty palindromes. Hence for every fixed positive

k

, Pal

k

is online recognizable in linear time and space. Thus we solve an open problem posed by Galil and Seiferas in 1978.

Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur

Two Grammatical Equivalents of Flip-Pushdown Automata

Flip-pushdown automata, introduced by Sarkar [7], are pushdown automata with an additional ability to reverse the contents of their pushdown, and with the most interesting setting arising when the number of such flips is limited by a constant. Two characterizations of flip-pushdown automata (with a limited number of flips) in terms of grammars are presented in this paper. First, the model is characterized by context-free grammars with an extra ability to generate reversals, which are called

reversal-generating context-free grammars

(RGCFG). Next, a model of parallel word production called

parallel interleaving grammar system

(PIGS) is introduced, for which the equivalence with flip-pushdown automata is proved, linking flip-pushdown automata to parallelism. The characterization in terms of PIGS is used to prove that flip-pushdown automata (with a limited number of flips) are weaker than ET0L systems, which solves an open problem of Holzer and Kutrib [2].

Peter Kostolányi

On the Hierarchy Classes of Finite Ultrametric Automata

This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any

k

-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite

k

-head automata is a proper subclass of the class of languages recognized by (

k

 + 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines and ultrametric multi-register machines to assist in proving the results.

Rihards Krišlauks, Kaspars Balodis

Nash-Williams-type and Chvátal-type Conditions in One-Conflict Graphs

Nash-Williams and Chvátal conditions (1969 and 1972) are well known and classical sufficient conditions for a graph to contain a Hamiltonian cycle. In this paper, we add constraints, called

conflicts

. A conflict is a pair of edges of the graph that cannot be both in a same Hamiltonian path or cycle. Given a graph

G

and a set of conflicts, we try to determine whether

G

contains such a Hamiltonian path or cycle without conflict. We focus in this paper on graphs in which each vertex is part of at most one conflict, called

one-conflict graphs

. We propose Nash-Williams-type and Chvátal-type results in this context.

Christian Laforest, Benjamin Momège

Optimal State Reductions of Automata with Partially Specified Behaviors

Nondeterministic finite automata with

don’t care

states, [4] namely states which neither accept nor reject, are considered. A cha- racterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. Finally, it is proved that the problem of minimizing nondeterministic and deterministic

don’t care

automata is NP-complete.

Nelma Moreira, Giovanni Pighizzini, Rogério Reis

Quantum Pushdown Automata with a Garbage Tape

Several kinds of quantum pushdown automaton models have been proposed, and their computational power is investigated intensively. However, for some quantum pushdown automaton models, it is not known whether quantum models are at least as powerful as classical counterparts or not. This is due to the reversibility restriction. In this paper, we introduce a new quantum pushdown automaton model that has a garbage tape. This model can overcome the reversibility restriction by exploiting the garbage tape to store popped symbols. We show that the proposed model can simulate any quantum pushdown automaton with a classical stack as well as any probabilistic pushdown automaton. We also show that our model can solve a certain promise problem exactly while deterministic pushdown automata cannot. These results imply that our model is strictly more powerful than classical counterparts in the setting of exact, one-sided error and non-deterministic computation.

Masaki Nakanishi

Towards a Characterization of Leaf Powers by Clique Arrangements

In this paper, we use the new notion of clique arrangements to suggest that leaf powers are a natural special case of strongly chordal graphs. The clique arrangement

${{\cal A}}(G)$

of a chordal graph

G

is a directed graph that represents the intersections between maximal cliques of

G

by nodes and the mutual inclusion of these vertex subsets by arcs. Recently, strongly chordal graphs have been characterized as the graphs that have a clique arrangement without bad

k

-cycles for

k

 ≥ 3.

The class

${{\cal L}}_k$

of

k

-leaf powers consists of graphs

G

 = (

V

,

E

) that have a

k

-leaf root, that is, a tree

T

with leaf set

V

, where

xy

 ∈ 

E

if and only if the

T

-distance between

x

and

y

is at most

k

. Structure and linear time recognition algorithms have been found for 2-, 3-, 4-, and, to some extent, 5-leaf powers, and it is known that the union of all

k

-leaf powers, that is, the graph class

${{\cal L}} = \bigcup_{k=2}^\infty {{\cal L}}_k$

, forms a proper subclass of strongly chordal graphs. Despite that, no essential progress has been made lately.

In this paper, we characterize the subclass of strongly chordal graphs that have a clique arrangement without certain bad 2-cycles and show that

${{\cal L}}$

is contained in that class.

Ragnar Nevries, Christian Rosenke

Filling Logarithmic Gaps in Distributed Complexity for Global Problems

Communication complexity theory is a powerful tool to show time complexity lower bounds of distributed algorithms for global problems such as minimum spanning tree (MST) and shortest path. While it often leads to nearly-tight lower bounds for many problems, polylogarithmic complexity gaps still lie between the currently best upper and lower bounds. In this paper, we propose a new approach for filling the gaps. Using this approach, we achieve tighter deterministic lower bounds for MST and shortest paths. Specifically, for those problems, we show the deterministic

$\Omega(\sqrt{n})$

-round lower bound for graphs of

O

(

n

ε

) hop-count diameter, and the deterministic

$\Omega(\sqrt{n/\log n})$

lower bound for graphs of

O

(log

n

) hop-count diameter. The main idea of our approach is to utilize the two-party communication complexity lower bound for a function we call

permutation identity

, which is newly introduced in this paper.

Hiroaki Ookawa, Taisuke Izumi

On Visibly Pushdown Trace Languages

We present a characterization of the class of (linearizations of) visibly pushdown trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size one that use an external pushdown store for computing the global successor relation.

Friedrich Otto

Dominating an s-t-Cut in a Network

We study an optimization problem with applications in design and analysis of resilient communication networks: given two vertices

s

,

t

in a graph

G

 = (

V

,

E

), find a vertex set

X

 ⊂ 

V

of minimum cardinality, such that

X

and its neighborhood constitute an

s

-

t

vertex separator. Although the problem naturally combines notions of graph connectivity and domination, its computational properties significantly differ from these relatives.

In particular, we show that on general graphs the problem cannot be approximated to within a factor of

$2^{\log^{1-\delta}{n}}$

, with

δ

 = 1 / loglog

c

n

and arbitrary

$c<\frac{1}{2}$

(if P ≠ NP). This inapproximability result even applies if the subgraph induced by a solution set has the additional constraint of being connected. Furthermore, we give a

$2\sqrt{n}$

-approximation algorithm and study the problem on graphs with bounded node degree. With Δ being the maximum degree of nodes

V

 ∖ {

s

,

t

}, we identify a (Δ + 1) approximation algorithm.

Ralf Rothenberger, Sascha Grau, Michael Rossberg

Lower Bounds for Linear Decision Trees with Bounded Weights

In this paper, we consider a linear decision tree such that a linear threshold function at each internal node has a bounded weight: the sum of the absolute values of its integer weights is at most

w

. We prove that if a Boolean function

f

is computable by such a linear decision tree of size (i.e., the number of leaves)

s

and rank

r

, then

f

is also computable by a depth-2 threshold circuit containing at most

s

(2

w

 + 1)

r

threshold gates with weight at most (2

w

 + 1)

r

 + 1

in the bottom level. Combining a known lower bound on the size of depth-2 threshold circuits, we obtain a 2

Ω(

n

/log

w

)

lower bound on the size of linear decision trees computing the Inner-Product function modulo 2, which improves on the previous bound

$2^{\sqrt{n}}$

if

$w=2^{o(\sqrt{n})}$

.

Kei Uchizawa, Eiji Takimoto

Software and Web Engineering

A Model-Driven Approach to Generate External DSLs from Object-Oriented APIs

Developers in modern general-purpose programming languages create reusable code libraries by encapsulating them in Applications Programming Interfaces (APIs). Domain-specific languages (DSLs) can be developed as an alternative method for code abstraction and distribution, sometimes preferable to APIs because of their expressivity and tailored development environment. However the cost of implementing a fully functional development environment for a DSL is generally higher. In this paper we propose

DSLit

, a prototype-tool that, given an existing API, reduces the cost of developing a corresponding DSL by analyzing the API, automatically generating a semantically equivalent DSL with its complete development environment, and allowing for user customization. To build this bridge between the API and DSL technical spaces we make use of existing Model-Driven Engineering (MDE) techniques, further promoting the vision of MDE as a unifying technical space.

Valerio Cosentino, Massimo Tisi, Javier Luis Cánovas Izquierdo

Function Based Requirements Engineering and Design –Towards Efficient and Transparent Plant Engineering

Industrial enterprises are facing an increasing complexity of their manufactured products. This goes along with a high number of fast moving and volatile customer requirements. In order to support engineering organizations in increasing their profitability, this paper presents major success factors for efficient requirements engineering and design in plant engineering. In this paper a

Function Based Requirements Engineering and Design

concept is introduced, which helps plant engineering companies achieve a more efficient requirement analysis and solution concept engineering. By splitting up the requirements engineering process in three layers –

Problem Layer

,

Abstraction Layer

and

Solution Layer

– the concept fosters an increase in reusability of requirements and features, better traceability as well as higher transparency throughout the whole process. We were able to prove the feasibility of the concept based on a case study involving the engineering of baggage handling systems.

Florian Himmler

Software Developer Activity as a Source for Identifying Hidden Source Code Dependencies

Connections between source code components are important to know in the whole software life. Traditionally, we use syntactic analysis to identify source code dependencies which may not be sufficient in cases of dynamically typed programming languages, loosely coupled components or when multiple programming languages are combined. We aim at using developer activity as a source for identifying implicit source code dependencies, to enrich or supplement explicitly stated dependencies in the source code. We propose a method for identification of implicit dependencies from activity logs in IDE, mainly of switching between source code files in addition to usually used logs of copy-pasting code fragments and commits. We experimentally evaluated our method using data of students’ activity working on five projects. We compared implicit dependencies with explicit ones including manual evaluation of their significance. Our results show that implicit dependencies based on developer activity partially reflect explicit dependencies and so may supplement them in cases of their unavailability. In addition, implicit dependencies extend existing dependency graph with new significant connections applicable in software development and maintenance.

Martin Konôpka, Mária Bieliková

Discovering Motifs in Real-World Social Networks

We built a framework for analyzing the contents of large social networks, based on the approximate counting technique developed by Gonen and Shavitt. Our toolbox was used on data from a large forum—

boards.ie

—the most prominent community website in Ireland. For the purpose of this experiment, we were granted access to 10 years of forum data. This is the first time the approximate counting technique is tested on real-world, social network data.

Lotte Romijn, Breanndán Ó. Nualláin, Leen Torenvliet

Data, Information, and Knowledge Engineering

Exploiting Semantic Activity Labels to Facilitate Consistent Specialization of Abstract Process Activities

Designing business processes from scratch is an intricate and challenging task for process modellers. For this reason, the reuse of process patterns has become an integral part of process modelling in order to deal with recurring design issues in a given domain when modelling new business processes and variants thereof. The specialization of abstract process activities remains a key issue in process pattern reuse. Depending on the intended purpose of process pattern reuse, the specialization of abstract process activities typically ranges from the substitution of abstract process activities with sub-processes to the substitution of activity labels with specialized labels. The specialization of abstract process activities through label specialization has been hardly investigated so far in the business process community. The approach presented in this paper achieves consistent specialization of abstract process activities by ensuring consistent specialization of activity labels through exploitation of semantic activity labels as introduced in previous work. Semantic activity labels encode the linguistic meaning of process activities and thereby facilitate the establishment of consistency criteria based on the implicit semantics captured by activity labels.

Andreas Bögl, Michael Karlinger, Christoph Schütz, Michael Schrefl, Gustav Pomberger

Efficient Similarity Search by Combining Indexing and Caching Strategies

A critical issue in large scale search engines is to efficiently handle sudden peaks of incoming query traffic. Research in metric spaces has addressed this problem from the point of view of creating caches that provide information to, if possible, exactly/approximately answer a query very quickly without needing to further process an index. However, one of the problems of that approach is that, if the cache is not able to provide an answer, the distances computed up to that moment are wasted, and the search must proceed through the index structure. In this paper we present an index structure that serves a twofold role: that of a cache and an index in the same structure. In this way, if we are not able to provide a quick approximate answer for the query, the distances computed up to that moment are used to query the index. We present an experimental evaluation of the performance obtained with our structure.

Nieves R. Brisaboa, Ana Cerdeira-Pena, Veronica Gil-Costa, Mauricio Marin, Oscar Pedreira

Retrieving Documents Related to Database Queries

Databases and documents are commonly isolated from each other, controlled by Database Management Systems (DBMS) and Information Retrieval Systems (IRS), respectively. However, both systems are likely to store data about the same entities, a strong argument in favor of their integration. We propose a DBMS-IRS integration approach that uses terms in DBMS queries as keywords to IRS searches, retrieving documents strongly related to the queries. The IRS keywords are built “expanding” an initial set of user-provided keywords, with top-ranked terms found in a query result: the terms are ranked based on a measure of term diffusion over the query result. Our experiments show the effectiveness of the approach in two different domains, in comparison to other DBMS-IRS integration methods, as well as to other term-ranking methods.

Vladimir Soares Catão, Marcus Costa Sampaio, Ulrich Schiel

Advantages of Dependency Parsing for Free Word Order Natural Languages

An important reason to prefer dependency parsing over classical phrased based methods, especially for languages such as Persian, with the property of being “free word order”, is that this particular property has a negative impact on the accuracy of conventional parsing methods. In Persian, some words such as adverbs can freely be moved within a sentence without affecting its correctness or meaning. In this paper, we illustrate the robustness of dependency parsing against this particular problem by training two well-known dependency parsers, namely

MST Parser

and

Malt Parser

, using a Persian dependency corpus called Dadegan. We divided the corpus into two separate parts including only projective sentences and only non-projective sentences, which are corelated with the free word order property. As our results show,

MST Parsing

is not only more tolerant than

Malt Parsing

against the free word order problem, but it is also in general a more accurate technique.

Seyed Amin Mirlohi Falavarjani, Gholamreza Ghassem-Sani

Detecting Identical Entities in the Semantic Web Data

Large amount of entities published by various sources inevitably introduces inaccuracies, mainly duplicated information. These can even be found within a single dataset. In this paper we propose a method for automatic discovery of identity relationship between two entities (also known as instance matching) in a dataset represented as a graph (e.g. in the Linked Data Cloud). Our method can be used for cleaning existing datasets from duplicates, validating of existing identity relationships between entities within a dataset, or for connecting different datasets using the

owl:sameAs

relationship. Our method is based on the analysis of sub-graphs formed by entities, their properties and existing relationships between them. It can learn a common similarity threshold for particular dataset, so it is adaptable to its different properties. We evaluated our method by conducting several experiments on data from the domains of public administration and digital libraries.

Michal Holub, Ondrej Proksa, Mária Bieliková

Conducting a Web Browsing Behaviour Study – An Educational Scenario

Web browsing behaviour is a matter of study in several fields – from web usage mining, to its applications in adaptive and personalized systems. Current web browsers allow for parallel browsing – opening multiple web pages at once and switching between them. To capture such behaviour, client-side observations are typically performed, where attracting and retaining enough participants poses a challenge. In this paper, we describe a study based on an experiment on logging the parallel browsing behaviour, both in an adaptive web-based educational system and on the open Web, while using the educational system as a tool for recruiting and motivating the participants. We focus on how various types of users (here students), including their personality information, participated in the experiment regarding churn and their observed behaviour. The paper concludes with ”lessons learned” important to consider when planning and performing similar studies.

Martin Labaj, Mária Bieliková

A Uniform Programmning Language for Implementing XML Standards

We propose X-Fun, a core language for implementing various

Xml

standards in a uniform manner. X-Fun is a higher-order functional programming language for transforming data trees based on node selection queries. It can support the

Xml

data model and

XPath

queries as a special case. We present a lean operational semantics of X-Fun based on a typed lambda calculus that enables its in-memory implementation on top of any chosen path query evaluator. We also discuss compilers from

Xslt

,

XQuery

and

XProc

into X-Fun which cover the many details of these standardized languages. As a result, we obtain in-memory implementations of all these

Xml

standards with large coverage and high efficiency in a uniform manner from

SaXON

’s

XPath

implementation.

Pavel Labath, Joachim Niehren

OntoSDM: An Approach to Improve Quality on Spatial Data Mining Algorithms

The increase in new electronic devices had generated a considerable increase in obtaining spatial data information; hence these data are becoming more and more widely used. As well as for conventional data, spatial data need to be analyzed so interesting information can be retrieved from them. Therefore, data clustering techniques can be used to extract clusters of a set of spatial data. However, current approaches do not consider the implicit semantics that exist between a region and an object’s attributes. This paper presents an approach that enhances spatial data mining process, so they can use the semantic that exists within a region. A framework was developed, OntoSDM, which enables spatial data mining algorithms to communicate with ontologies in order to enhance the algorithm’s result. The experiments demonstrated a semantically improved result, generating more interesting clusters, therefore reducing manual analysis work of an expert.

Carlos Roberto Valêncio, Diogo Lemos Guimarães, Geraldo F. D. Zafalon, Leandro A. Neves, Angelo C. Colombini

Cryptography, Security, and Verification

Attribute-Based Encryption Optimized for Cloud Computing

In this work, we aim to make attribute-based encryption (ABE) more suitable for access control to data stored in the cloud. For this purpose, we concentrate on giving to the encryptor full control over the access rights, providing feasible key management even in case of multiple independent authorities, and enabling viable user revocation, which is essential in practice. Our main result is an extension of the decentralized CP-ABE scheme of Lewko and Waters [6] with identity-based user revocation. Our revocation system is made feasible by removing the computational burden of a revocation event from the cloud service provider, at the expense of some permanent, yet acceptable overhead of the encryption and decryption algorithms run by the users. Thus, the computation overhead is distributed over a potentially large number of users, instead of putting it on a single party (e.g., a proxy server), which would easily lead to a performance bottleneck. The formal security proof of our scheme is given in the generic bilinear group and random oracle models.

Máté Horváth

Trustworthy Virtualization of the ARMv7 Memory Subsystem

In order to host a general purpose operating system, hypervisors need to virtualize the CPU memory subsystem. This entails dynami- cally changing MMU resources, in particular the page tables, to allow a hosted OS to reconfigure its own memory. In this paper we present the verification of the isolation properties of a hypervisor design that uses direct paging. This virtualization approach allows to host commodity OSs without requiring either shadow data structures or specialized hardware support. Our verification targets a system consisting of a commodity CPU for embedded devices (ARMv7), a hypervisor and an untrusted guest running Linux.The verification involves three steps: (i) Formalization of an ARMv7 CPU that includes the MMU, (ii) Formalization of a system behavior that includes the hypervisor and the untrusted guest (iii) Verification of the isolation properties. Formalization and proof are done in the HOL4 theorem prover, thus allowing to re-use the existing HOL4 ARMv7 model developed in Cambridge.

Hamed Nemati, Roberto Guanciale, Mads Dam

True Random Number Generators Secure in a Changing Environment: Improved Security Bounds

Barak, Shaltiel Tromer showed how to construct a True Random Number Generator (TRNG) which is secure against an adversary who has some limited control over the environment.

In this paper we improve the security analysis of this TRNG. Essentially, we significantly reduce the entropy loss and running time needed to obtain a required level of security and robustness.

Our approach is based on replacing the combination of union bounds and tail inequalities for ℓ-wise independent random variables in the original proof, by a more refined of the deviation of the probability that a randomly chosen item is hashed into a particular location.

Maciej Skorski

Java Loops Are Mainly Polynomial

Although there exist rare cases where exponential algorithms are used with success, practical software projects mostly consist of polynomial code. We present an automatic analysis tool which divides while-loops in a Java software project into polynomial ones and the rest. The analysis can be useful for example in software quality assurance, maintenance and design of new programming language idioms.

After running our tool on two sets of several medium size Java projects we conclude that almost 80% of while-loops are trivially polynomial.

Maciej Zielenkiewicz, Jacek Chrząszcz, Aleksy Schubert

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise