Graphs and automata: theoretical aspects and applications to words and images
Research focus
The Peer review has evaluated this group as Average
We focused on graph and automaton theory to cope with novel applications of these theoretic concepts in fields emerging from applicative behaviours like image processing, linguistics, mathematics, etc. To deal with these problems we widely used graph automorphisms and isomorphisms (R5,O7). The main directions of our research are - Reconstruction problem of graphs (B1). This is connected with the celebrated conjecture of Kelly-Ulam (R8), and to relative generalizations, e.g. local and global analysis of pathcongruences (R7, R15, O2). - Geometric tomography. The notion of X-rays in a graph arises as application of reconstruction problems and immediately brings to geometric tomography, topic where results in continuous and in discrete spaces are obtained, using both numerical and algebraic-geometric methods (R4, R9, R12, R13, R14, O1). - Language theory. Various applicative domains suggested new formalisms in language theory, like tile rewriting grammars (R11) for dealing with image processing and associative description of languages (O3) to face criticisms against Chomsky’s hierarchy raised from neuro-linguistics . - Combinatoric on words. A longstanding open problem in finite automaton theory is Cerny’s conjecture. From its generalizations the concepts of collapsing and synchronizing words naturally arise. Characterization, decision and complexity problems on these words are considered in (R1, C1, C5, C6). - Decisional and algorithmic problems in semigroup theory. The main problem in combinatorial theory of inverse semigroups is the word problem. We considered this problem for several classes of inverse semigroups (R6, O5, O6) using Schützenberger graphs and, by their automorphism groups, we obtained structural properties of families of inverse semigroups (O7) using typical arguments from topology, like fundamental group. We also considered how to compact the description of several classes of finite semigroups (R2, R10) looking for a good trade-off between number of generators and number of needed products. Moreover we occasionally deal also with different problems arising from discussions and contacts with people of Computer Science Department concerning with cryptography (C2, C4), fuzzy logic (O4) and timed automata for modelling concrete behaviours (C3, R3).
Dipartimento di afferenza
Docenti afferenti
Full Professor
Alessandra Cherubini
Associate Professor
Raffaele Scapellato
Assistant Professor
Paolo Dulio