Research Activities

Research Interests

Formal languages:

• Two-dimensional picture languages:
        Tiling sistems recognizability, regualr expressions, other models
        Determinism, non-determinism and ambiguity
        Unary case
        Two-dimensional picture codes
        Overlap-free picture sets
  
  
• String languages:
        Z-codes and z-submonoids
        Covering codes
        Unary alphabet automata
        Rational relations and multi-tape automata
  
  
• Binary trees:
        Reducibility
  

Publications :

• M. Madonia  “Two-dimensional Codes” in M. Anselmo, G. Della Vedova, F. Manea and A. Pauly (Eds.): Proc. Int. Conference on Computability in Europe (CiE'20), Lecture Notes in Computer Science, Vol. 12098. Springer (2020).

• M. Anselmo, D. Giammarresi, M. Madonia  “Characterization and Measure of Infinite Two-dimensional Strong Prex Codes” Information and Computation  Vol. 274 (2020).

• M. Anselmo, D. Giammarresi, M. Madonia  “A common framework to recognize two-dimensional languages” Fundamenta Informaticae  Vol. 171,  pp. 1-17 (2020).

• M. Anselmo, D. Giammarresi, M. Madonia  “Sets of Pictures Avoiding Overlaps” International Journal of Foundations of Computer Science Vol. 60 (6-7),  pp. 875-898 (2019).

• M. Anselmo, M. Madonia, C. Selmi  “Toroidal Codes and Conjugate Pictures” in C. Martín-Vide, A. Okhotin, D. Shapira (Eds.): Proc. Int. Language and Automata Theory and Applications (LATA'19), Lecture Notes in Computer Science, Vol. 11417. Springer (2019).

• M. Anselmo, D. Giammarresi, M. Madonia  “Full sets of pictures to encode pictures” Theoretical Computer Science Vol. 777,  pp. 55-68 (2019). http://dx.doi.org/10.1016/j.tcs.2018.10.031

• M. Anselmo, D. Giammarresi, M. Madonia  “Encoding Pictures with Maximal Codes of Pictures” in A. Min Tjoa, L. bellatreche, J. van Leewen and J. Wiedermann (Eds.): Proc. Int. Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'18), Lecture Notes in Computer Science, Vol. 10706. Springer (2018).

• M. Anselmo, D. Giammarresi, M. Madonia  “Avoiding Overlaps in Pictures” in G. Pighizzini and C. Campeanu (Eds.): Proc. Int. Descriptional Complexity of Formal Systems  (DCFS'17), Lecture Notes in Computer Science, Vol. 10316. Springer (2017).

• M. Anselmo, D. Giammarresi, M. Madonia  “Infinite Two-dimensional Strong Prefix Codes:  Characterization and Properties” in A. Dennunzio, E. Formenti, L.Manzoni and A. E. Porreca (Eds.): Proc. Int. AUTOMATA'17, Lecture Notes in Computer Science, Vol. 10248. Springer (2017).

• M. Anselmo, D. Giammarresi, M. Madonia  “Non-Expandable Non-Overlapping sets of pictures” Theoretical Computer Science Vol. 657 (A),  pp. 127-136 (2017).

• M. Anselmo, M. Madonia  “Two-dimensional Comma-free and Cylindric Codes” Theoretical Computer Science Vol. 658 (A),  pp. 4-17 (2017). 

• M. Anselmo, D. Giammarresi, M. Madonia  “Picture Codes and Deciphering Delay” Information and Computation Vol. 253,  pp. 358-370 (2017).  http://dx.doi.org/10.1016/j.ic.2016.06.003

• M. Anselmo, D. Giammarresi, M. Madonia  “Picture Codes and Deciphering Delay” Information and Computation Vol. 253,  pp. 358-370 (2017). 

• M. Anselmo, D. Giammarresi, M. Madonia  “Structure and properties of strong prefix codes of pictures” Mathematical Structures in Computer Science Vol. 27 (2),  pp. 123-142 (2017). 

• M. Anselmo, D. Giammarresi, M. Madonia  “Unbordered Pictures: Properties and Construction” in A. Maletti (Ed.): Proc. Int. Conference on Algebraic Informatics (CAI’15), Lecture Notes in Computer Science, Vol. 9270,  pp. 45-57. Springer (2015).

• M. Anselmo, D. Giammarresi, M. Madonia  “Structure and Measure of a Decidable Class of Two-dimensional Codes” in : Proc. Int. Conf. Language and Automata Theory and Applications, (LATA’15), Lecture Notes in Computer Science  Springer-Verlag (2015).

• M. Anselmo, D. Giammarresi, M. Madonia   “Prefix Picture Codes: a Decidable Class of Two-dimensional Codes” International Journal of Foundations of Computer Science Vol. 25, n.8,  pp. 1017-1032 (2014).

• M. Anselmo, D. Giammarresi, M. Madonia  “Picture Codes with Finite Deciphering Delay” in Adrian-Horia Dediu, Carlos Martín-Vide, José‐Luis Sierra, and Bianca Truthe (Eds.): Proc. Int. Conf. Language and Automata Theory and Applications, (LATA’14), Lecture Notes in Computer Science  Vol. 8370, pp. 88-100. Springer-Verlag (2014).

• M. Anselmo, D. Giammarresi, M. Madonia  “Strong Prefix Codes of Pictures” in T. Muntean, D. Poulakis, and R. Rolland (Eds.): Proc. Int. Conference on CAlgebraic Informatics (CAI’13), Lecture Notes in Computer Science,  Vol. 8080, pp. 47-59. Springer-Verlag, Berlin Heidelberg (2013).

• M. Anselmo, D. Giammarresi, M. Madonia  “Two-dimensional Prefix Codes of Pictures” in M.-P. Béal and O. Carton (Eds.): Proc. Int. Conf. Developments on Language Theory (DLT’13), Lecture Notes in Computer Science,  Vol. 7907, pp. 46-57. Springer, Heidelberg (2013).

• M. Anselmo, M. Madonia  “A Stronger Recognizability Condition for Two-dimensional Languages” Discrete Mathematics and Theoretical Computer Science, Vol. 15, n.2,  pp. 139-156 (2013).

• M. Anselmo, D. Giammarresi, M. Madonia  “Two-dimensional rational automata: a bridge unifying one- and  two-dimensional language theory” in Peter van Emde Boas et al. (Eds.): Proc. Int. Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM13), Lecture Notes in Computer Science,  Vol. 7741, pp. 133-145. Springer-Verlag, Berlin (2013).

• M. Madonia, G. Scollo  “Reducibility and Solvability of Some Classes of Kryuchkov Binary Tree Pairs” The Electronic Journal of Combinatorics, Vol. 18, n. 2 (2012).

• M. Anselmo, M. Madonia "Comparing Necessary Conditions for Recognizability of Two-dimensional Languages" in F. Winkler (Ed.) Procs. Int. Conference on Algebraic Informatics (CAI’11), Lecture Notes in Computer Science, Vol. 6742, pp. 84-96, Springer, Heidelberg (2011).

• M. Anselmo, D. Giammarresi, M. Madonia  “Classification of String Languages via Tiling Recognizable Picture Languages” in A. Dediu, S. Inenaga, C. Martín-Vide (Eds.): Procs. LATA 2011, Lecture Notes in Computer Science,  Vol. 6638, pp. 105-116, Springer, Heidelberg (2011).

• M. Anselmo, M. Madonia "Some results on the structure of unary unambiguous automata"  Advances in Applied  Mathematics  Vol. 47, n. 1, pp. 88–101 (2011).

• M. Anselmo, M. Madonia "Classes of Two-dimensional Languages and Recognizability Conditions"  RAIRO-ITA Theoretical Informatics and Applications Vol. 44, n. 4, pp. 471–488 (2010).

• M. Anselmo, D. Giammarresi, M. Madonia   “Deterministic and unambiguous families within recognizable two-dimensional languages”   Fundamenta  Informaticae, Vol. 98, n. 2-3, pp. 143–166 (2010).

• M. Anselmo, M. Madonia "A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-dimensional Languages" in S. Bozapalidis and G. Rahonis (Eds.):  Proc. Int. Conference on Algebraic Informatics (CAI’09), Lecture Notes in Computer Science,  Vol. 5725, pp. 147–159, Springer-Verlag Berlin Heidelberg (2009).

• M. Anselmo, D. Giammarresi, M. Madonia  “A Computational Model for Tiling Recognizable Two-dimensional Languages” Theoretical Computer Science, Vol. 410, n.37,  pp. 3520-3529 Elsevier (2009).

• M. Anselmo, M. Madonia  “Deterministic and Unambiguous Two-dimensional Languages over One-letter Alphabet” Theoretical Computer Science, Vol. 410, n. 16, pp. 1477-1485 Elsevier (2009).

• M. Anselmo, N. Jonoska, M. Madonia "Framed versus Unframed Two-Dimensional Recognizable Languages" in M. Nielsen et al. (Eds.): SOFSEM 2009, Lecture Notes in Computer Science,  Vol. 5404, pp. 79–92, 2009. Springer-Verlag Berlin Heidelberg 2009.

• M. Anselmo, D. Giammarresi, M. Madonia  “Tiling automaton: a Computational Model for Recognizable Two-dimensional Languages” in J. Holub and J. Zdarek (Eds.): Proc. Int. Conference on Implementation and Application of Automata (CIAA’07), Lecture Notes in Computer Science,  Vol 4783, pp. 290-302, 2007. Springer-Verlag, Berlin (2007).

• M. Anselmo, M. Madonia  “Deterministic Two-dimensional Languages over One-letter Alphabet” in S. Bozapalidis and G. Rahonis (Eds.): Proc. Int. Conference on Algebraic Informatics (CAI’07), Lecture Notes in Computer Science,  Vol 4728, pp. 147-159, 2007. Springer-Verlag Berlin, (2007).

• M. Anselmo, D. Giammarresi, M. Madonia  “From determinism to non-determinism in recognizable two-dimensional languages” in T. Harju, J. Karhumaki, and A. Lepisto (Eds): Proc. Int. Conf. Developments on Language Theory (DLT’07), Lecture Notes in Computer Science,  Vol 4588, pp. 36-47, 2007, Springer-Verlag, Berlin 2007.

• M. Anselmo, D. Giammarresi, M. Madonia, A. Restivo  “Unambiguous recognizable two-dimensional languages”  RAIRO-Theoretical Informatics and Applications, Vol. 40, n. 2, pp. 277-293 EDP-Sciences (2006).

• M. Anselmo, M. Madonia  “Simulating two-dimensional recognizability by pushdown and queue automata” in J. Farré, I. Litovsky, Igor and S. Schmitz (Eds.):  Proc. Int. Conference on Implementation and Application of Automata (CIAA’05), Lecture Notes in Computer Science,  Vol 3845, pp. 43-53 Springer Verlag, Berlin  (2006).

• M. Anselmo, D. Giammarresi, M. Madonia  “New operations and regular expressions for two-dimensional languages over one-letter alphabet”  Theoretical Computer Science, Vol. 340, n. 2, pp. 408-431 Elsevier (2005).

• M. Anselmo, M. Madonia  “A Language-Theoretic approach to coverings problems” Journal of Automata Languages and Combinatorics Vol. 10, n. 1, pp. 3-24 Otto-von-Guericke-Universität Magdeburg (2005).

• M. Anselmo, D. Giammarresi, M. Madonia  “Regular expressions for two-dimensional languages over one-letter alphabet” in C.S. Calude, E. Calude and M. J. Dinnen (Eds.) Proc. Int. Conf. Developments on Language Theory (DLT’04), Lecture Notes in Computer Science,  Vol 3340, pp. 63-75, Springer Verlag, Berlin (2004).

• M. Anselmo, M. Madonia  “Covering problems from a formal language point of view” in Z. Ésik and Z. Fülöp (Eds): Proc. Int. Conf. Developments on Language Theory (DLT’03), Lecture Notes in Computer Science, Vol 2710 pp. 122-133, Springer Verlag, Berlin (2003).

• M. Madonia, T. Sportelli, S. Salemi  “Covering submonoids and covering codes” Journal of Automata Languages and Combinatorics Vol. 4,  n. 4, pp. 333-350 Otto-von-Guericke-Universität Magdeburg (1999).

• M. Madonia, S. Varricchio  “Some decisional problems on rational relations” Theoretical Computer Science, Vol. 180, pp. 1-15 Elsevier  (1997).

• M. Madonia, S. Varricchio  “Iterative tapes and multitape automata” in H. Kirchner Ed. : Trees in Algebra and programming Proc. Int. CAAP’96 Conference, Lecture Notes in Computer Science, Vol 1059, pp. 17-29, Springer Verlag, Berlin (1996).

• M. Madonia, S. Salemi, T. Sportelli  “A generalization of Sardinas-Patterson algorithm to z-codes” Theoretical Computer Science, Vol. 108, n. 2, pp. 251-270 Elsevier (1993).

• M. Madonia, S. Salemi, T. Sportelli  “On z-submonoids and z-codes” RAIRO Informatique Théorique et Applications,  Vol. 25, n. 4, pp. 305-322 EDP-Sciences (1991).