Abstract:
In this paper, we suggest a methodology for testing robustness of Real-Time Component-Based
Systems (RTCBS). A RTCBS system is described as a collection of components where
each component is modeled as a Timed Input-Output Automaton (TIOA).
For each component, we handle two specifications : a nominal one and a degraded one.
We extract test sequences from the nominal specification and we inject automatically faults
in order to model hostile environments.
Then we present an adequate test architecture consisting of the System Under
Test (SUT) of components, and a distributed tester that consists of a set of coordinating
testers. Each tester is dedicated to test a single SUT component. A test execution
algorithm is presented. Testing the SUT is divided into two phases. In the first phase, the
tester executes the generated test sequences of each component in
isolation and records the feedback of this experimentation. The robustness is checked by
verifying if the recorded results are accepted by the degraded specification of each component.
If all components are robust according to the inserted hazards, we check the robustness of
communications between components respecting the same process described before.
Anna Bobkowska:
"A Methodology of Visual Modeling Languages Evaluation"
Abstract: In order to achieve more maturity in Visual Modelling Language (VML) engineering, effective methodologies of VML evaluation are necessary. This paper discusses methodological problems of applying psychological results for VML evaluation. Then, it presents research on a CD-VML methodology which is based on cognitive dimensions (CD). This research covers analysis of application, empirical studies of UML with original CD questionnaire, customisation of CDs for VML evalation and empirical studies of use cases with a CD-VML-UC questionnaire - a product of the CD-VML methodology for use case diagrams. Finally it presents and explains problems related to use cases which were found during the second empirical study.
Antonin Kucera and Jan Strejcek:
"Characteristic Patterns for LTL"
Abstract: We give a new characterization of those languages that are definable
in fragments of LTL where the nesting depths of X and U
modalities are bounded by given constants. This brings further results
about various LTL fragments. We also propose a generic method for
decomposing LTL formulae into an equivalent disjunction of "semantically
refined" LTL formulae, and indicate how this result can be used to
improve the functionality of existing LTL model-checkers.
Cristina Bazgan and Jérôme Monnot and Vangelis Th. Paschos and Fabrice Serrière:
"Greedy differential approximations for min set cover"
Abstract: We present in this paper differential approximation results for
set cover and weighted set cover. We first show that the differentialapproximation ratio of the natural greedy algorithm for set cover is bounded below by~$1.365/\Delta$ (asymptotically) and above by $4/(\Delta+1)$,where~$\Delta$ is the maximum set-cardinality in the set cover instance. Next, we study an approximation algorithm for weighted set cover and provide a tight lower bound of~$1/\Delta$.
Daniel Sawitzki:
"Lower Bounds on the OBDD Size of Graphs of Some Popular Functions"
Abstract: Ordered binary decision diagrams (OBDDs) are a data structure for
Boolean functions which supports many useful operations. It finds many
applications in logic design, CAD, model checking, and symbolic graph
algorithms. Nevertheless, many simple functions are known which have
only OBDDs of exponential size w.r.t. the number of Boolean variables
they are defined on. In order to investigate the limits of symbolic
graph algorithms which work on OBDD-represented graph instances, it is
useful to have simply-structured graphs whose OBDD representation has
exponential size. Therefore, we consider popular arithmetic and
storage access functions with exponential lower bounds on their OBDD
size and transfer these results to the corresponding graphs of these
functions. Concretely, lower bounds for the graphs of integer
multiplication, indirect storage access, and the hidden weighted bit
function are presented. Finally, an exemplary application of the
result for multiplication to the analysis of a symbolic all-pairs
shortest-paths algorithm is sketched.
David Safranek:
"VCD: A Visual Formalism for Specification of Heterogeneous Software Architectures"
Abstract: A visual formalism called Visual Coordination Diagrams
(VCD) for high-level design of heterogeneous systems is presented in
this paper. The language is based on a state-transition operational se-
mantics, which allows application of formal methods to software design.
Formal definition of VCD is included in the paper. Moreover, an example
of use of the language is also given.
Dominik Raub and Rainer Steinwandt and Jörn Müller-Quade:
"On the Security and Composability of the One Time Pad"
Abstract: Recent experimental results in quantum cryptography have renewed the interest in information-theoretically secure ciphers. In April 2004, in Vienna a bank transfer was secured by means of a one time pad encryption, with the key material being derived from a quantum key exchange. However, in this experiment the integrity of the transmitted message remained unprotected. This can have severe consequences, if the bank transfer form itself contains no authentication mechanism and there is a known position where the amount of money or the recipient is specified. Through flipping bits at the corresponding positions in the ciphertext, the amount of transfered money or the recipient of the money can be changed.
This concrete example illustrates the necessity for a thorough theoretical analysis of information-theoretically secure cryptographic techniques that are to be deployed in practice. In this work we show how to implement a statistically secure and composable system for message passing, that is, a channel with negligible failure rate secure against unbounded adversaries, using a one time pad based cryptosystem. We prove the security of our system in an
asynchronous adversarially-controlled network using the framework put forward by Backes, Pfitzmann, and Waidner. The composition theorem offered by this framework enables the use of our scheme as a building block of more complex protocols as needed in practical applications.
Emilio Di Giacomo, Walter Didimo, Luca Grilli, Giuseppe Liotta:
"A Topology-driven Approach to the Design of Web Meta-search Clustering Engines"
Abstract: The paradigm adopted by classical Web search engines to output
the results of a query is often inadequate. It typically consists of a ranked list of URLs, which may be very long and difficult to browse for the interested user. Recently, a lot of attention has been devoted to the design of Web meta-search clustering engines. These systems support the user by grouping the URLs returned by a search engine into distinct semantic categories, which are organized in a hierarchy; each category is properly labeled with a sentence that reflects its topics. However, even the most effective Web meta-search engines usually end-up by presenting many ``meaningful'' categories together with a few ``inexpressive'' categories on some specific queries.
In this paper we describe a novel topology-driven approach to the design of a Web meta-search clustering engine. By this approach the set of URLs is modeled as a suitable graph and the hierarchy of categories is obtained by variants of classical graph-clustering algorithms. The topology-driven approach turns out to be comparable with traditional text-based strategies for the definition of the cluster hierarchy. In addition, our approach makes it natural to use graph visualization techniques to support the user in handling inexpressive labels. Namely, categories with inexpressive labels can be visually related to more meaningful ones.
György Frivolt and Mária Bieliková:
"Topology Generation for Web Communities Modeling"
Abstract: In this paper we present a model of Web communities, which constitute a part of the Web structure. Proposed model is aimed at characterization of topology behind the Web communities. It is inspired by small world graphs that show behaviors similar to many natural networks. We model Web communities as clusters of Web pages using graph grammars. Graph grammars allow us to simulate the structural properties of Web communities including their growth and evolution. An example of grammar is presented. We discuss possibilities for the utilization of the proposed model for research of Web community properties and their identification.
Hamid Nazerzadeh, Mohammad Ghodsi:
"RAQ: A Range-Queriable Distributed Data Structure"
Abstract: Different structures are used in peer-to-peer networks to
represent their inherently distributed, self-organized, and
decentralized memory structure. In this paper, a simple
range-queriable distributed data structure, called RAQ, is
proposed to efficiently support exact match and range queries over
multi-dimensional data. In RAQ, the key space is partitioned among
the network with n nodes, in which each element has links to
O(\log n) other elements. We will show that the look-up query
for a specified key can be done via O(\log n) message passing.
Also, RAQ handles range-queries in at most O(\log n)
communication steps.
Hans Huttel and Jiri Srba:
"Recursion vs. Replication in Simple Cryptographic Protocols"
Abstract: We use some very recent techniques from process algebra to draw
interesting conclusions about the well studied class of ping-pong
protocols introduced by Dolev and Yao. In particular we show that all
nontrivial properties, including reachability and equivalence checking
wrt. the whole van Glabbeek's spectrum, become undecidable for a very
simple recursive extension of the protocol. The result holds even if no
nondeterministic choice operator is allowed. We also show that the
extended calculus is capable of an implicit description of the active
intruder, including full analysis and synthesis of messages in the sense
of Amadio, Lugiez and Vanackere. We conclude by showing that
reachability analysis for a replicative variant of the protocol becomes
decidable.
Henning Fernau:
"Two-Layer Planarization: Improving on Parameterized Algorithmics"
Abstract: A bipartite graph is biplanar if the vertices can be
placed on two parallel lines in the plane such that there are
no edge crossings when edges are drawn as straight-line segments.
We study two variants of biplanarization problems:
- Two-Layer Planarization TLP: can $k$ edges be deleted from
a given graph $G$ so that the remaining graph is biplanar?
- One-Layer Planarizatoin OLP:
fix the order of the vertices on one layer.
Improving on earlier works of Dujmovi\'c et al.,
we solve the TLP problem in $O^*(5.19^k)$ time and the
OLP problem in $O^*(2.53^k)$ time.
Moreover, we derive a small problem kernel for OLP.
The paper contains an appendix with all proofs.
Jiu Jun Chen, Ji Gao, Jun Hu, and Bei Shui Liao:
"Dynamic Mining for Web Navigation Patterns Based on Markov Model"
Abstract: Web user patterns can be used to create a more robust web information service in personalization. But the user interests are changeable, that is, they differ from one user to another, and they are constantly changing for a specific user. This paper presents a dynamic mining approach based on Markov model to solve this problem. Markov model is introduced to keep track of the changes of user interest according to his or her navigational behaviors. Some new concepts in the model are defined. An algorithm based on the model is then designed to learn the user's favorite navigation paths. The approach is implemented in an example website, and the experimental results proved the effective of our approach.
Jérémie Chalopin:
"Local Computations on Closed Unlabelled Edges: the Election Problem and the Naming Problem"
Abstract: The study of the different local computations mechanisms is very
useful for delimiting the borderline between positive and negative
results in distributed computing. We consider here a model where in a
computation step, two neighbours can modify their states according
only to their precedent states. This model is an intermediate model
between the powerful model of Mazurkiewicz and the more realistic one
of Yamahita and Kameda. It is quite close from the model studied by
Angluin, but in the model studied here a node cannot distinguish its
neighbours.
We consider in this paper two important algorithmic problems: the
election problem and the naming problem which turn out to be
equivalent in the model studied here. We introduce pseudo-coverings,
which are particular graph morphisms, to characterize the graphs where
these problems can be solved.
Kayhan Erciyes, Ali Alp, Geoffrey Marshall:
"Serial and Parallel Multilevel Graph Partitioning using Fixed Centers"
Abstract: We present new serial and parallel algorithms for multilevel graph partitioning. Our algorithm has coarsening, partitioning and uncoarsening phases like other multilevel partitioning methods. However, we choose fixed nodes which are at least a specified distance away from each other and coarsen them with their neighbor nodes in the coarsening phase using various heuritics. Using this algorithm, it is possible to obtain experimentally much more balanced partitions with substantially decreased total edge costs between the partitions than other algorithms. We also developed a parallel method for the fixed centered partitioning algorithm. It is shown that parallel fixed centered
Luca Forlizzi, Juraj Hromkovic, Guido Proietti, Sebastian Seibert:
"On the Stability of Approximation for Hamiltonian Path Problems"
Abstract: We consider the problem of finding a cheapest Hamiltonian path of a complete graph
satisfying a relaxed triangle inequality, i.e., such that for some parameter \beta > 1, the
edge costs satisfy the inequality c({x; y})\le \beta (c({x; z}) + c({z; y})) for every triple of vertices x, y, z.
There are three variants of this problem, depending on the number of prespecified endpoints:
zero, one, or two. For metric graphs, there exist approximation algorithms, with approximation ratio
3/2 for the first two variants and 5/3 for the latter one, respectively.
Using results on the approximability of the Travelling Salesman Problem with input graphs satisfying
the relaxed triangle inequality, we obtain for our problem approximation algorithms with ratio
min(\beta^2 + \beta; 3/2\beta^2) for zero or one prespecified endpoints, and 5/3\beta^2 for
two endpoints.
M. Chimani, G.W. Klau, R. Weiskircher:
"Non-Planar Orthogonal Drawings with Fixed Topology"
Abstract: This paper discusses the calculation of bend minimal shapes for non-planar graphs with given topology. Based on the Simple-Kandinsky drawing standard – a simplification of the more complex Kandinsky standard – we show the disadvantage of using standard models for this
task: We show that the minimal bend count is suboptimal, when these models are applied to non-planar graphs; it is therefore beneficial to extend these standards.
We define such an extension for Simple-Kandinsky called Skanpag (Simple-Kandinsky for Non-Planar Graphs). It treats edge crossings in a special way by letting them share identical grid points where appropriate. Hence it allows crossings of whole bundles of edges instead of single edges only. Besides having a reduced number of bends, drawings following this standard are easier to read and consume less area than those produced by the traditional approaches.
In this paper, we show a sharp upper bound of the bend count, if the standard Simple-Kandinsky model is used to calculate shapes for non-planar graphs. Furthermore, we present an algorithm that computes provably bend-minimal drawings in the Skanpag standard.
Maciej Kurowski:
"Planar Straight-Line Drawing in the $\mathcal{O}(n) \times \mathcal{O}(n)$ Grid with Angular Resolution $\Omega(1/n)$"
Abstract: Anonymous communication with onions requires that
the user application determines the whole routing path of an onion.
This has certain disadvantages, potential dangers, and
does not fit well to the current layered architecture
of communication networks.
We show that using universal re-encryption encoding
can solve many of these problems by providing
much flexibility -- onions can be created on-the-fly or in advance by
different parties.
We show also how to attach a digital signature
of a processing server so that the signature can be
universally re-encrypted and does not betray a path of a message.
Olli Luoma:
"Modeling Nesting Relationships in XML Documents Using Relational Databases"
Abstract: Structural joins, i.e., operations that determine all occurrences of parent/child or ancestor/descendant relationships between node sets, are at the heart of XML management systems. To perform these joins, the systems exploit the information about the nesting relationships between elements, attributes, and pieces of text in XML documents. Since performing the structural joins is often the most time-consuming phase in query evaluation, the method chosen to model the nesting relationships has a considerable impact on the overall effectiveness of any XML management system. In this paper, we discuss four different methods for modeling the nesting relationships using relational databases. We also propose a novel modeling method and present the results of our comprehensive performance experiments.
Patrick Healy and Karol Lynch:
"Fixed Parameter Tractable Algorithms for Testing Upward Planarity"
Abstract: We consider the problem of testing a digraph $G=(V,E)$ for
upward planarity. In particular we present two fixed-parameter tractable (FPT) algorithms for testing the upward planarity of $G$. Let $n$ be the number of vertices of $G$, let $t$ be the number of triconnected components of $G$, and let $c$ be the number of cut-vertices of $G$. The first upward planarity testing (UPT) algorithm we present runs in $O(2^t * t! * n^3)$-time. The previously known best result is an $O(t! * 8^t * n^3 + 2^{3*2^c} * t^{3*2^c} * t! *8^t * n)-time algorithm by Chan [Proc. of the 12th Annual European Symposium on Algorithms (to appear)]. We use the method of reduction to a problem kernel to develop a second UPT algorithm that runs in $O(n^2 + k^4(2k + 1)!)$-time, where $k = |E| - |V|$. In addition to this we show that all acyclic digraphs (DAGs)
with $k < 2$ are upward planar. We also give an upper bound on the number of edges in an arbitrary upward planar digraph, in terms of the number of vertices it contains. We use the SPQR-tree data structure.
Piotr Habela, Krzysztof Kaczmarski, Hanna Kozankiewicz, Kazimierz Subieta:
"Modeling Data Integration with Updateable Object Views"
Abstract: Recently, a range of applications of views increases. Views are not anymore tightly related to classical databases – there are proposals to use them as means of data transformation and integration in distributed environment. Despite many aspects of view applications, there is still lack of suitable graphical notation that would help designers by providing clear notions from the very early stage of system development. Therefore, our objective is to propose a suitable extension of UML supporting the design process. We focus on modeling object-oriented updateable views in the context of data integration. We believe it is one of the most prominent appliances of views. The paper describes assumed general features of updateable object views and fits them into an object-oriented meta-model. Based on this, we suggest the necessary view-specific notation elements, and present some examples of view modeling.
Prasad Jayanti, Srdjan Petrovic, Neha Narula:
"Read/Write Based Fast-Path Transformation for FCFS Mutual Exclusion"
Abstract: Lamport (1987) observed that in practical systems
processes rarely compete for the entry into the Critical Section.
This led to research on fast mutual exclusion algorithms that,
in the absence of contention, allow a process to enter and exit the Critical Section in O(1) steps.
Anderson and Kim (2001) designed a general transformation
that can turn any mutual exclusion algorithm A into a new algorithm A' that is fast.
Their transformation, however, does not preserve the fairness property FCFS.
The main result of this paper is the design of a new transformation
which works similarly as Anderson and Kim's, but additionally preserves FCFS.
Our transformation, like theirs, requires only read/write registers.
Przemyslaw Kazienko, Mariusz Matrejek:
"Adjustment of Indirect Association Rules for the Web"
Abstract: The concept of indirect association rule, which is useful to discover
indirect relationships existing within data sets, is the extension of the idea of
classic direct association rules. Experiments on e-commerce web logs were
performed to determine the importance of individual parameters of indirect
patterns extracted from web user sessions. Especially minimal indirect
confidence and the method of estimation of partial indirect confidence were
investigated. Indirect rules are obtained from direct ones using minimal direct
confidence and support. The influence of these both thresholds on the quantity
of indirect rules was studied. The cut-point of indirect rules and normalization
issues were also discussed. The most important results and conclusions were
presented in the paper.
Robert Steele, William Gardner, Tharam Dillon, Abdelkarim Erradi:
"XML-based Declarative Access Control"
Abstract: XML, a self-describing and semi-structured data format, is becoming a standard to represent information and exchange data between applications across the Web. XML repositories are also starting to be used either to store data or as an interoperability layer for legacy applications and data sources. The widespread use of XML highlights the need for flexible access control models for XML documents to protect sensitive and valuable information from unauthorised access. This paper presents a novel declarative access control model and elaborates how this model allows the expression of access control rules in XML. The paper further introduces the operational semantics of the model by describing the Xplorer engine which supports search-browse-navigate activities on XML repositories. Xplorer takes as inputs XML-based data schema, instance data and access control rules to auto-generate an access control-enabled Web application in accordance with these rules.
Satoshi Tayu, Turki Ghazi Al-Mutairi, and Shuichi Ueno:
"Cost-Constrained Minimum-Delay Multicasting"
Abstract: We consider a problem of cost-constrained minimum-delay
multicasting in a network,
which is to find a Steiner tree spanning
the source and destination nodes
such that the maximum total delay along a path
from the source node to a destination node is minimized,
while the sum of link costs in the tree is bounded by a constant.
The problem is NP-hard even if the network is
series-parallel.
We present a fully polynomial time approximation scheme
for the problem if the network is series-parallel.
Stefan Porschen:
"On Some Weighted Satisfiability and Graph Problems"
Abstract: In the first part of this paper
we address several weighted satisfiability problems.
Among others, we provide linear time algorithms solving
MIN(MAX)-NAESAT and MIN(MAX)-XSAT for 2CNF formulas and arbitrary real
weights assigned to the variables.
In a second part we investigate the relationship between the problems
maximum weight independent set (MAX-IS) in a graph and the problem exact
satisfiability (also known as 1-in-sat, XSAT for short). We show that
$\#$XSAT can be solved in time $O(2^{0.40567n})$ significantly improving on a
bound $O(2^{0.81131n})$ provided by Dahl\"of and Jonsson in [Proc. of 13th ACM-SIAM Symp.of Discrete Algorithms, 2002].
Walter Didimo:
"Computing Upward Planar Drawings Using Switch-regularity Heuristics"
Abstract: Let $G$ be an upward planar embedded digraph. The classical approach used to compute an upward drawing of $G$ consists of two steps: (i) A planar $st$-digraph including $G$ is constructed adding a suitable set of dummy edges; (ii) A polyline drawing of the $st$-digraph is computed by using standard techniques, and dummy edges are then removed. For computational reasons, the number of dummy edges added in the first step should be kept as small as possible. However, as
far as we know, there is only one algorithm known in literature to compute an $st$-digraph including an upward planar embedded digraph. In this paper we describe an alternative heuristic, which is based on the concept of \emph{switch-regularity} introduced by Di Battista and Liotta (1998). We experimentally prove that the new heuristic significantly reduces the number of dummy edges added to determine the including $st$-digraph, saving precious computation time and space. We
also show that the reduction of dummy edges dramatically improves the total edge length of the final drawings.
Xuefeng Zhu, Zhi Jin:
"Ontology-Based Inconsistency Management of Software Requirements Specifications"
Abstract: Automated inconsistency management of requirements is key to the development of trustworthy software systems. Although there are alreay a lot of work on this topic, most of them are limited in treating inconsistency at syntactic level. We still lack a promising method for managing requirements inconsistency at semantic level.
This paper first proposes a requirements refinement model, which suggests that interactions between software agents and their ambiences are essential to capture the semantics of requirements. We suppose that real effects of these interactions is to make the state of entities in the ambiences changed. So we explicitly represent requirements of a software agent as a set of state transition diagrams, each of which is for one entity in the ambiences. Domain ontology then is used to detect and solve inconsistency.
Fei Shi:
An Index Structure for Local Similarity Searches
Abstract: We present an index structure and algorithms that support local similarity
searches in DNA and amino acid sequence databases as the commonly used
BLAST program does. Our strategy is completely different from the one that
is used in BLAST: we organize the sequences in the database in such a way
that we only have to examine a small subset of the database sequences to find
those sequences that are similar to the query sequence, based on the given scor-
ing scheme (PAM, BLOSUM, or other scoring schemes, such as weighted edit
distance). The BLAST program, however, has to examine EVERY sequence
in the database. Since in a database of thousands sequences, generally only a
handful, if any, will be homologous to the query sequence, our index structure
allows us to perform local similarity searches in large sequence databases much
faster than the BLAST algorithm, specially in cases where the query sequences
are very long (e.g, several thousand bases). Our index structure is implemented
using a data structure for spatial objects, called M-tree, and we use a similarity
measure for strings, called Q-gram distance, to filter out those database se-
quences that have littel chance of matching our query sequence when we search
the database.
Abstract: This paper presents a multiagent system (called AGWI) which should assist users in information retrieval in Internet. In this system consensus methods are applied for reconciling inconsistency of answers generated by agents for the same query. The system has been created by means of platform IBM Aglets.
Adam Niewiadomski:
"Interval-valued data structures and their applications to e-learning"
Abstract: The paper is devoted to the problem of replacing crisp numbers
with interval numbers in soft computations. Intervals used as numbers
are frequently met in human natural language, especially, when
some imprecise and vague predicates, i.e.many, high, quickly, need to be described more specifically (concerning money, speed, dimensions, time, mass etc.). Intervals appear also in engineering data, as descriptions of amount, bounds, and limits, instead of crisp values.
In the beginning sections of the article, the original propositions of
interval-valued matrix and interval-valued vector are introduced. Then, three classic similarity measures for vectors are originally extended with respect to interval data. Finally, the presented structures and template matching methods are used in the process of automated evaluation of student tests in e-learning and e-testing (distance learning and examining within the Internet).
Ana C. V. de Melo & Adilson de J. Sanchez:
"Bayesian Networks in Software Maintenance Management"
Abstract: Managing software maintenance is rarely a precise task due to
uncertainties concerned with resources and services descriptions.
Even when a well-established maintenance process is followed, the
risk of delaying tasks remains if the new services are not
precisely described or when resources change during process
execution. Also, the delay of a task at an early process stage may
represent a different delay at the end of the process, depending
on complexity or services reliability requirements. This paper
presents a knowledge based representation (Bayesian Networks) for
maintenance project delays based on specialists experience.
Aneta Poniszewska - Maranda, Gilles Goncalves, Fred Hemery:
"Representation of extended RBAC model using UML language"
Abstract: The role-based access control (RBAC) model is one of the policies used to access control in information systems for enterprises. The RBAC model is a powerful technology for managing and enforcing security in large-scale, enterprise-wide systems. Many implementations of this model, including the RBAC96 model, have been
already proposed. However assigning permissions to roles in standard RBAC model is too complex to accomplish this task directly.
This paper presents an extension of the standard RBAC model together with its representation using the Unified Modeling Language (UML).
The presented model is developed for the role engineering in the security of information system.
In the paper the union of the RBAC model, which controls access in the information system, and the UML language, i.e. a unified method of object analysis and design, is proposed. The presented implementation of the RBAC model consists in role creation via defining appropriate permissions. The entire procedure is performed in two stages; first permissions assigned to a function are defined, and then definitions of functions assigned to a particular role are provided.
Fritz Mayer-Lindenberg:
"A management scheme for the basic types in high level languages"
Abstract:
This note describes a type concept for the basic data types handled in
the applications of digital systems, numbers and bit fields, which are usually
predefined in higher level languages and serve as the basis for application
spe-cific data types and classes. It has been implemented in a real-time language
for parallel embedded systems and is motivated by the fact that such systems may
have to use a multitude of application-specific number types. The type concept
actually applies to programming languages for all classes of applications. It
pro-poses the use of an abstract data type of numbers for which the various
enco-dings of numbers provide implementations. This simple approach not only allows
non-standard encoding types to be added as needed but also provides common formats
for input and output and derived numeric data types that aren't bound to a specific
encoding. Related to the handling of the basic data types is a conversion policy.
For bit fields, conversions are substituted by word number changes of multi-word
codes. Finally, the abstract number type can be used to simplify the related typing
of functions that no longer need to specify the encoding of all their arguments and
results.
Heikki Hyyro, Yoan Pinzon, Ayumi Shinohara:
"Fast Bit-Vector Algorithms for Approximate String Matching under Indel-Distance"
Abstract: The approximate string matching problem is to find all location at
which a query of length $m$ matches a substring of a text of
length $n$ with at most $k$ differences (insertion, deletion, and
substitution). The fastest solutions in practice for this problem
are the bit-parallel NFA simulation algorithms of Wu\&Manber and
Baeza-Yates\&Navarro, and the bit-parallel dynamic programming
algorithm of Myers. In this paper we present modified versions of
these algorithms to deal with the restricted case where only
insertions and deletions (called indel for short) are permitted.
Although the solution to the restricted case appeared to be
easier, we will show that for the case of bit-parallel dynamic
programming, the problem was indeed more complex to solve. In the
end we present a set of experimental results comparing each of the
resulting algorithms.
Jun Feng, Naoto Mukai, Toyohide Watanabe:
"Stepwise Optimization Method for k-CNN Search for Location-based Service"
Abstract: The issue of how to provide location-based service (LBS)
attracts many researchers. In this paper, we focus on a typical situation
of LBS which is to provide services for users in cars that move in
a road network. For such kind of users, the problem of k-CNN search
along a specific route on road network is to find out k nearest neighbor
(k-NN) objects for any place on the route. k nearest neighbors are
selected based on the path length from the route to the objects, and
the continuous search for all the points on the route should be considered.
A k-CNN search method is proposed by using an incremental k-NN
search based on road network. The method is an extension of CNN search
method proposed by adding new data structure – a fixed length queue
for recording up-to-now intermediate results. Because the search regions
can be reduced stepwise by the intermediate results, our k-CNN search
is efficient.
Liliana Favre:
"Well-Founded Metamodeling for Model-Driven Architecture"
Abstract: A recent initiative of the Object Management Group (OMG) is the
Model-Driven Architecture (MDA). MDA proposes to use different models at
different stages of the development and to employ automated
transformations between them. It distinguishes platform independent
models (PIM), platform specific models (PSM) and code. Metamodeling
plays a key role in MDA. A combination of formal specification
techniques and metamodeling can help us to address model driven
developments. In this paper we describe a conceptual framework for
MDA-based metamodeling that integrates UML/OCL and formal
specifications. We propose an algebraic language, called NEREUS, to cope
with concepts of UML metamodels. NEREUS can be viewed as an intermediate
notation open to many other formal languages. A transformational system
to translate UML/OCL to NEREUS was defined. We specify mappings between
PIM and PSM metamodels in terms of UML/OCL and NEREUS.
Lubomir Torok:
"Volumes of 3D drawings of homogenous product graphs"
Abstract: 3-dimensional layout of graphs is a standard model for orthogonal graph drawing.
Vertices are mapped into the 3D grid and edges are drawn as the grid edge
disjoint paths. The main measure of the efficiency of the drawing is the volume
which is motivated by the 3D VLSI design. In this paper we develop a general
framework for efficient 3D drawing of product graphs in both 1 active layer
and general model. As a consequence we obtain several optimal drawing
of product graphs when the factor graphs represent typical networks like CCC,
Butterfly, star graph, De Bruijn... This is an analogue of a similar work done
by Fernandez and Efe for 2D drawings using a different approach.
Marcel Jirina, Marcel Jirina, jr.:
"Feature Selection by Reordering"
Abstract: Feature selection is an important step in data processing. It serves for both reduction of the total amount of available data (removing of redundant or unimportant data) and improvement of the whole behavior of a given induction algorithm (removing data that cause deterioration of the results). This paper discusses this problem in more detail. A method of proper selection of features for an inductive algorithm is discussed. The main idea behind the method consists in proper descending ordering of features according to a measure of new information contributing to previous valuable set of features. The measure is based on comparing of statistical distributions of individual features including mutual correlation. A criterion (level) below which the features can be omitted without loss of information is discussed. A mathematical theory of the approach is described. Results of the method applied to both artificial and real-life data are shown. Finally, a comparison with other published results is given.
Nele Smeets, Eric Steegmans:
"A Methodology for Writing Class Contracts"
Abstract: One of the principles of Design by Contract is that contracts for software components must be written in a declarative way, using a formal, mathematically founded notation. When we apply the Design by Contract methodology in a naive and straightforward way, we risk ending up with a lot of unwanted duplication. In this paper, we describe a methodology for writing class contracts that avoids specification duplication and that gives rise to uniform class specifications with a clear and fixed structure.
Radoslav Fulek, Hongmei He, Ondrej Sykora, Imrich Vrto :
"Outerplanar Crossing Numbers of 3-row Meshes, Halin graphs and Complete p-partite graphs"
Abstract: An outerplanar (also called circular, convex, one-page) drawing
of an n-vertex graph G is a drawing in which the vertices of G are placed on a circle and each edge is drawn using one straight line segment.
We derive exact results for the minimal number of crossings in any outerplanar drawings of some classes of graphs, like 3-row meshes, Halin graphs and complete p-partite graphs with equal size partite sets.
Rados³aw Adamus, Kazimierz Subieta:
"Tier Aspect Model Based on Updatable Views"
Abstract: The tier aspect model addresses Aspect Oriented Programming (AOP) in the context of database applications. It is a new technique of separation of concerns through tiers implemented as virtual object-oriented updatable views. The code of an aspect related to particular data is encapsulated within a separate tier that overrides all generic operations performed on the data. Because virtual objects delivered by object-oriented updatable views cannot be distinguished from stored objects by any programming option, any aspect tier can be in turn overridden by a next aspect tier. Thus aspect tiers form a chain of views, which overrides a given item of the data model, e.g. a collection of objects, an attribute, a method, etc. Any operation on the item is augmented by corresponding pieces of code from the overriding views. A code can do any extra action that is required by a particular aspect on the given item, e.g. security, licensing, integrity constraints, monitoring and others. The paper explains technical details concerning implementation of the technique within an object-oriented database management system. The idea is based on the Stack-Based Approach (SBA) to object-oriented query/programming languages and the novel idea of virtual updatable views. The tier aspect model is being implemented for the prototype object-oriented database server ODRA.
Raitis Ozols, Rusins Freivalds, Jevgenijs Ivanovs, Elina Kalnina, Lelde Lace, et al.:
"Boolean functions with a low polynomial degree and quantum query algorithms"
Abstract: The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem. We present an infinite sequence of Boolean functions for which deg(f)=(D(f))^1.79... improving the result by A.Ambainis.
Roman Filkorn, Pavol Návrat:
"An Approach for Integrating Analysis Patterns and Feature Diagrams into Model Driven Architecture"
Abstract: Knowledge-capturing approaches cover a wide variety of software engineering activities, and this variety impedes to easily find relations and integration between them. Recent researches consider combinations of knowledge with a view to find and elaborate new knowledge. One of such movement is OMGs Model Driven Architecture (MDA) a novel strict model-centric engineering approach based on platform-specific abstractions and model transformations. We give a short overview on selected knowledge-based techniques along with more details on MDA. On a background of a case study integrating knowledge captured in Analysis Patterns, incorporating Feature Modeling technique to elaborate additional knowledge, we develop and propose a method for mapping for the initial steps in MDA transformations.
Abstract: Suffix tree is a widely studied data structure with a range of applications.
Although originally developed for string matching algorithms, it has
proved to be useful for implementation of various data compression
methods, including both statistical and dictionary-based techniques.
This paper explores a completely different way how the this structure
could be used putting the principle of ´a suffix tree as an efficient
data structure for an existing method´ upside down. Based on suffix
trees properties, a brand new algorithm is presented. Resulting from
a thorough study of algorithms of suffix tree construction by McCreight
and Ukkonen, several variants of suffix tree based compression are
proposed. Our strategy is to construct a suffix tree for the data
to be compressed and, while doing so, store the decisions made. The
original data can be reconstructed later from such information. Implementation
issues are discussed and our algorithms are tested on a standard
text corpus and compared with existing compression methods.
Ondřej Bojar, Cyril Brom, Milan Hladík, Vojtěch Toman:
"The Project ENTs: Towards Modeling Human-like Artificial Agents"
Abstract: The Project ENTs aims at providing a universal high-level tool for prototyping human-like artificial agents. The main features of this tool are a virtual test-bed environment and E language, which enables description of human-like agents behaviours using various techniques, in particular reactive planning and BDI-architecture. In this paper, we present first generation of this tool together with an example agent - an artificial gardener that acts in a virtual family house. We then briefly discuss applicability of this tool and introduce some requirements for its second generation.
Marek Petrík:
"Statistically Optimal Combination of Algorithms"
Abstract: Usually, the most practical way of achieving efficiency of an algorithm is by limiting its generality. Then, the algorithm is efficient, but only for a specific set of problem instances. In practice, the problem instances, which must be solved, do not necessarily correspond to the sets that are solved efficiently by one algorithm. It is then possible to run more algorithms concurrently, each specializing on a different set of the problem instances. We present a method addressing optimality of composition of several decision algorithms. Optimality is considered with regard to the expected solution time. Two possible approaches are presented. The first, static approach, leads to a simple analytically calculable solution. The second, dynamic approach, results in formulation of the combination of algorithms as a Markov Decision Process. In comparison to the static approach, the dynamic approach offers combinations that are more effective but harder to calculate and implement. There is also an approximation algorithm presented for the dynamic approach. Combination of algorithms has proved to be quite effective in case of SAT problem. Dynamic schedules truly offered more effective combinations, but the difference was not as significant as expected. Both methods are therefore attractive for future research.
Vladimír Marko
"Describing Structural Properties of Object-oriented Design Patterns"
Abstract:
Specification of design patterns intended to be usable for tool-assisted
instantiation, annotation, eventual automated pattern recognition consists of
structural and behavioral compound. The structural component models
responsibilities of pattern collaboration and points where to weave application
specific concerns. This paper evaluates different prospective approaches to
describing the model of design pattern structure, i.e. roles and relationships
among them which determine design pattern instances in terms of possible
collaborations of concrete actors. It is also indicated, how the design pattern
can be modeled using UML-based metamodel.
Accepted Communication Papers
Akihiro Yamamura, Tatiana Jajcayova, Takashi Kurokawa:
"Oblivious transfer and private information retrieval based on the p-subgroup problem"
Abstract: We propose efficient oblivious transfers and private information retrieval
schemes using Okamoto-Uchiyama's encryption function.
Our private information retrieval enables the user to retrieve
block data from the database consisting of several binary strings
without iteration.
A symmetric private information scheme is also constructed
only under the $p$-subgroup assumption.
Derya Birant, Alp Kut:
"Design a Web Service-Based Model for Running Parallel Applications"
Abstract: Web based computing is one of the very fast developing technique in computer applications. Web service based computing is the important part of web based computing. Traditionally, Web Services are invoked from one application to work sequentially in a distributed environment. This study introduces a new design and implementation model for applications that run several Web Services in parallel. It presents a new approach: Web Service-Based Parallel Computing. This approach provides multitasking with using thread mechanisms. The purpose of the study is to allow users to satisfy their parallel programming needs without the knowledge of any parallel programming tool such as MPI or PVM. This work also presents an example study implemented for explaining how Web Service-Based Parallel Computing can be done. In addition, this study contains the experimental results of related work. Finally it identifies and discusses some important problems and research issues related to this approach.
Edgar Głowacki, Tomasz Serafiński, Kazimierz Subieta:
"Dependencies Supporting Assessment of the Scope of Software Change"
Abstract: The necessity of change is an inherent feature of information systems. Change introduction implies problems that consist in ascertaining and then performing the minimal set of actions adding the requested business value to the existing software product. Usually, however, the information gathered about the product and the development process does not supply enough data to solve the above problems. The paper specifies the kinds of information that is necessary for efficient future modification(s) of a software product. This information may be used in the future for reliable assessment of the scope, cost and time necessary for the intended change. Furthermore combined with supplementary data, it may be an indispensable source of knowledge required for proper quality assurance if the need for change in software product appears.
Hongmei He, Matthew C. Newton, Ondrej Sykora:
"GAs for 1-Side Bipartite Graph Drawings and for Outerplanar Graph Drawing is Best!"
Abstract: The basic problem with drawing of bipartite graphs is two layer automatic drawing where the two vertex partitions are put in distinct points on two parallel lines and edges are drawn as straight line segments between the vertices. This is the
basic building block used for drawing hierarchical graphs or producing row-based VLSI layouts. The most important objective is minimisation of the number of crossings in the drawing as the aesthetics and readability of graph drawings depend on the number of edge crossings. VLSI layouts with fewer crossings are more easily realisable and consequently cheaper.
There are two variants of the problem: the one-sided and two-sided crossing minimisation problems. In the one-sided problem the vertices of one part of the bipartite graph are placed in fixed positions and the positions of the vertices of the other part, on the other line (called the free side), are found so that
the number of pairwise edge crossings is minimised. In the two-sided problem no vertices are fixed. As both problems are NP-hard, a lot of different heuristics to solve the problem have been designed.
Another usual type of the graph drawing is the outerplanar
(also called circular, convex and one-page) drawing.
In this type of the drawing one places vertices
of a connected graph G along a circle, and
the edges are drawn as straight lines. Similarly as with bipartite
drawing, our objective is to minimise the
number of crossings in outerplanar drawings.
Genetic algorithms (GAs) are a class of randomised optimisation heuristics based loosely on the biological paradigm of natural selection. While the exact mechanisms behind natural evolution are not very well known, some aspects have been studied in considerable depth. It is believed that chromosomes are the information carriers and that the evolution process works at the chromosome level through reproduction. The reproduction can be made by either combining chromosomes from the parents to produce offspring, a process called
crossover, or by a random change occurring in the chromosome pattern, termed mutation.
In this paper we focus on the design of a genetic algorithm for the one-sided bipartite drawing problem and outerplanar drawing problem.
The results for one-sided problem we compare with Penalty Minimisation. PM is probably the best one-sided heuristic currently available in terms of both quality of results and speed. For graphs without a structural symmetry our GA achieves better results (drawings with lower numbers of crossings) than PM. Our GA does not fare so well for graphs that do have a symmetrical structure (cycles, meshes, hypercubes, etc.), where PM very quickly finds optimal or hypothetically optimal drawings.
If run on different initial random seeds and for a longer time, however, our GA can also find the optimal drawings. For all types of graph, a combination of PM and our GA can be used, to achieve very good results in a respectable amount of time.
The results of our GA for outerplanar drawings were compared with the previously known heuristic algorithms such as Makinen's algorithm, CIRCULAR+ algorithm of Six and Tollis, algorithm of Baur and Brandes and our own heuristic algorithms. The results achoieved by the GA are the best.
Christoph Fünfzig:
"Iconic Drawing of Scenegraph Structure"
Abstract: In this paper we consider graph drawing for the application of scenegraphs as encoded by VRML97/X3D.
As these fileformats store the structure and contents of threedimensional scenes in a directed acyclic graph,
the techniques for drawing rooted trees are suitable but require much drawing space.
Therefore we devised a smart, interactive drawing technique, which uses a detailed view of the current point
of interest and an iconic view of subgraphs besides the current point of interest.
This interactive method balances detail and overview much better than classic techniques to cope with limited space like fisheye views.
Concerning implementation it is easy to implement with a small LOC count (in Java).
Jaroslav Kral, Michal Zemlicka:
"Modeling of Service-Oriented Systems"
Abstract: Service-oriented software systems (SOSS) are becoming the leading paradigm of
contemporary software engineering. SOSS are virtual p2p systems of autonomous
software components (services) behaving like the service in mass services systems of
real world. There are different types of SOSS. The ones used in e-commerce (alliances)
have properties different from the properties of broad collections of systems in which all
their services are known. Examples are e-government or information systems of
decentralized enterprises. We call such systems confederations. And we shall namely
discuss them. Confederations admit various implementations being difficult to describe
by known modeling methods like UML. The reason is that the diagrams are based on
object-oriented philosophy and object oriented philosophy appeared to be different from
the service-oriented one. It is especially true for the diagrams applicable to describe the
(virtual) logical architecture (network of services) of confederations. We show that such
diagrams should combine and generalize some features of data-flow diagrams and of the
diagrams of Petri nets. The complexity of the confederations' model is caused by the fact
that different parts of the confederation may use differnt interface types like database
sharing, message passing, method invocation. We believe, however, that the full
model-driven definition of confederations is not the matter of the near future. It is not
excluded that it is not any feasible aim at all.
J. Christian Attiogbé:
"Practical Combination of Theorem Proving and Model Checking for the Multi-facet Analysis: a Case Study"
Abstract: Theorem proving and model checking are recognized as formal analysis techniques used to mechanize formal methods of software development. However the tools based on them are not widely and systematically used as they should. One reason for this is the lack of practical approaches to guide the users. Another reason is that the tools often focus on one specific aspect of analysis. Tool-assisted analysis of software systems and convenient guidance to practise formal methods are still motivating challenges. This paper addresses these challenges. It presents using a case study, how one can carry out both analysis techniques by using a stepwise approach.
Michael Kaufmann, Katharina Lehmann, Andreas Gerasch:
"Area-optimal hv-like tree drawings with a fixed aspect ratio"
Abstract: In most practical applications a certain aspect ratio
for the layout of a graph is required or at least should be obeyed.
This problem has been attacked for certain graph classes, especially for binary
trees and also for directed graphs.
Here, we introduce three generalized hv-layouts for ordered trees with arbitrary degree that keep the easy
readibality of the classic binary hv-layout. We develop
efficient algorithms for all three variants that are guaranteed to yield an area-optimal drawing for any given aspect ratio.
Rastislav Lencses:
"Indexing for Information Retrieval System supported with Relational Database"
Abstract: We deal with indexing of document collection for information retrieval engine which use relational database as data store. We will present an algorithm for index generation, compare it with other algorithms in this area and estimate its time complexity. We created a distributed version of this algorithm and discuss about its effectiveness.
Robert Wrembel, Bartosz Bebel, Tadeusz Morzy:
"Implementation and Evaluation of Storage Structures for Data Sharing in a Multiversion Data Warehouse "
Abstract: A data warehouse (DW) is a large database that stores data from various external data sources (EDSs), that often change their structures. The evolution of EDSs has to be reflected in a DW, by means of schema changes. For this purpose, and for the purpose simulating alternative business scenarios, a multiversion DW seems to be promising. In such a DW, each DW version describes a schema and data at certain period of time. In many cases two consecutive DW versions may contain identical subsets of data, which should be shared, in order to reduce storage space. In this paper we propose data version storage structures, that allow sharing data between several DW versions. The structures were evaluated by experiments aiming at measuring how fast shared data can be retrieved and managed by using these structures.
Zoltan Fazekas:
"Concern-Based Software Evolution"
Abstract: The implementation of concerns by means of changes of the source code of a program is usually preceded by a time-consuming analysis of the source code. To come around this, we propose an approach based on concerns as the central concept of change management. With this approach we address in opposite to other separation of concerns approaches not only concerns in the current version, but in the whole evolution history of the program. We use the association between changes and concerns to support programmers in diverse activities such as finding locations in the program to maintain or removing undesired features from the program. In this paper we provide a brief introduction of our research results.
On-line version of the SOFSEM 2005 Proceedings printed by Springer-Verlag can be found at
SpringerLink website.