Beatrice Palano
She was born in Milan on July 23, 1972.
Email: palano@dsi.unimi.it

Since December 2002 she is an assistant professor at the Computer Science Departement of University of Milan.

In 2002 she got a temporary research position on the subject "Automi quantistici: possibilità e limiti alla potenza di calcolo e applicazioni" at the Computer Science Department of University of Milan, supervised by Prof. A. Bertoni.

In 2002, she received a PhD in Computer Science with excellent, with a thesis having the title: "Synthesis of unary quantum automata from periodic events".

From 1998 to 2002, she attended the course of "XIV ciclo - Dottorato di Ricerca in Informatica" at the Computer Science Department of the University of Turin.

In 1998, she received a MS degree in Computer Science cum laude at the University of Milan, with a thesis having the title: "Riconoscimento di linguaggi con circuiti neurali di profondità costante".
 



Scientific Activity

The research activity deals with the following topics:
- Descriptional complexity of formal systems. Study of the succinctness of different type of automata and grammars for formal languages.
- Quantum computing. Study of the computational and descriptional power of different models of quantum automata.
- Descriptive complexity. Study of the expressive power of fragments of first order logic for classes of formal languages and their implication on parallel algorithms.
- Context free grammars, Dyck and XML languages. Study of formal properties of this family of languages and their representation by rewriting systems.
- Discrete algorithms. Study of optimization problems on combinatorial structures.
- Parallel complexity. Study of efficient parallel algorithms on different computational models (boolean and threshold circuits, iterative array).

Publications on Journal

  1. Z. Bednárová, V. Geffert, C. Mereghetti and B. Palano. Boolean language operations on nondeterministic automata with a pushdown of constant height. In Journal of Computer and System Science, 2017. Accepted. [.pdf]

  2. M.P. Bianchi, C. Mereghetti and B. Palano. Quantum finite automata: Advances on Bertoni's ideas. In Theoretical Computer Science, 39--53, vol. 664, 2017. [.pdf]

  3. M.P. Bianchi, C. Mereghetti and B. Palano. On the power of one-way finite automata with quantum and classical states. In International Journal of Foundations of Computer Science, 895--912, vol. 26, 2015. [.pdf]

  4. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano and M. Wendlandt. Deterministic input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties. In Theoretical Computer Science, 58--71, vol. 578, 2015.[.pdf]

  5. M.P. Bianchi, C. Mereghetti and B. Palano. Size Lower Bounds for Quantum Automata. In Theoretical Computer Science, 102--115, vol. 551, 2014.[.pdf]

  6. Z. Bednárová, V. Geffert, C. Mereghetti and B. Palano. Removing nondeterminism in constant height pushdown automata. In Information and Computation, 257--267, vol. 237, 2014. [.pdf]

  7. M. P. Bianchi, C. Mereghetti, B. Palano, G. Pighizzini, M. Holzer and S. Jakobi. On Inverse Operations and Their Descriptional Complexity. In Journal of Automata, Languages and Combinatorics, 61--81 , vol. 17, 2012. [.pdf]

  8. A. Malcher, K. Meckel, C. Mereghetti and B. Palano. Descriptional Complexity of Pushdown Store Languages. In Journal of Automata, Languages and Combinatorics, 225--244 , vol. 17, 2012. [.pdf]

  9. Z. Bednárová, V. Geffert, C. Mereghetti and B. Palano. The size-cost of Boolean operations on constant height deterministic pushdown automata. In Theoretical Computer Science, 23--36, vol. 449, 2012. [.pdf]

  10. A. Malcher, C. Mereghetti and B. Palano. Descriptional complexity of two-way pushdown automata with restricted head reversals. In Theoretical Computer Science, 119--133, vol. 449, 2012. [.pdf]

  11. C. Choffrut, A. Malcher, C. Mereghetti and B. Palano. First-order logics: some characterizations and closure properties. In Acta Informatica, 225--248, vol. 49, 2012. [.pdf]

  12. M. P. Bianchi, C. Mereghetti, B. Palano and G. Pighizzini. On the Size of Unary Probabilistic and Nondeterministic Automata. In Fundamenta Informaticae, 119--135, vol. 112, 2011. [.pdf]

  13. M. P. Bianchi and B. Palano. Behaviours of unary quantum automata. In Fundamenta Informaticae, 1--15, vol. 104, 2010. [.pdf]

  14. A. Malcher, C. Mereghetti and  B. Palano. Sublinearly space bounded iterative arrays. In International Journal of Foundations of Computer Science, 843--858, vol. 21, 2010. [.pdf]

  15. A. Bertoni,  C. Mereghetti and B. Palano. Trace monoids with idempotent generators and measure-only quantum automata. In Natural Computing, 383--395, vol. 9, 2010. [.pdf]

  16. V. Geffert, C. Mereghetti and  B. Palano. More concise representation of regular languages by automata and regular expressions. In Information and Computation, 385--394, vol. 208, 2010. [.pdf]

  17. B. Palano. A regularity condition for context-free grammars. In International Journal of Foundations of Computer Science, pp. 845--857, vol. 19, 2008. [.pdf]

  18. C. Mereghetti and B. Palano. Quantum automata for some multiperiodic languages. In Theoretical Computer Science, pp. 177--186, vol. 387, 2007. [.pdf]

  19. C. Mereghetti and B. Palano. Quantum finite automata with control language. In Theoretical Informatics and Applications, pp. 315--332, vol. 40, 2006. [.pdf]

  20. A. Bertoni,  C. Mereghetti and B. Palano. Some formal tools for analyzing quantum automata. In Theoretical Computer Science, pp. 14--25, vol. 356, 2006. [.pdf]

  21. C. Mereghetti and B. Palano. The complexity of Minimum Difference Cover. In  Journal of Discrete Algorithms, pp. 239--254, vol. 4, 2006. [.pdf]

  22. A. Bertoni,  C. Mereghetti and B. Palano. Small size quantum automata recognizing some regular languages. In Theoretical Computer Science, pp. 394--407, vol. 340, 2005. [.pdf]

  23. A. Bertoni,  C. Mereghetti and B. Palano. Golomb Rulers and Difference Sets for Succinct Quantum Automata. In International Journal of Foundations of Computer Science, pp. 871--888, vol. 14,  2003. [.pdf]

  24. C. Mereghetti and B. Palano. On the Size of One-way Quantum Finite Automata with periodic behaviors. In Theoretical Informatics and Applications, pp. 277--291, vol. 36, 2002. [.pdf]

  25. C. Mereghetti and B. Palano. The Parallel Complexity of Deterministic and Probabilistic Automata. In Journal of Automata, Languages and Combinatorics, pp. 95--108. vol. 7, 2002. [.pdf]

  26. C. Mereghetti,  B. Palano and G. Pighizzini.  Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. In Theoretical Informatics and Applications, pp. 477--490, vol. 5, 2001. [.pdf]

  27. C. Mereghetti and B. Palano. Threshold circuits for iterated matrix product and powering. In Theoretical Informatics and Applications, pp. 39--46, vol. 34, 2000. [.pdf] 

