Scienze matematiche, fisiche ed informatiche
http://elea.unisa.it/xmlui/handle/10556/826
2024-03-29T15:50:18ZGeometries associated with Von Dick Groups
http://elea.unisa.it/xmlui/handle/10556/2016
Geometries associated with Von Dick Groups
Stypa, Monika Ewa
This thesis contains a theoretical result in the eld of group actions on combinatorial structures, which is an important
area of research, bringing forth some thirty publications per year. Besides its applications, mostly found in cryptography
and image{recognition, such a discipline casts interesting bridges between the abstract theory of groups and more \visible"
objects, like the graphs. On the theoretical side, in the last three decades, the deepest contributions have been given,
among others, by M. D. E. Conder and his collaborators (see, e.g., [1] and references therein).
But what is the advantage of associating a geometric structure to a given group G? If G is of a \tamed" kind, i.e.,
it is either nite, Abelian, solvable, or equipped with some additional structure like, e.g., that of a Lie group, then there
are no advantages at all. In this thesis I will rather consider a class of groups, which is rather \wild", in the sense that
it comprises in nite, discrete and solvable groups and it was allegedly introduced by W. von Dyck at the turn of the
eighteenth century [10], and I will study some natural combinatorial geometric structures they act upon. My purpose is
to show that even extremely elementary structures can play a nontrivial role in the understanding of such groups.
I would like to stress, from the very beginning, that all the theoretical reasonings in this thesis are carried out in
terms of abstract groups. By an \abstract group" I mean a group without any additional structure whatsoever which is
not, a priori, realised as the transformation groups of some other mathematical entity. Such kind of groups are classically
introduced through a presentation. In symbols, a presentation looks like G = hS j Ri, and it means that G can be obtained
from the free group over the set S, i.e., the \largest"|so to speak|group admitting S as a set of generators, by factoring
out the elements belonging to the normal subgroup generated by R.
In spite of its rather formal and abstract
avour, the notion of a presentation is heavy with geometrical implications.
At the end of the eighteen century, A. Cayley introduced a combinatorial geometric structure, which nowadays is known
to be a coloured graph, associated, in a functorial way, to a given presentation G = hS j Ri of the group G. Such a graph,
which I will denote by (G; S), goes under the name of Cayley graph, and it has the remarkable property of being regular
(or homogeneous) with respect to G, i.e., the original group G act freely and transitively on it. It is a true marvel that
such a rudimentary construction can be put at the foundations of some straightforward yet far{reaching observations:
the so{called word problem (a still open problem) for a group G = hS j Ri is equivalent to the constructability
(i.e., the possibility of de ning it through a recursive function) of (G; S) [4];
if (G; S) can be embedded into a surface, then it makes sense to attach to the group G a typical geometric
property, namely, that of the genus [11];
the geometric properties of the surface (e.g., its compactness) (G; S) is embedded into may be used to check
the niteness of G [9, 2].
In this thesis, I basically discovered a link|a duality, to be more precise|between such a classical construction as the
Cayley graph and another interesting (though perhaps less known) way of linking a graph to a group, which is the incidence
graph [5] associated with the so{called coset geometry.
Its main result stems from a subtle yet unfairly forgotten theorem, formulated by G. Sabidussi in 1958, establishing
that (G; S) is the unique, up to isomorphisms, edge{coloured graph on which the original group G acts vertex{transitively
[7]. So, since the incidence graph of the coset geometry of G carries a natural edge{transitive G{action, and it is naturally
vertex{coloured, I was led to suspect that the incidence graph of the coset geometry is, in fact, the same thing as the
Cayley graph, provided that|roughly speaking|\vertices are replaced with edges". This thesis contains a rigorous proof
of such a result, complemented by all the necessary preliminaries, and some (envisaged) applications and perspectives.
The role played herewith by the von Dyck group D(n; n; n) is that of a tool to better explain such a vertex{to{edge
duality. Indeed, for n > 3 the von Dyck groups D(n; n; n) belong to a class of (in nite, discrete and not solvable) groups
known as Fuchsian groups, which are the discrete and nitely generated subgroup of the three{dimensional Lie group
PSL (2;R) of the isometries of the hyperbolic plane H. The Fuchsian groups naturally act on a tangible geometric entity
such as H. Moreover, D(n; n; n) is generated by the orientation{preserving transformations of a regular{triangular tessel-
lation Tn, which, once again, is a rather elementary structure of combinatorial character, being essentially a triangulation
by regular triangles.
ABSTRACT (EN) 3
The vertex{to{edge duality, which is a quite general result, admits a nice transparent geometric formulation: in the
case of von Dyck groups D(n; n; n) both the Cayley graph and the incidence graph of the coset geometry of D(n; n; n)
are inscribed into Tn. More precisely, the latter is the 1{skeleton of Tn, while the former is the 1{skeleton of the so{called
derived tessellation of Tn. In other words, the groups of von Dyck allow to visualise the vertex{to{edge duality in terms
of the most elementary geometric shapes: triangles on a surface.
Let me describe some of the applications and perspectives of the vertex{to{edge duality.
First of all, it makes it evident that the Cayley graph of the von Dyck group is a planar one, which, to my best
knowledge, has never been observed before, though a very similar result can be found in [9].
Then, the vertex{to{edge duality immediately allows to recast, in a transparent geometric way, a result proved in
1983 by T.W. Tucker [8], concerning the genus of the factors of D(n; n; n). I must mention that among the factors of
D(n; n; n) there are the famous free Burnisde groups with two generators B(2; n), whose importance also pushed me to
look for a recursive way to enumerate the elements of D(n; n; n).
This is probably the most important consequence of the vertex{to{edge duality I have managed to discover so far:
it allows to recursively enumerate the edges (called cliques, as in the theory of coloured graphs) of the incidence graph
of the coset geometry and, hence, the elements of D(n; n; n). I dubbed this procedure \cliques enumeration algorithm",
and there are indications that it may be useful for attacking the celebrated Burnside problem in the still unsolved cases
with two generators. Indeed, in view of the natural surjection between D(n; n; n) and B(2; n), which makes it possible to
associate to the latter some of the geometric features of the former, the niteness of B(2; n) can be a consequence of the
niteness of a suitable \quotient tessellation" of Tn, with respect to the kernel of the projection D(n; n; n) ! B(2; n).
Incidentally, this solves the word problem for the Burnisde groups with two generators.
I must stress that, in one form or another, any existing algorithm to check the niteness of B(2; n) implements
a mechanism to enumerate words, and, due to the presence of relations, the lexicographic way is not necessarily the
cheapest one (see [3] and references therein). On the other hand, the cliques enumeration algorithm I proposed allows
to \avoid" relations and to produce exactly once each element of the group, so that it may be computationally more
advantageous. I have written the cliques enumeration algorithm by using the Wolfram MathematicaTMcomputer algebra
software, but, due to the unavoidable computational complexity, I have managed to test it only for n 4. Nevertheless, it
seems that, especially in comparison with the existing techniques, the cliques enumeration algorithm has the \aesthetic"
merit of providing an uni ed approach to the problem of the niteness of B(2; n), for arbitrary n, in sharp contrast with
the methods applied so far to each particular situation. [edited by author]
2013 - 2014
2015-05-04T00:00:00ZUsing Structural and Semantic Information to Support Software Refactoring
http://elea.unisa.it/xmlui/handle/10556/2022
Using Structural and Semantic Information to Support Software Refactoring
Bavota, Gabriele
In the software life cycle the internal structure of the system undergoes
continuous modifications. These changes push away the source code from its
original design, often reducing its quality. In such cases refactoring techniques
can be applied to improve the design quality of the system.
Approaches existing in literature mainly exploit structural relationships present in
the source code, e.g., method calls, to support the software engineer in
identifying refactoring solutions. However, also semantic information is
embedded in the source code by the developers, e.g., the terms used in the
comments.
This research investigates about the usefulness of combining structural and
semantic information to support software refactoring. In particular, a framework
of approaches supporting different refactoring operations, i.e., Extract Class,
Move Method, Extract Package, and Move Class, is presented.
All the approaches have been empirically evaluated. Particular attention has
been devoted to evaluations conducted with software developers, to
understand if the refactoring operations suggested by the proposed
approaches are meaningful from their point of view. [edited by Author]
2011 - 2012
2015-07-20T00:00:00ZSearch-based approaches for software development effort estimation
http://elea.unisa.it/xmlui/handle/10556/1969
Search-based approaches for software development effort estimation
Sarro, Federica
Effort estimation is a critical activity for planning and monitoring software project development and for delivering the product on time and within budget. Significant over or under-estimates expose a software project to several risks. As a matter of fact under-estimates could lead to addition of manpower to a late software project, making the project later (Brooks’s Law), or to the cancellation of activities, such as documentation and testing, negatively impacting on software quality and maintainability. Thus, the competitiveness of a software company heavily depends on the ability of its project managers to accurately predict in advance the effort required to develop software system. However, several challenges exists in making accurate estimates, e.g., the estimation is needed early in the software lifecycle, when few information about the project are available, or several factors can impact on project effort and these factor are usually specific for different production contexts.
Several techniques have been proposed in the literature to support project manager in estimating software project development effort.
In the last years the use of Search-Based (SB) approaches has been suggested to be employed as an effort estimation technique. These approaches include a variety of meta-heuristics, such as local search techniques (e.g., Hill Climbing, Tabu Search, Simulated Annealing) or Evolutionary Algorithms (e.g., Genetic Algorithms, Genetic Programming).
The idea underlying the use of such techniques is based on the reformulation of software engineering problems as search or optimization problems whose goal is to find the most appropriate solutions which conform to some adequacy criteria (i.e., problem goals). In particular, the use of SB approaches in the context of effort estimation is twofold: they can be exploited to build effort estimation models or to enhance the use of existing effort estimation techniques. The usage reported in the literature of SB approaches for effort estimation have provided promising results that encourage further investigations. However, they can be considered preliminary studies. As a matter of fact, the capabilities of these approaches were not fully exploited, either the employed empirical analyses did not consider the more recent recommendations on how to carry out this kind of empirical assessment in the effort estimation and in the SBSE contexts. The main aim of the PhD dissertation is to provide an insight on the use of SB
techniques for the effort estimation trying to highlight strengths and weaknesses of these approaches for both the uses above mentioned. [edited by Author]
2011 - 2012
2015-06-19T00:00:00ZVirtual worlds for education: methodology, interaction and evaluation
http://elea.unisa.it/xmlui/handle/10556/1433
Virtual worlds for education: methodology, interaction and evaluation
Cuccurullo, Stefania
When students arrive in the classroom they expect to be involved in immersive, fun and challenging learning experiences. There is a high risk that they become quickly bored by the traditional instructional methods. The technological evolution offers a great variety of sophisticated interactive devices and applications that can be combined with innovative learning approaches to enhance study efficiency during the learning process.
3D immersive multi-user Virtual Worlds (VWs) are increasingly becoming popular and accessible to wide public due to the advances in computational power graphics and network bandwidth also connected with reduced costs. As a consequence, it is possible to offer more engaging user experiences. This is particularly true in the learning sector, where an increasing interest is worldwide rising towards three-dimensional (3D) VWs and new interaction modalities to which young digital native people are accustomed to. Researches on the educational value of VWs have revealed their potential as learning platforms. However, further studies are always needed in order to assess their effectiveness, satisfactorily and social engagement not only in the general didactic use of the environment, but also for each specific learning subjects, activities and modality. The main challenge is to well exploit VW features and determine learning approaches and interaction modalities in which the didactic actions present added value with respect to traditional education. Indeed, educational VW activities are evolving from the early ones based only on information displaying towards simulated laboratories and new interaction modalities.
The main objective of this thesis is to propose new learning methodologies in Virtual Worlds, also experimenting new interaction modalities and evaluating the effectiveness of the support provided.
To this aim we first investigate how effectively a 3D city-building game supports the learning of the waste disposal practice and promotes behavior change. The game is one of the results of a research project funded by Regione Campania and is addressed to primary school children. A deep analysis of the didactic methodologies
adopted worldwide has been performed to propose a reputation-based learning approach based on collaborative, competitive and individual activities. Also, the effectiveness of the proposed approach has been evaluated.
The didactic opportunities offered by VWs when considering new interaction approaches are also investigated. Indeed, if for the last four decades keyboard and mouse have been the primary means for interacting with computers, recently, the availability of greater processing power, wider memories, cameras, and sensors make it possible to introduce new interaction modalities in commonly used software. Gestural interfaces offer new interaction modalities that the primary school children known well and may result accepted also for higher students. To assess the potentiality of this new interaction approach during learning activities we selected Geography as subject, since there is a decreasing interest of the students towards this topic. To this aim the GeoFly system supporting the Geography learning based on a Virtual Globe and on the interaction modalities offered by Microsoft Kinect has been developed. GeoFly is designed for elementary school level Geography students. It enables the exploration of the World by flying, adopting the bird (or aeroplane) metaphor. It also enables the teacher to create learning trips by associating to specific places images, text and videos, to develop learning activities concerning geographically situated scenarios. The proposed approach has been evaluated through a controlled experiment aiming at assessing the effect of the adoption of GeoFly on both the students' attitude towards learning Geography and also on their knowledge. [edited by author]
2011 - 2012
2014-05-20T00:00:00Z