2020

W.Rost
Mining of DSLs and generator templates from reference applications
IMODELS '20: Proceedings of the 23rd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems: Companion ProceedingsOctober 2020, Article No.: 32, pp 1–7
Abstract:
Domain-Specific Languages (DSLs) found application in different domains. The development of Model-Driven Development (MDD) components is facilitated by a wealth of frameworks like EMF, Xtext, and Xtend. However, the development of the necessary IDE components still can take up to several weeks or even months until it can be used in a production environment. The first step during the development of such an MDD infrastructure is to analyse a set of reference applications to deduce the DSL used by the domain experts and the templates used in the generator. The analysis requires technical expertise and is usually performed by MDD infrastructure developers, who have to adhere to a close communication with domain experts and are exposed to high cognitive load and time-consuming tasks.
The objective of this PhD project is to reduce the initial effort during the creation of new MDD infrastructure facilities for either a new domain or newly discovered platforms within a known domain. This should be made possible by the (semi-)automatic analysis of multiple codebases using Code Clone Detection (CCD) tools in a defined process flow. Code clones represent schematically redundant and generic code fragments which were found in the provided codebase. In the process, the key steps include (i) choosing appropriate reference applications (ii) distinguishing the codebase by clustering the files, (iii) reviewing the quality of the clusters, (iv) analysing the cluster by tailored CCD, and (v) transforming of the code clones, depending on the code clone type, to extract a DSL and the corresponding generator templates.

2019

D.Priefer, P.Kneisel, W.Rost, D.Strüber, G.Taentzer
Applying MDD in the Content Management System Domain: Scenarios and Empirical Assessment
IEEE / ACM 22nd International Conference on Model Driven Engineering Languages and Systems (MODELS), 2019, Munich, Germany, in press.
Abstract:
In this paper, we present a mixed-method empirical investigation of applying MDD in the CMS domain, based on an interview suite, a controlled experiment, and a field experiment. We consider three scenarios of developing new (both independent and dependent) CMS extensions and of migrating existing ones to a new major platform version. The experienced developers in our interviews acknowledge the relevance of these scenarios and report on experiences that render them suitable candidates for a successful application of MDD. We found a particularly high relevance of the migration scenario. Our experiments largely confirm the potentials and limits of MDD as identified for other domains. In particular, we found a productivity increase up to factor 17 during the development of CMS extensions. Furthermore, our observations highlight the importance of good tooling that seamlessly integrates with already used tool environments and processes.

Frank Kammer, Johannes Meintrup, Andrej Sajenko
Space-Efficient Vertex Separator for Treewidth
https://arxiv.org/abs/1907.00676
Abstract:
Practical applications that use treewidth algorithms have graphs with treewidth k = O(n^1/3). Given such n-vertex graphs we present a word-RAM algorithm to compute vertex separators using only O(n) bits of working memory. As an application of our algorithm, we show an O(1)-approximation algorithm for tree decomposition. Our algorithm computes a tree decomposition in c^k n(log^* n) log log n time using O(n) bits for some constant c. 

