SOFSEM 2014: Theory and Practice of Computer Science

The paper presents an update of the change of expectations and most recent new approaches regarding software processes and their improvement following the Software Process Improvement Hype Cycle introduced earlier by the author as an extension of the Gartner Hype Cycle idea. Software process assessment and improvement can itself be considered on the more abstract level as a quest for compliance with best practices. Etics and regulatory regimes explicitly addressing safety-critical systems mean however stringent compliance requirements beyond the commitment to improve process capability. New approaches are necessary for software engineers to fulfill the considerably growing expectations regarding quality under much slower changing development budget and deadline constraints. Open Services for Lifecycle Collaboration (OSLC) is the emerging initiative inspired by the web which is currently at the technology trigger stage along its hype cycle with the potential to have a determining impact on the future of Software Process Compliance Engineering.

Recent modeling experiments conducted in computational music give evidence that a number of concepts, methods and tools belonging to inverse semigroup theory can be attuned towards the concrete modeling of time-sensitive interactive systems. Further theoretical developments show that some related notions of higher-dimensional strings can be used as a unifying theme across word or tree automata theory. In this invited paper, we will provide a guided tour of this emerging theory both as an abstract theory and with a view to concrete applications.

We survey recent results from different areas, studying how introducing per-instance a-priori information affects the solvability and complexity of given tasks. We mainly focus on distributed, and online computation, where some sort of hidden information plays a crucial role: in the distributed computing, typically nodes have no or only limited information about the global state of the network; in online problems, the algorithm lacks the information about the future input. The traditional approach in both areas is to study how the properties of the problem change if some partial information is available (e.g., nodes of a distributed system have sense of direction, the online algorithm has the promise that the input requests come in some specified order etc.). Recently, attempts have been made to study this information from a quantitative point of view: there is an oracle that delivers (per-instance) best-case information of a limited size, and the relationship between the amount of the additional information, and the benefit it can provide to the algorithm, is investigated. We show cases where this relationship has a form of a trade-off, and others where one or more thresholds can be identified.

We explore the performance of the recently proposed two-view image matching algorithms using affine view synthesis – ASIFT (Morel and Yu, 2009) [14] and MODS (Mishkin, Perdoch and Matas, 2013) [10] on images of objects that do not have significant local texture and that are locally not well approximated by planes.

Experiments show that view synthesis improves matching results on images of such objects, but the number of ”useful” synthetic views is lower than for planar objects matching. The best detector for matching images of 3D objects is the Hessian-Affine in the

Sparse

configuration. The iterative MODS matcher performs comparably confirming it is a robust, generic method for two view matching that performs well for different types of scenes and a wide range of viewing conditions.

Agile methodologies have impact not only on coding, but also on requirements engineering activities. In the paper agile requirements engineering is examined from the research point of view. It is claimed that use cases are a better tool for requirements description than user stories as they allow zooming through abstraction levels, can be reused for user manual generation, and when used properly can provide quite good effort estimates. Moreover, as it follows from recent research, parts of use cases (namely event descriptions) can be generated in an automatic way. Also the approach to non-functional requirements can be different. Our experience shows that they can be elicited very fast and can be quite stable.

Graph and cartographic visualization have the common objective to provide intuitive understanding of some underlying data. We consider a problem that combines aspects of both by studying the problem of fitting planar graphs on planar maps. After providing an NP-hardness result for the general decision problem, we identify sufficient conditions so that a fit is possible on a map with rectangular regions. We generalize our techniques to non-convex rectilinear polygons, where we also address the problem of efficient distribution of the vertices inside the map regions.

In

activation network

problems we are given a directed or undirected graph

G

 = (

V

,

E

) with a family {

f

uv

: (

u

,

v

) ∈ 

E

} of monotone non-decreasing activation functions from

D

2

to {0,1}, where

D

is a constant-size subset of the non-negative real numbers, and the goal is to find activation values

x

v

for all

v

 ∈ 

V

of minimum total cost ∑ 

v

 ∈ 

V

x

v

such that the activated set of edges satisfies some connectivity requirements. We propose algorithms that optimally solve the

minimum activation cost of k node-disjoint st-paths

(

st

-MANDP) problem in

O

(

tw

((5 + 

tw

)|

D

|)

2

tw

 + 2

|

V

|

3

) time and the

minimum activation cost of node-disjoint paths

(MANDP) problem for

k

disjoint terminal pairs (

s

1

,

t

1

),…,(

s

k

,

t

k

) in