Publications in Collection

  1. M.P. Bianchi, C. Mereghetti and B. Palano. Complexity of Promise Problems on Classical and Quantum Automata. In `` Computing with New Resources. Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday.'' C.S. Calude, R. Freivalds, K. Iwama (eds). Springer, Lecture Notes in Computer Science, vol. 8808, pp. 161--175, 2014. [.pdf] 

  2. C. Mereghetti and B. Palano. Quantum Automata and Periodic Events. In ``Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory. Scientific Applications of Language Methods.'' Carlos Martin-Vide (ed.). Imperial College Press, London, pp. 563--582, 2011. [.pdf] 

Publications on conference and workshop

  1. M.P. Bianchi, H.J. Boeckenhauer, T. Bruelisauer, D. Komm, B. Palano. Online Minimum Spanning Tree with Advice. In 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016). LNCS 9587, pp. 195--207. Harrachov, Czech Republic, 2016. [.pdf]

  2. M.P. Bianchi, C. Mereghetti, B. Palano. On the power of one-way finite automata with quantum and classical states. In 19th International Conference on Implementation of Automata and Applications (CIAA 2014). LNCS 8587, pp. 84--97. Giessen, Germany, 2014. [.pdf]
    Best Paper Award (Sheng Yu Award)

  3. V. Geffert, A. Malcher, K. Meckel, C. Mereghetti and B. Palano. A direct construction of finite automata for pushdown store languages. In 15th Workshop on Descriptional Complexity of Formal Systems (DCFS 2013), LNCS 8031, pp. 90--101. London, Ontario, Canada, 2013.[.pdf]

  4. S. Jakobi, K. Meckel, C. Mereghetti and B. Palano. Queue automata of constant length. In 15th Workshop on Descriptional Complexity of Formal Systems (DCFS 2013), LNCS 8031, pp. 124--135. London, Ontario, Canada, 2013.[.pdf]

  5. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano and M. Wendlandt. Input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties. In 18th International Conference on Implementation and Application of Automata (CIAA 2013), LNCS 7982, pp. 232--243. Halifax, Nova Scotia, Canada, 2013. [.pdf]

  6. M.P. Bianchi, C. Mereghetti and B. Palano. Size lower bounds for quantum automata. In 11th International Conference on Unconventional Computation and Natural Computation (UCNC 2013), LNCS 7956, pp. 19--30. Milano, Italy, 2013. [.pdf]

  7. Z. Bednárová, V. Geffert, C. Mereghetti and B. Palano. Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height. In 8th International Computer Science Symposium in Russia (CSR 2013), LNCS 7913, pp. 100--111. Ekaterinburg, Russia, 2013. [.pdf]

  8. A. Malcher, K. Meckel, C. Mereghetti and B. Palano. Descriptional complexity of pushdown store languages. In 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012), LNCS 7386, pp. 209--221. Braga, Portugal, 2012. [.pdf]

  9. Z. Bednárová, V. Geffert, C. Mereghetti and B. Palano. Removing nondeterminism in constant height pushdown automata. In 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012), LNCS 7386, pp. 76--88. Braga, Portugal, 2012. [.pdf]

  10. A. Malcher, K. Meckel, C. Mereghetti and B. Palano. On pushdown store languages. In 13th Italian Conference on Theoretical Computer Science 2012 (ICTCS 2012), pp. 168--171. Varese, Italy, 2012.[.pdf]

  11. A. Malcher, C. Mereghetti and B. Palano. Descriptional complexity of Two-Way Pushdown Automata With Restricted Head Reversals. In 13th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2011), LNCS 6808, pp. 248--260. Vicinity of Giessen, Germany, 2011. [.pdf]

  12. Z. Bednárová, V. Geffert, C. Mereghetti and B. Palano. The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata. In 13th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2011), LNCS 6808, pp. 80--92. Vicinity of Giessen, Germany, 2011. [.pdf]

  13. M. P. Bianchi, C. Mereghetti, B. Palano and  G. Pighizzini. Probabilistic vs. Nondeterministic Unary Automata. In Second International Workshop on Non-Classical Models of Automata and Applications (NCMA 2010), pp. 33--44. Jena, Germany, 2010. [.pdf]

  14. C. Choffrut, A. Malcher, C. Mereghetti and  B. Palano. On the Expressive Power of FO[+]. In 4th International Conference on Language and Automata Theory and Application (LATA 2010), LNCS 6031, pp. 190--201. Trier, Germany, 2010. [.pdf]

  15. A. Malcher, C. Mereghetti and  B. Palano. Logical description of Structured and XML languages. In 11th Italian Conference on Theoretical Computer Science (ICTCS 2009), pp. 161--167. Cremona, Italy, 2009. [.pdf]

  16. M. P. Bianchi, B. Palano. Events and Languages on Unary Quantum Automata. In First International Workshop on Non-Classical Models of Automata and Applications (NCMA 2009), pp. 61--75. Wroclaw, Poland, 2009. [.pdf]

  17. V. Geffert, C. Mereghetti and  B. Palano. Descriptional Complexity Issues Concerning Regular Languages. In 18th Workshop on Theorietag Automaten und Formale Sprachen, pp. 11-22. Giessen, Germany, 2008. [.pdf]

  18. V. Geffert, C. Mereghetti and  B. Palano. More concise representation of regular languages by automata and regular expressions. In 12th International Conference on Developments in Language Theory (DLT 2008), LNCS 5257, pp. 349--360. Kyoto, Japan, 2008. [.pdf]

  19. M. P. Bianchi, B. Palano. On leftmost #-rewriting systems. In 9th International Workshop on Descriptional Complexity of Formal Systems, pp. 61--72 (DCFS 2008). Charlottetown, Canada, 2008. [.pdf]

  20. A. Malcher, C. Mereghetti and  B. Palano. Sublinearly space bounded iterative arrays. In 12th International Conference on Automata and Formal Languages (AFL 2008), pp. 292--301. Balatonfüred, Hungary, 2008. [.pdf]

  21. A. Malcher, C. Mereghetti and  B. Palano. Recent results on iterative arrays with small space bounds. In EPSRC Workshop on Cellular Automata Theory and Applications (AUTOMATA 2008), pp. 222--226. Bristol, United Kingdom, 2008. [.pdf]

  22. B. Palano.  A regularity condition for context-free grammars. In 9th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2007), pp. 117--128. High Tatras, Slovakia, 2007. [.pdf]

  23. C. Mereghetti and  B. Palano.  Quantum automata for some multiperiodic languages. In 8th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2006), pp. 199--210. Las Cruces, New Mexico, USA, 2006. [.pdf]

  24. A. Bertoni, C. Choffrut and B. Palano.   Context-free grammars and XML languages. In 10th International Conference on Developments in Language Theory (DLT 2006), LNCS 4036, pp. 108--119. Santa Barbara, CA, USA, 2006. [.pdf]

  25. A. Bertoni, C. Mereghetti and B. Palano.  Some formal methods for analyzing quantum automata. In 7th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2005), pp. 1--14. Como, Italy, 2005. [.pdf]

  26.   A. Bertoni,  C. Mereghetti and B. Palano. Approximating  stochastic events by quantum automata. In ERATO Conference on Quantum Information Science, pp. 43--44. Kyoto, Japan, 2003.[.pdf]

  27. A. Bertoni, C. Mereghetti and B. Palano.  Lower bounds on the size of quantum automata accepting unary languages.  In 8th  Italian Conference on Theoretical Computer Science (ICTCS 2003), LNCS 2841, pp. 86--95. Bertinoro, Italy, 2003. [.pdf]

  28. A. Bertoni, C. Mereghetti and B. Palano.   Quantum Computing: 1-way quantum automata. In 7th International Conference on Developments in Language Theory (DLT 2003), LNCS 2710, pp. 1--20. Szeged, Hungary, 2003. [.pdf]

  29. A. Bertoni and  B. Palano. Structural Complexity and Neural Networks. In 13th Italian Workshop on Neural Nets,  LNCS 2486, pp. 190--216. Vietri sul Mare, Italy, 2002. [.pdf]

  30. C. Mereghetti and  B. Palano. Upper Bounds on the Size of One-way Quantum finite Automata. In 7th Italian Conference on Theoretical Computer Science (ICTCS 2001), LNCS 2202, pp. 123--135. Torino, Italy, 2001. [.pdf]

  31. M. Goldwurm, B. Palano  and M. Santini. On the Circuit Complexity of Random Generation Problems for Regular and Contex--Free Languages. In 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001), LNCS 2010, pp. 305--316. Dresden, Germany, 2001. [.pdf]

  32. C. Mereghetti,  B. Palano  and G. Pighizzini.  On the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. In 3rd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS 2001), pp. 141--148. Vienna, Austria, 2001. [.pdf]

  33. A. Bertoni, M. Goldwurm and  B. Palano. A fast parallel algorithm for the Speed up Problem of traces. In Workshop on Trace Theory and Code Parallelization, pp. 23--28, Dip. di Scienze dell'Informazione, Università degli studi di Milano, Rapporto Interno n. 263--00. Milano, Italy, 2000.[.pdf]

  34. A. Bertoni, C. Mereghetti and  B. Palano.  Computing the Cartier--Foata Form and Height of Traces by Threshold Circuits. In Workshop on Trace Theory and Code Parallelization, pp. 29--36, Dip. di Scienze dell'Informazione, Università degli studi di Milano, Rapporto Interno n. 263--00. Milano, Italy, 2000.[.pdf]

  35. C. Mereghetti and  B. Palano.  Threshold circuits for some matrix operations.  Consequences on regular and probabilistic languages. In 6th Italian Conference on Theoretical Computer Science (ICTCS 1998), pp. 216--227, World Scientific. Prato, Italy, 1998. [.pdf]