We finally show that our tree-decomposition algorithm can be used to solve several monadic second-order problems using O(n) bits as long as the treewidth of the graph is smaller than c' log n for some constant 0 < c' < 1.

Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, Jakob T. Spooner
Two Moves per Time Step Make a Difference
ICALP19
Abstract:
A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n1.75) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Ω(n2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.

2018

Frank Kammer, Andrej Sajenko
Simple 2^f-Color Choice Dictionaries
ISAAC18
Abstract:
A c-color choice dictionary of size n \in IN is a fundamental data structure in the development of space-efficient algorithms that stores the colors of n elements and that supports operations to get and change the color of an element as well as an operation choice that returns an arbitrary element of that color. For an integer f > 0 and a constant c = 2^f , we present a word-RAM algorithm for a c-color choice dictionary of size n that supports all operations above in constant time and uses only nf + 1 bits, which is optimal if all operations have to run in o(n/w) time where w is the word size.
In addition, we extend our choice dictionary by an operation union without using more space.

Frank Kammer, Dieter Kratsch, Moritz Laudahn
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
Algorithmica Seiten 1-25.
Abstract:
We present space-efficient algorithms for computing cut vertices in a given graph with n vertices and m edges in linear time using O(n + min{m, n log log n}) bits. With the same time and using O(n + m) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in O(n log log n) time using O(n) bits.

Frank Kammer, Andrej Sajenko
Extra Space during Initialization of Succinct DS and of Dynamical Initializable Arrays
MFCS18 | https://arxiv.org/abs/1803.09675
Abstract:
Many succinct data structures on the word RAM require precomputed tables to start operating. Usually, the tables can be constructed in sublinear time. In this time, most of a data structure is not initialized, i.e., there is plenty of unused space allocated for the data structure. We present a general framework to store temporarily extra buffers between the real data so that the data can be processed immediately, stored first in the buffers, and then moved into the real data structure after finishing the tables. As an application, we apply our framework to Dodis, Patrascu, and Thorup's data structure (STOC 2010) that emulates c-ary memory and to Farzan and Munro's succinct encoding of arbitrary graphs (TCS 2013). We also use our framework to present an in-place dynamical initializable array.

Frank Kammer, Andrej Sajenko
Linear-Time In-Place DFS and BFS in the Restore Model
https://arxiv.org/abs/1803.04282
Abstact:
We present an in-place depth first search (DFS) and an in- place breadth first search (BFS) that runs in the restore model in linear time. To obtain our results we use properties of the representation used to store the given graph and show several linear-time in-place graph transformations from one representation into another.

2017

Thomas Erlebach, Michael Hoffmann, Frank Kammer
On Temporal Graph Exploration
Abstract:
A temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. In the first part of the paper, we consider only temporal graphs that are connected at each step. For such temporal graphs with n nodes, we show that it is NP-hard to approximate TEXP with ratio O(n^1−ϵ) for any ϵ > 0. We also provide an explicit construction of temporal graphs that require Θ(n²) steps to be explored. We then consider TEXP under the assumption that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in O(n^1.5 k² log n) steps if the underlying graph has treewidth k and in O(n log³ n) steps if the underlying graph is a 2 × n grid. In the second part of the paper, we replace the connectedness assumption by a weaker assumption and show that m-edge temporal graphs with regularly present edges and with random edges can always be explored in O(m) steps and O(m log n) steps with high probability, respectively. We finally show that the latter result can be used to obtain a distributed algorithm for the gossiping problem.

Torben Hagerup, Frank Kammer
On-the-Fly Array Initialization in Less Space
Presentation at the ISAAC 2017. Presentation description
Abstract:
We show that for all given n,t,w in {1,2,...} with n<2^w, an array of n entries of w bits each can be represented on a word RAM with a word length of w bits in at most nw+ceil(n(t/(2 w))^t) bits of uninitialized memory to support constant-time initialization of the whole array and O(t)-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with nw+ceil(n/w^t) bits for arbitrary fixed t, to be compared with nw+Theta(n) bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support O(log n)-time access with just nw+1 bits, which is optimal for arbitrary access times if the initialization executes fewer than n steps.

Dennis Priefer, Peter Kneisel, Daniel Strüber
Iterative Model-Driven Development of Software Extensions for Web Content Management Systems
In European Conference on Modelling Foundations and Applications (ECMFA), pp. 142-157, 2017.
Abstract: 
Dynamic web applications powered by Web Content Management Systems (WCMSs) such as Joomla, WordPress, or Drupal dominate today’s web. A main advantage of WCMSs is their functional extensibility by standardized WCMS extensions. However, the development and evolution of these extensions are challenging tasks. Due to dependencies to the core platform and other WCMS extensions, the code structure of an extension includes a large defect potential. Mistakes usually lead to website crashes and are hard to find, especially for inexperienced developers. In this work, we define a model-driven development (MDD) process and apply it during the development of software extensions for the WCMS Joomla. To address two separate scenarios, involving the development of independent and dependent WCMS extensions, we use an MDD infrastructure, comprising a domain-specific language, a code editor, and reverse engineering facilities. In addition, we provide evidence indicating that our model-driven approach is useful to generate extensions with consistent interdependencies, demonstrating that the main issues of extension development in the WCMS domain can be addressed using a model-driven approach. By applying the MDD infrastructure on actual projects, we additionally present the lessons learned.

Dennis Priefer
Augmentation of existing Extensions using a Low-Code Platform
Presentation at the international Joomla! Conference J and Beyond, Kraków, Poland. 
Abstract: 
The creation of new Joomla extensions can be a time-consuming process for extension developers. This includes both scenarios, the development of new independent extensions (e.g. components) as well as new dependant extensions using existing ones (e.g modules). In our presentation, We will illustrate a model-driven process for both development scenarios using a low-code platform named JooMDD. JooMDD can be used within common IDEs and as platform-independent web application. The latter will be demonstrated within the talk, by means of the development scenario of augmenting an existing component by a new module.

2016

Dennis Priefer, Peter Kneisel, Gabriele Taentzer
A Model-Driven Process to Migrate Web Content Management System Extensions
In Web Engineering - Volume 9671 of the series Lecture Notes in Computer Science, pages 603-606. Springer International Publishing Switzerland, 2016. Poster at the 16th International Conference on Web Engineering, Lugano, Switzerland.
Abstract: 
Developing and maintaining software extensions for Web Content Management Systems (WCMSs) like Joomla, WordPress, or Drupal can be a difficult and time consuming process. This poster presents a model-driven process which addresses typical challenges during the migration of software extensions for WCMSs. We introduce JooMDD as a prototypical environment for the development and maintenance of Joomla extensions. JooMDD consists of a domain-specific modelling language for WCMS extensions, a reverse engineering tool to create models based on existing WCMS extensions, and a code generator for software extensions, which can be used to enrich Joomla-based applications. The use of JooMDD within our research demonstrates the application of a model-driven migration process for WCMS extensions.

Dennis Priefer
JooMDD - Joomla Extension Creation for Everybody
Presentation at the Joomla!Dagen Nederlande, Zeist, Netherlands. Presentation Description
Description: 
It is no secret, that the creation and maintenance of Joomla extensions can be a time-consuming process, especially for developers with less knowledge of the platform itself. In my presentation, I will talk about an environment which allows developers to create Joomla extensions on a higher abstraction level. The environment can be used within PHPStorm, IntelliJ, and Eclipse. This in turn allows the integration into the usual development process of the most developers. Through the use of JooMDD, Joomla extension developers can achieve both, saving of time during development and increasing the quality of their extensions. In this context we created a modelling language and a code generator for Joomla extensions. The presentation will consist of an explanation of the approach, including advantages and possibilities for Joomla developers, as well as a live demo of the current state of the existing tools within the PHPStorm IDE.

Peter Kneisel
Planung an der Technischen Hochschule Mittelhessen.
"Untis" Salzburg Seminar, Salzburg, Österreich, invited presentation (in german) 
Abstract: 
Ressource planning in a distributed, complex, dynamic, sometimes even chaotic system - such as an university - is an challenging task. This task is mainly about structuring and integrating and deals with various technical systems. This presentation provides an overview over the systems and processes to deal with ressource planning and shows the concrete challenges. It additionally shows the process and  infrastructure, that has been developped and the requirement on planning systems to deal with these tasks in future.
It provides a good motivation for the modelling and software engineering activities in our working group.

Dennis Priefer, Peter Kneisel, Gabriele Taentzer
JooMDD: A Model-Driven Development Environment for Web Content Management System Extensions
In Proceedings of the 38th ACM/IEEE International Conference on Software Engineering, Austin, TX, USA, pages 633-636. ACM, New York, 2016
Abstract:
Developing software extensions for Web Content Management Systems (WCMSs) like Joomla, WordPress, or Drupal can be a difficult and time consuming process. In this demo we present JooMDD, an environment for model-driven development of software extensions for the WCMS Joomla. JooMDD allows the rapid development of standardised software extensions requiring reduced technological knowledge of Joomla. This implies that even inexperienced developers are able to create their own functional WCMS extensions. This demonstrates that a model-driven approach is suitable for the domain of WCMSs. A supporting video illustrating the main features and a demonstration of JooMDD can be found at: https://youtu. be/Uy_WBIjPldI.

2015

Dennis Priefer
JooMDD - Model-driven Development Environment for Joomla Extensions
Presentation at the international Joomla! Conference J and Beyond, Prague, Czech Republic. Video: https://youtu.be/J-Qukj6Kyg8
Abstract: 
The creation and maintenance of Joomla extensions can be a time-consuming process, which is often done by fluctuating developer teams. In my presentation, I will talk about a plug-in infrastructure for the Eclipse IDE, which allows developers to create Joomla extensions on an higher abstraction level. Through the use of this infrastructure, Joomla developers can achieve both, saving of time during development and increasing the quality of their extensions. In this context we created a modelling language and a code generator for Joomla extensions. Due to the fact that our infrastructure is a part of an IDE, Joomla developers can easily integrate it into their common development process. The presentation will consist of an explanation of the approach, including advantages and possibilities for Joomla developers, as well as a live demo of the current state of the existing tools.

2014

Dennis Priefer
Model-Driven Development of Content Management Systems based on Joomla
In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering, Västerås, Sweden, pages 911-914. ACM, New York, 2014.
Abstract:
Today’s web consists of dynamic web sites with a wide range of functionality, whereby most of the sites are based on Content Management Systems (CMS). CMSs became a de facto standard as basic frameworks for web applications, because they provide lots of existing features and a high usability. Even though typical CMSs come along with lots of core functions, the most of them are extensible through different extension types. Through these extensions CMS-based applications become fully adequate web applications. One of the most popular CMSs is Joomla, which is extensible through external functionality. During the development and maintenance of both external functionality and concrete Joomla-based sites, some obstacles occur. One of the most substantial obstacle occurs when a new version of the core CMS platform is released. A further migration process is always an extremely time-consuming process. Through the use of model-driven development (MDD) a lot of the invested development and maintenance effort can be reduced, especially when new platform versions appear frequently. This paper proposes an MDD approach to the Joomla CMS, and contains several use cases for both forward engineering and reverse engineering of Joomla extensions and Joomla-based web sites with concrete data which shall be used for a faster and simpler migration process.