O

(

tw

((4 + 3

tw

)|

D

|)

2

tw

 + 2

|

V

|) time for graphs with treewidth bounded by

tw

.

In this work, we study the advice complexity of the online minimum Steiner tree problem (

ST

). Given a (known) graph

G

 = (

V

,

E

) endowed with a weight function on the edges, a set of

N

terminals are revealed in a step-wise manner. The algorithm maintains a sub-graph of chosen edges, and at each stage, chooses more edges from

G

to its solution such that the terminals revealed so far are connected in it. In the standard online setting this problem was studied and a tight bound of

O

(log(

N

)) on its competitive ratio is known. Here, we study the power of non-uniform advice and fully characterize it. As a first result we show that using

q

·log(|

V

|) advice bits, where 0 ≤ 

q

 ≤ 

N

 − 1, it is possible to obtain an algorithm with a competitive ratio of

O

(log(

N

/

q

). We then show a matching lower bound for all values of

q

, and thus settle the question.

In the disjoint path allocation problem, we consider a path of

L

 + 1 vertices, representing the nodes in a communication network. Requests for an unbounded-time communication between pairs of vertices arrive in an online fashion and a central authority has to decide which of these calls to admit. The constraint is that each edge in the path can serve only one call and the goal is to admit as many calls as possible.

Advice complexity is a recently introduced method for a fine-grained analysis of the hardness of online problems. We consider the advice complexity of disjoint path allocation, measured in the length

L

of the path. We show that asking for a bit of advice for every edge is necessary to be optimal and give online algorithms with advice achieving a constant competitive ratio using much less advice. Furthermore, we consider the case of using less than loglog

L

advice bits, where we prove almost matching lower and upper bounds on the competitive ratio.

In the latter case, we moreover show that randomness is as powerful as advice by designing a barely random online algorithm achieving almost the same competitive ratio.

It is increasingly difficult for customers to understand complex systems like clouds and to trust them with regard to security. As a result, numerous companies achieved a security certification according to the ISO 27001 standard. However, assembling an Information Security Management System (ISMS) according to the ISO 27001 standard is difficult, because the standard provides only sparse support for system development and documentation.

Security requirements engineering methods have been used to elicit and analyse security requirements for building software. In this paper, we propose a goal-based security requirements engineering method for creating an ISMS compliant to ISO 27001. We illustrate our method via a smart grid example.

Online Social Networks (OSNs) enjoy high popularity, but their centralized architectures lead to intransparency and mistrust in the providers who can be the single point of failure. A solution is to adapt the OSN functionality to an underlying and fully distributed peer-to-peer (P2P) substrate. Several approaches in the field of OSNs based on P2P architectures have been proposed, but they share substantial P2P weaknesses and they suffer from low availability and privacy problems. In this work, we propose a distributed OSN which combines an underlying P2P architecture with friend-based data propagation and a Proof-of-Work (PoW) concept. ProofBook provides availability of user data, stability of the underlying network architecture and privacy improvements while it does not limit simple data sharing based on social relations.

Many of software engineering tools and systems are focused to monitoring source code quality and optimizing software development. Many of them use similar source code metrics to solve different kinds of problems. This inspired us to propose an environment for platform independent code monitoring, which supports employment of multiple software development monitoring tools and sharing of information among them to reduce redundant calculations. In this paper we present design of an architecture of the environment, whose main contribution is employing (acquiring, generating and processing) information tags - descriptive metadata that indirectly refer source code artifacts, project documentations and developers activity via document models and user models. Information tags represent novel concept unifying traditional content based software metrics with recently developed activity-based metrics. We also describe prototype realization of the environment within project PerConIK (Personalized Conveying Information and Knowledge), which proves feasibility and usability of the proposed environment.

A central problem in the delivery of intensity-modulated radiation therapy (IMRT) using a multileaf collimator (MLC) relies on finding a series of leaves configurations that can be shaped with the MLC to properly deliver a given treatment. In this paper, we analyse, from an algorithmic point of view, the impact of using dual-layer MLCs and Rotating Collimators for this purpose.

In this paper we study the

Sparsest

k

-

Subgraph

problem which consists in finding a subset of

k

vertices in a graph which induces the minimum number of edges. The

Sparsest

k

-

Subgraph

problem is a natural generalization of the

Independent Set

problem, and thus is

${\mathcal NP}$

-hard (and even

W

[1]-hard) in general graphs. In this paper we investigate the parameterized complexity of both

Sparsest

k

-

Subgraph

and

Densest

k

-

Subgraph

in chordal graphs. We first provide simple proofs that

Densest

k

-

Subgraph

in chordal graphs is FPT and does not admit a polynomial kernel unless

${\mathcal NP} \subseteq co{\mathcal NP}/poly$

(both parameterized by

k

). More involved proofs will ensure the same behavior for

Sparsest

k

-

Subgraph

in the same graph class.

De Alfaro and Henzinger introduced interface automata to model and study behavioural types. These come with alternating simulation as refinement and with a specific parallel composition: if one component receives an unexpected input, this is regarded as an error and the resp. error states are removed with a special pruning operation. In this paper, we return to the foundations of interface automata and study how refinement and parallel composition should be defined best. We take as basic requirement that an implementation must be error-free, if the specification is. For three variants of error-free, we consider the coarsest precongruence for parallel composition respecting the basic requirement. We find that pruning proves to be relevant in all cases; we also point out an error in an early paper by de Alfaro and Henzinger.

Contemporary enterprise web applications deal with a large stack of different kinds of concerns involving business rules, security policies, cross-cutting configuration, etc. At the same time, increasing demands on user interface complexity make designers to consider the above concerns in the presentation. To locate a concern knowledge, we try to identify an appropriate system component with the concern definition. Unfortunately, this is not always possible, since there exist concerns cross-cutting multiple components. Thus to capture the entire knowledge we need to locate multiple components. In addition to it, often, we must restate the knowledge in the user interface because of technological incompatibility between the knowledge source and the user interface language. Such design suffers from tangled and hard to read code, due to the cross-cutting concerns and also from restated information and duplicated knowledge. This leads to a product that is hard to maintain, a small change becomes expensive, error-prone and tedious due to the necessity of manual changes in multiple locations.

This paper introduces a novel approach based on independent, description of all orthogonal concerns in information systems and their dynamic automated weaving according to the current user’s context. Such approach avoids information restatement, speeds up development and simplifies maintenance efforts due to application of automated programming and runtime weaving of all concerns, and thus distributes the knowledge through the entire system.

The clique-chromatic number of a graph

G

 = (

V

,

E

) denoted by

χ

c

(

G

) is the smallest integer

k

such that there exists a partition of the vertex set of

G

into

k

subsets with the property that no maximal clique of

G

is contained in any of the subsets. Such a partition is called a

k

-clique-colouring of

G

. Recently Marx proved that deciding whether a graph admits a

k

-clique-colouring is

$\Sigma^p_2$

-complete for every fixed

k

 ≥ 2. Our main results are an

O

*

(2

n

) time inclusion-exclusion algorithm to compute

χ

c

(

G

) exactly, and a branching algorithm to decide whether a graph of bounded clique-size admits a 2-clique-colouring which runs in time

O

*

(

λ

n

) for some

λ

 < 2.

This paper presents the

π

SOD-M method, an extension to the Service-Oriented Development Method (SOD-M) to support the development of services software by considering their functional and non-functional requirements. Specifically,

π

SOD-M proposes:

(i)

meta-models for representing non-functional requirements at different abstraction levels;

(ii)

model-to-model transformation rules, useful to semi-automatically refine Platform Independent Models into Platform Specific Models; and

(iii)

rules to transform Platform Specific Models into concrete implementations. In order to illustrate our proposal, the paper also describes how to apply the methodology to develop a proof of concept.

A variety of system design and architecture description languages, such as SysML, UML or AADL, allows the decomposition of complex system designs into communicating timed components. In this paper we consider the contract-based specification of such components. A contract is a pair formed of an assumption, which is an abstraction of the component’s environment, and a guarantee, which is an abstraction of the component’s behavior given that the environment behaves according to the assumption. Thus, a contract concentrates on a specific aspect of the component’s functionality and on a subset of its interface, which makes it relatively simpler to specify. Contracts may be used as an aid for hierarchical decomposition during design or for verification of properties of composites. This paper defines contracts for components formalized as a variant of timed input/output automata, introduces compositional results allowing to reason with contracts and shows how contracts can be used in a high-level modeling language (SysML) for specification and verification, based on an example extracted from a real-life system.

Clustering graphs based on a comparison of the number of links within clusters and the expected value of this quantity in a random graph has gained a lot of attention and popularity in the last decade. Recently, Aldecoa and Marín proposed a related, but slightly different approach leading to the quality measure

surprise

, and reported good behavior in the context of synthetic and real world benchmarks. We show that the problem of finding a clustering with optimum surprise is

$\mathcal{NP}$

-hard. Moreover, a bicriterial view on the problem permits to compute optimum solutions for small instances by solving a small number of integer linear programs, and leads to a polynomial time algorithm on trees.

This paper concerns probabilistic distributed graph algorithms to solve classical graph problems such as colouring, maximal matching or maximal independent set. We consider anonymous networks (no unique identifiers are available) where vertices communicate by single bit messages. We present a general framework, based on coverings, for proving lower bounds for the bit complexity and thus the execution time to solve these problems. In this way we obtain new proofs of some well known results and some new ones.

We study active learning of classes of recursive functions by asking value queries about the target function

f

, where

f

is from the target class. That is, the query is a natural number

x

, and the answer to the query is

f

(

x

). The complexity measure in this paper is the worst-case number of queries asked. We prove that for some classes of recursive functions

ultrametric active learning

algorithms can achieve the learning goal by asking

significantly fewer

queries than deterministic, probabilistic, and even nondeterministic active learning algorithms. This is the first ever example of a problem where ultrametric algorithms have advantages over nondeterministic algorithms.

We consider the task of transmitting a data stream in the sliding window model, where communication takes place over an

adversarial

noisy channel with noise rate up to 1. For any noise level

c

 < 1 we design an efficient encoding scheme, such that for any window in which the noise level does not exceed

c

, the receiving end decodes at least a (1 − 

c

 − 

ε

)-prefix of the window, for any small

ε

 > 0. Decoding more than a (1 − 

c

)-prefix of the window is shown to be impossible in the worst case, which makes our scheme optimal in this sense. Our scheme runs in polylogarithmic time per element in the size of the window, causes constant communication overhead, and succeeds with overwhelming probability.

To cope with the complexity of large systems, one usually makes use of hierarchical structures in their models. To detect and to remove design errors as soon as possible, these models must be analyzed in early stages of the development process. For example, UML models can be analyzed through simulation using the semantics of a foundational subset for executable UML models (fUML). However, the composite structures used to describe the hierarchy of systems in UML is not covered by fUML. In this paper, we therefore propose a complementary meta-model for fUML covering parts of UML’s composite structures, and elaborate the rules previously defined in the literature for static semantics. These rules are described in an axiomatic way using first-order logic so that a large set of tools can be used for analysis. Our preliminary evaluation provides results about the applicability of the meta-model and the soundness of the rules.

The value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? This problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely

$\sharp-acyclic$

partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a

$\sharp$

-acyclic partially observable Markov decision process

${\mathcal M}$

such that the first player has a winning strategy in the knowledge game if and only if the value of

${\mathcal M}$

is 1.

Let

${\cal B}$

be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs

$G_{\cal B}$

where each body of the collection

${\cal B}$

is represented by a vertex, and two vertices of

$G_{\cal B}$

are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

Anonymous authentication protocols aim to provide means to anonymously prove membership in a group. Moreover, the membership should not be transferable i.e. a subgroup of members should not be able to help an outsider to gain access on behalf of a group. In this note we present two attacks on a recently published protocol of this kind (ICUIMC ’11 Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication, article no. 32) and thereby we show that it failed the security targets for an anonymous authentication protocol.

The well-known

Disjoint Paths

problem takes as input a graph

G

and a set of

k

pairs of terminals in

G

, and the task is to decide whether there exists a collection of

k

pairwise vertex-disjoint paths in

G

such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by

k

due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP ⊆ coNP/poly. We prove that

Disjoint Paths

remains NP-complete on split graphs, and show that the problem admits a kernel with

O

(

k

2

) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with

O

(

k

3

) vertices. To the best of our knowledge, our kernelization results are the first non- trivial kernelization results for these problems on graph classes.

We study the 3-dimensional Strip Packing problem: Given a list of

n

boxes

b

1

,…,

b

n

of the width

w

i

 ≤ 1, depth

d

i

 ≤ 1 and an arbitrary length ℓ

i

. The objective is to pack all boxes into a strip of the width and depth 1 and infinite length, so that the packing length is minimized. The boxes may not overlap or be rotated. We present an improvement of the current best asymptotic approximation ratio of 1.692 by Bansal et al.[2] with an asymptotic 3/2 + 

ε

-approximation for any

ε

 > 0.

We propose a stronger conjecture regarding the number of distinct squares in a binary word. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is upper bounded by the length of the word. Here, we conjecture that in the case of a word of length

n

over the alphabet {

a,b

}, the number of distinct squares is upper bounded by

$\frac{2k-1}{2k+2}n$

, where

k

is the least of the number of

a

’s and the number of

b

’s. We support the conjecture by showing its validity for several classes of binary words. We also prove that the bound is tight.

Currently nearly all commercial and open source BPMS are based on BPMN as a process notation. In contrast, the paper proposes to build a BPMS based on a domain specific language (DSL) as a process notation – DSBPMS. In such a DSBPMS a specific business process support could be created by business analysts. A platform for creating such DSBPMS with feasible efforts is described. This platform contains a Configurator for easy creation of graphical editors for the chosen DSL and a simple mapping language for transforming processes in this DSL to a language directly executable by the execution engine of this platform. The engine includes also all typical execution support functions so no other tools are required.

Given two sets of strings and a similarity function on strings,

similarity joins

attempt to find all similar pairs of strings from each respective set. In this paper, we focus on similarity joins with respect to the edit distance, and propose a new metric called the bounded occurrence edit distance and a filter based on the metric. Using the filter, we can reduce the total time required to solve similarity joins because the metric can be computed faster than the edit distance by bitwise operations. We demonstrate the effectiveness of the filter through experiments.

Let

A

,

B

and

C

be

n

×

n

matrices of integer numbers. We show that there is a deterministic algorithm of quadratic time complexity (w.r.t. the number of arithmetical operations) verifying whether

AB

=

C.

For the integer matrices this result improves upon the best known result by Freivalds from 1977 that only holds for a randomized (Monte Carlo) algorithm. As a consequence, we design a quadratic time nondeterministic integer and rational matrix multiplication algorithm whose time complexity cannot be further improved. This indicates that any technique for proving a super-quadratic lower bound for deterministic matrix multiplication must exploit methods which would not work for the non-deterministic case.

In this contribution, we describe and compare two genetic systems which create trading strategies. The first system is based on the idea that the connection weight matrix of a neural network represents the genotype of an individual and can be changed by genetic algorithm. The second system uses genetic programming to derive trading strategies. As input data in our experiments, we used technical indicators of NASDAQ stocks. As output, the algorithms generate trading strategies, i.e. buy, hold, and sell signals. Our hypothesis that strategies obtained by genetic programming bring better results than buy-and-hold strategy has been proven as statistically significant. We discuss our results and compare them to our previous experiments with fuzzy technology, fractal approach, and with simple technical indicator strategy.

We consider

admissible encodings on an elliptic curve

, that is, the hash functions that map bitstrings to points of the curve. We extend the framework of admissible encodings, known from CRYPTO 2010 paper, to some class of non-deterministic mapping algorithms. Using Siguna Müller’s probabilistic square root algorithm we show a mapping that works efficiently for

any

finite field

$\mathbb{F}_q$

of characteristic greater than 3, and that is

immune to timing attacks

. Thereby we remove limitations of the mappings analyzed in the CRYPTO 2010 paper. Consequently, we remove limitations of a so called PACE Integrated Mapping protocol, which has recently been standardized by ICAO, and is used to protect contactless identity documents against unauthorized access.

As the use of intelligent agents in critical domains increases, the need for verifying their behavior becomes stronger. Reactive rules are the main reasoning formalism for intelligent agents. For this reason, we propose the use of the OTS/CafeOBJ method for the specification of reactive rules, which will permit the verification of safety properties for reactive rule-based intelligent agents.

We investigate the parameterized prefix distance between regular languages. The prefix distance between words is extended to languages in such a way that the distances of all words up to length

n

to the mutual other language are summed up. Tight upper bounds for the distance between unary as well as non-unary regular languages are derived. It is shown that there are pairs of languages having a constant, degree

k

polynomial, and exponential distance. Moreover, for every constant and every polynomial, languages over a binary alphabet are constructed that have exactly that distance. From the density and census functions of regular languages the orders of possible distances between languages are derived and are shown to be decidable.

We introduce a two-dimensional variant of the restarting automaton with window size three-by-three for processing rectangular pictures. In each rewrite step such an automaton can only replace the symbol in the middle position of its window by a symbol that is smaller with respect to a fixed ordering on the tape alphabet. When restricted to one-dimensional inputs (that is, words) the deterministic variant of these

ordered restarting automata

only accepts regular languages, while the nondeterministic one can accept some languages that are not even context-free. We then concentrate on the deterministic two-dimensional ordered restarting automaton, showing that it is quite expressive as it can simulate the deterministic sgraffito automaton, and we present some closure and non-closure properties for the class of picture languages accepted by these automata.

We consider unary finite automata employing limited nondeterminism. We show that for a unary regular language, a minimal finite tree width nondeterministic finite automaton (NFA) can always be found in Chrobak normal form. A similar property holds with respect to other measures of nondeterminism. The latter observation is used to establish relationships between classes of unary regular languages recognized by NFAs of given size where the nondeterminism is limited in various ways. Finally, we show that the branching measure of a unary NFA is always either bounded by a constant or has an exponential growth rate.

In this paper, we focus on small or medium-sized e-commerce portals. Due to high competition, users of these portals are not too loyal and e.g. refuse to register or provide any/enough explicit feedback. Furthermore, products such as tours, cars or furniture have very low average consumption rate preventing us from tracking unregistered user between two consecutive purchases. Recommending on such domains proves to be very challenging, yet interesting research task. For this task, we propose a model coupling various implicit feedbacks and object attributes in matrix factorization. We report on promising results of our initial off-line experiments on travel agency dataset. Our experiments corroborate benefits of using object attributes; however we are yet to decide about usefulness of some implicit feedback data.

Rapid development of new technologies brings with it a need for the new security solutions. Identifying, defining and implementing of security constraints is an important part of the process of modeling and developing of application/information systems and its administration.

The paper presents the issue of security constraints of information system from the point of view of Usage Role-based Access Control approach - it deals with the classification of constraints and their implementation in the process of modeling the access rules for dynamic information systems.

One of the most representative and studied Distance-Based Queries in Spatial Databases is the

K

-Closest-Pairs Query (

K

CPQ). This query involves two spatial data sets and a distance function to measure the degree of closeness, along with a given number

K

of elements of the result. The output is a set of pairs of objects (with one object element from each set), with the

K

lowest distances. In this paper, we study the problem of processing

K

CPQs between RAM-based point sets, using

Plane-Sweep

(

PS

) algorithms. We utilize two improvements that can be applied to a

PS

algorithm and propose a new algorithm that minimizes the number of distance computations, in comparison to the

classic PS

algorithm. By extensive experimentation, using real and synthetic data sets, we highlight the most efficient improvement and show that the new

PS

algorithm outperforms the

classic

one, in most cases.

Most automobile manufacturers maintain many vehicle types to keep a successful position on the market. Through the further development all vehicle types gain a diverse amount of new functionality. Additional features have to be supported by the car’s software. For time efficient accomplishment, usually the existing electronic control unit (ECU) code is extended.

In the majority of cases this evolutionary development process is accompanied by a constant decay of the software architecture. This effect known as software erosion leads to an increasing deviation from the requirements specifications. To counteract the erosion it is necessary to continuously restore the architecture in respect of the specification.

Automobile manufacturers cope with the erosion of their ECU software with varying degree of success. Successfully we applied a methodical and structured approach of architecture restoration in the specific case of the brake servo unit (BSU). Software product lines from existing BSU variants were extracted by explicit projection of the architecture variability and decomposition of the original architecture. After initial application, this approach was capable to restore the BSU architecture recurrently.

We present an optimal, linear time algorithm for the shortest unique substring problem, thus improving the algorithm by Pei et al. (ICDE 2013). Our implementation is simple and based on suffix arrays. Computational experiments show that our algorithm is much more efficient in practice, compared to that of Pei et al.

We implement various oracle mechanisms on nondeterministic pushdown automata, which naturally induce nondeterministic reducibilities among formal languages in a theory of context-free languages. In particular, we examine a notion of nondeterministic many-one CFL-reducibility and carry out ground work of formulating a coherent framework for further expositions. Another more powerful reducibility—Turing CFL-reducibility—is also discussed in comparison. The Turing CFL-reducibility, in particular, makes it possible to induce a useful hierarchy (the CFL hierarchy) built over the family CFL of context-free languages. For each level of this hierarchy, basic structural properties are proven and three alternative characterizations are presented. We also show that the CFL hierarchy enjoys an upward collapse property. The first and second levels of the hierarchy are proven to be different. We argue that the CFL hierarchy coincides with a hierarchy over CFL built by applications of many-one CFL-reductions. Our goal is to provide a solid foundation for structural-complexity analyses in automata theory.