Editorship:

  1. C. Mereghetti, B. Palano, G. Pighizzini and D. Wotschke.  7th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2005), Como, Italy, June 30--July 2, 2005. Proceedings, Università degli Studi di Milano, 2005. [.pdf]

  2. R. Freund, M. Holzer, C. Mereghetti, F. Otto and B. Palano.  Third Workshop on Non-Classical Models for Automata and Applications (NCMA 2011), Milan, Italy, July 18--July 19, 2011. Proceedings Austrian Computer Society 2011. [.pdf]

  3. R. Freund, M. Holzer, C. Mereghetti, F. Otto and B. Palano.  Non-Classical Models of Automata and Applications III. Theoretical Informatics and Applications, 2012. [.pdf]

Technical Reports

  1. B. Palano.  A depth upper bound for matrix powering on threshold circuits. Dipartimento di Scienze dell'Informazione, Università degli studi di Milano, Rapporto Interno n. 265--01. [.pdf]

Projects

M.I.U.R. COFIN: "Automi e Linguaggi Formali: Aspetti Matematici e Applicativi", 2013--2015.

CRUI-DAAD (Ateneo Italo-Tedesco, Programma Vigoni): "Complessità descrizionale di modelli di calcolo non classici'', 2011--2012.

M.I.U.R. COFIN: "Aspetti matematici e applicazioni emergenti degli automi e dei linguaggi formali: metodi probabilistici e combinatori in ambito di linguaggi formali", 2008--2010.

CRUI-DAAD (Ateneo Italo-Tedesco, Programma Vigoni): "Riduzione della complessità mediante l'introduzione di strutture'', 2007--2008. She is the SUPERVISOR of the italian group.

M.I.U.R. COFIN: "Linguaggi Formali e Automi: aspetti matematici ed applicativi'', 2005--2007.

M.I.U.R. COFIN: "Linguaggi formali e automi: metodi, modelli e applicazioni'', 2003--2005.

FIRB: "Complessità descrizionale di automi e strutture correlate'', 2002--2004.

M.I.U.R. COFIN: "Linguaggi formali e automi: teoria ed applicazioni'', 2001--2003.

MURST 40%: "Modelli di calcolo innovativi: metodi sintattici e combinatori'', 1998--2000.



Other Scientific Activities

She is a member of the editorial board of "International Journal of Natural Computing Research" (IJNCR).

She is a member of the scientific committee of "Workshop on Descriptional Complexity of Formal Systems" (DCFS 2013).

She is a member of the scientific committee of "International Workshop on Non-Classical Models of Automata and Applications" (NCMA 2010, NCMA 2011 (co-chair), NCMA 2012, NCMA 2013, NCMA 2014).

She is a member of the scientific committee of "Workshop on Formal Models" (WFM 2006, WFM 2007),  Prerov, Czech Republic. Chair: Prof. A. Meduna.

She is a member of the organizing committee of "Workshop on Descriptional Complexity of Formal Systems" (DCFS 2005) and of "International Workshop on Non-Classical Models of Automata and Applications" (NCMA 2011).

She is a member of the organizing committee of the summery school School on Quantum computing, Vietri sul Mare, Italy, 2000. Supervisor: Prof. A. Bertoni.

She is advisor of one PhD thesis on quantum automata by Maria Paola Bianchi.

She is a reviewer of scientific papers submitted to international conferences (ICTCS, STACS, MFCS, DLT, DCFS, CIAA, AFL, SOFSEM, CSR, CIE, LATA, NCMA) and international journals (TCS, DAM, ITA, IC). 



Teaching Activity

Her teaching activity is mainly devoted to the first level course of Informatics from "Facoltà di Scienze MM.FF.NN., Università degli Studi di Milano".

"Algoritmi Paralleli e Distribuiti":   Corso di Laurea Magistrale in Informatica, Università degli Studi di Milano, AA. AA. 2014/2015, 2015/2016, 2016/2017.

"Linguaggi Formali e Automi":   Corso di Laurea in Informatica, Università degli Studi di Milano, AA. AA. 2003/2004, 2004/2005, 2005/2006, 2006/2007, 2007/2008, 2008/2009, 2009/2010, 2011/2012, 2012/2013, 2013/2014, 2014/2015, 2015/2016, 2016/2017.

"Informatica":   Corso di Laurea in Podologia, Facoltà di Medicina e Chirurgia, Università degli Studi di Milano, A.A. 2005/2006; Corso di Laurea in Odontoiatria e Protesi Dentarie, Facoltà di Medicina e Chirurgia, Università degli Studi di Milano, A.A. 2003/2004.



Other Teaching Activities

She is coauthor of notes:

-- "Algoritmi Paralleli" with Prof. A. Bertoni and C. Mereghetti,  for the course "Algoritmi Paralleli e Distribuiti'' Corso di Laurea Magistrale in Informatica, Università degli Studi di Milano.

-- "Linguaggi formali e automi" with Prof. A. Bertoni,  for the course "Linguaggi formali e automi'' Corso di Laurea in Informatica, Università degli Studi di Milano.

--"Reti e Linguaggi" -- with Prof. A. Bertoni -- for the course "Corso di Apprendimento e Reti Neurali" Scuola Nazionale dei Dottorati di Informatica, Facoltà di Scienze (SNDIS98), Bertinoro, 1998.

She is advisor of several thesis on her research subjects.