Some Publications by Carlo Mereghetti

• International Journals
• Book Chapters
• Special Issues and Proceedings Editorships
• International Conference Proceedings
• Workshop Proceedings
• Technical Reports
• PhD and MSc Theses

1. C. Feletti, L. Mambretti, C. Mereghetti, B. Palano.
   Computational power of autonomous robots: transparency vs. opaqueness.
   Theoretical Computer Science, 1036:115153, 2025.
   DOI: 10.1016/j.tcs.2025.115153

2. C. Mereghetti, B. Palano, P. Raucci.
   Latvian quantum finite state automata for unary languages.
   International Journal of Foundations of Computer Science, 0:1-37, 2024.
   DOI: 10.1142/S0129054124430032

3. C. Mereghetti, B. Palano, P. Raucci.
   Unary quantum finite state automata with control language.
   Applied Sciences, 14:1490, 2024.
   DOI: 10.3390/app14041490

4. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
   Iterated uniform finite-state transducers on unary languages.
   Theoretical Computer Science, 969:114049, 2023.
   DOI: 10.1016/j.tcs.2023.114049

5. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
   Iterated uniform finite-state transducers: descriptional complexity of nondeterminism and two-way motion.
   Journal of Automata Languages and Combinatorics, 28:59-88, 2023.
   DOI: 10.25596/jalc-2023-059

6. C. Feletti, C. Mereghetti, B. Palano.
   Uniform circle formation for fully, semi-, and asynchronous opaque robots with lights.
   Applied Sciences, 13:7991, 2023.
   DOI: 10.3390/app13137991

7. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
   Computational and descriptional power of nondeterministic iterated uniform finite-state transducers.
   Fundamenta Informaticae, 185:337-356, 2022.
   DOI: 10.3233/FI-222113

8. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
   Descriptional complexity of iterated uniform finite-state transducers.
   Information and Computation, 284:104691, 2022.
   DOI: 10.1016/j.ic.2021.104691

9. A. Candeloro, C. Mereghetti, B. Palano, S. Cialdi, M.G.A. Paris, S. Olivares.
   An enhanced photonic quantum finite automaton.
   Applied Sciences, 11:8768, 2021.
   DOI: 10.3390/app11188768

10. C. Mereghetti, B. Palano.
    Guest Column: Quantum Finite Automata: From Theory to Practice.
    ACM SIGACT News, 52:38-59, 2021.
    DOI: 10.1145/3494656.3494666

11. S. Jakobi, K. Meckel, C. Mereghetti, B. Palano.
    The descriptional power of queue automata of constant length.
    Acta Informatica, 58:335-356, 2021.
    DOI: 10.1007/s00236-021-00398-7

12. C. Mereghetti, B. Palano, S. Cialdi, V. Vento, M.G.A. Paris, S. Olivares.
    Photonic realization of a quantum finite automaton.
    Physical Review Research, 2:013089, 2020.
    DOI: 10.1103/PhysRevResearch.2.013089

13. Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano.
    Boolean language operations on nondeterministic automata with a pushdown of constant height.
    Journal of Computer and System Science, 90:99-114, 2017.
    DOI: 10.1016/j.jcss.2017.06.007

14. M.P. Bianchi, C. Mereghetti, B. Palano.
    Quantum finite automata: Advances on Bertoni's ideas.
    Theoretical Computer Science, 664:39-53, 2017.
    DOI: 10.1016/j.tcs.2016.01.045

15. M.P. Bianchi, C. Mereghetti, B. Palano.
    On the power of one-way automata with quantum and classical states.
    International Journal of Foundations of Computer Science, 26:895-912, 2015.
    DOI: 10.1142/S0129054115400055

16. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, M. Wendlandt.
    Deterministic input-driven queue automata: finite turns, decidability, and closure properties.
    Theoretical Computer Science, 578:58-71, 2015.
    DOI: 10.1016/j.tcs.2015.01.012

17. M.P. Bianchi, C. Mereghetti, B. Palano.
    Size lower bounds for quantum automata.
    Theoretical Computer Science. 551:102-115, 2014.
    DOI: 10.1016/j.tcs.2014.07.004

18. Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano.
    Removing nondeterminism in constant height pushdown automata.
    Information and Computation. 237:257-267, 2014.
    DOI: 10.1016/j.ic.2014.03.002

19. A. Malcher, K. Meckel, C. Mereghetti, B. Palano.
    Descriptional complexity of pushdown store languages.
    Journal of Automata Languages and Combinatorics. 17:225-244, 2012.
    DOI: 10.25596/jalc-2012-225

20. M.P. Bianchi, M. Holzer, S. Jakobi, C. Mereghetti, B. Palano, G. Pighizzini.
    On inverse operations and their descriptional complexity.
    Journal of Automata Languages and Combinatorics. 17:61-81, 2012.
    DOI: 10.25596/jalc-2012-061

21. C. Choffrut, A. Malcher, C. Mereghetti, B. Palano.
    First-order logics: some characterizations and closure properties.
    Acta Informatica, 49:225-248, 2012.
    DOI: 10.1007/s00236-012-0157-z

22. Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano.
    The size-cost of Boolean operations on constant height deterministic pushdown automata.
    Theoretical Computer Science, 449:23-36, 2012.
    DOI: 10.1016/j.tcs.2012.05.009

23. A. Malcher, C. Mereghetti, B. Palano.
    Descriptional complexity of two-way pushdown automata with restricted head reversals.
    Theoretical Computer Science, 449:119-133, 2012.
    DOI: 10.1016/j.tcs.2012.04.007

24. M.P. Bianchi, C. Mereghetti, B. Palano, G. Pighizzini.
    On the size of unary probabilistic and nondeterministic automata.
    Fundamenta informaticae, 112:119-135, 2011.
    DOI: 10.3233/FI-2011-583

25. V. Geffert, C. Mereghetti, G. Pighizzini.
    One pebble versus $\varepsilon$log n bits.
    Fundamenta informaticae, 104:55-69, 2010.
    DOI: 10.3233/FI-2010-335

26. V. Geffert, C. Mereghetti, B. Palano.
    More concise representation of regular languages by automata and regular expressions.
    Information and Computation, 208:385-394, 2010.
    DOI: 10.1016/j.ic.2010.01.002

27. A. Bertoni, C. Mereghetti, B. Palano.
    Trace monoids with idempotent generators and measure only quantum automata.
    Natural Computing, 9:383-395, 2010.
    DOI: 10.1007/s11047-009-9154-8

28. A. Malcher, C. Mereghetti, B. Palano.
    Sublinearly space bounded iterative arrays.
    International Journal of Foundations of Computer Science, 21:843-858, 2010.
    DOI: 10.1142/S0129054110007581

29. C. Mereghetti.
    Testing the descriptional power of small Turing machines on nonregular language acceptance.
    International Journal of Foundations of Computer Science, 19:827-843, 2008.
    DOI: 10.1142/S012905410800598X

30. V. Geffert, C. Mereghetti, G. Pighizzini.
    Complementing two-way finite automata.
    Information and Computation, 205:1173-1187, 2007.
    DOI: 10.1016/j.ic.2007.01.008

31. C. Mereghetti, B. Palano.
    Quantum automata for some multiperiodic languages.
    Theoretical Computer Science, 387:177-186, 2007.
    DOI: 10.1016/j.tcs.2007.07.037

32. C. Mereghetti, B. Palano.
    Quantum finite automata with control language.
    Theoretical Informatics and Applications, 40:315-332, 2006.
    DOI: 10.1051/ita:2006007

33. A. Bertoni, C. Mereghetti, B. Palano.
    Some formal tools for analyzing quantum automata.
    Theoretical Computer Science, 356:14-25, 2006.
    DOI: 10.1016/j.tcs.2006.01.042

34. C. Mereghetti, B. Palano.
    The complexity of minimum difference cover.
    Journal of Discrete Algorithms, 4:239-254, 2006.
    DOI: 10.1016/j.jda.2005.03.004

35. A. Bertoni, C. Mereghetti, B. Palano.
    Small size quantum automata recognizing some regular languages.
    Theoretical Computer Science, 340:394-407, 2005.
    DOI: 10.1016/j.tcs.2005.03.032

36. A. Bertoni, C. Mereghetti, B. Palano.
    Golomb rulers and difference sets for succinct quantum automata.
    International Journal of Foundations of Computer Science, 14:871-888, 2003.
    DOI: 10.1142/S0129054103002060

37. V. Geffert, C. Mereghetti, G. Pighizzini.
    Converting two-way nondeterministic unary automata into simpler automata.
    Theoretical Computer Science, 295:189-203, 2003.
    DOI: 10.1016/S0304-3975(02)00403-6

38. C. Mereghetti, B. Palano.
    On the size of one-way quantum finite automata with periodic behaviors.
    Theoretical Informatics and Applications, 36:277-291, 2002.
    DOI: 10.1051/ita:2002014

39. C. Mereghetti, B. Palano.
    The parallel complexity of deterministic and probabilistic automata.
    Journal of Automata, Languages and Combinatorics, 7:95-108, 2002.
    DOI: 10.25596/jalc-2002-095

40. C. Mereghetti, G. Pighizzini.
    Optimal simulations between unary automata.
    SIAM Journal on Computing, 30:1976-1992, 2001.
    DOI: 10.1137/S009753979935431X

41. C. Mereghetti, B. Palano, G. Pighizzini.
    Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata.
    Theoretical Informatics and Applications, 35:477-490, 2001.
    DOI: 10.1051/ita:2001106

42. O. D'Antona, C. Mereghetti, F. Zamparini.
    The 224 non-chordal graphs on less than 10 vertices whose chromatic polynomials have no complex roots.
    Discrete Mathematics, 226:387-396, 2001.
    DOI: 10.1016/S0012-365X(00)00170-9

43. C. Mereghetti, B. Palano.
    Threshold circuits for iterated matrix product and powering.
    Theoretical Informatics and Applications, 34:39-46, 2000.
    DOI: 10.1051/ita:2000105

44. C. Mereghetti, G. Pighizzini.
    Two-way automata simulations and unary languages.
    Journal of Automata, Languages and Combinatorics, 5:287-300, 2000.
    DOI: 10.25596/jalc-2000-287

45. L. Colucci, O. D'Antona, C. Mereghetti.
    Fibonacci and Lucas numbers as cumulative connection constants.
    The Fibonacci Quarterly, 38.2:157-164, 2000.
    ISSN: 0015-0517, URL: https://www.fq.math.ca/Scanned/38-2/colucci.pdf

46. V. Geffert, C. Mereghetti, G. Pighizzini.
    Sublogarithmic bounds on space and reversals.
    SIAM Journal on Computing, 28:325-340, 1998.
    DOI: 10.1137/S0097539796301306

47. C. Mereghetti, G. Pighizzini.
    A remark on middle space bounded alternating Turing machines.
    Information Processing Letters, 56:229-232, 1995.
    DOI: 10.1016/0020-0190(95)00151-2

48. A. Bertoni, C. Mereghetti, G. Pighizzini.
    An optimal lower bound for nonregular languages.
    Information Processing Letters, 50:289-292, 1994.
    DOI: 10.1016/0020-0190(94)90018-3

49. A. Bertoni, C. Mereghetti, G. Pighizzini.
    Corrigendum: An optimal lower bound for nonregular languages.
    Information Processing Letters, 52:339, 1994.
    DOI: 10.1016/0020-0190(94)90018-3

1. M.P. Bianchi, C. Mereghetti, B. Palano.
   Complexity of Promise Problems on Classical and Quantum Automata.
   Eds. C.S. Calude, R. Freivalds, K. Iwama, Computing with New Resources. Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday,
   Lecture Notes in Computer Science 8808, 161-175, Springer, 2014.
   DOI: 10.1007/978-3-319-13350-8_12

2. C. Mereghetti, B. Palano.
   Quantum automata and periodic events.
   Ed. C. Martin-Vide, Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory.
   Vol. 2: Scientific Applications of Language Methods, 563-584, Imperial College Press, London, 2011.
   DOI: 10.1142/9781848165458_0011

3. C. Mereghetti, G. Pighizzini.
   The world of unary languages. A quick tour.
   Eds. C. Martin-Vide and V. Mitrana, Grammars and Automata for String Processing: from Mathematics
   and Computer Science to Biology, and Back, 275-284, Taylor and Francis, London, 2003.
   DOI: 10.1201/9780203009642.ch27

1. R. Freund, M. Holzer, C. Mereghetti, F. Otto and B. Palano.
   Non-Classical Models of Automata and Applications III.
   Theoretical Informatics and Applications, 2012.
   DOI: 10.1051/ita/2012022

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

3. C. Mereghetti, B. Palano, G. Pighizzini, D. Wotschke.
   Seventh International Workshop on Descriptional Complexity of Formal Systems (DCFS'05),
   Como, Italy, June 30-July 2, 2005. Proceedings, Università degli Studi di Milano, 2005.

1. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, P. Raucci, M. Wendlandt.
   On properties of languages accepted by deterministic pushdown automata with translucent input letters.
   In 28th International Conference on Implementation and Application of Automata (CIAA'24), Proceedings,
   Lecture Notes in Computer Science 15015, pp. 208-220, Springer, 2024.
   DOI: 10.1007/978-3-031-71112-1_15

2. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, P. Raucci, M. Wendlandt.
   Deterministic pushdown automata with translucent input letters.
   In 28th International Conference Developments in Language Theory (DLT'24), Proceedings,
   Lecture Notes in Computer Science 14791, pp. 203-217, Springer, 2024.
   DOI: 10.1007/978-3-031-66159-4_15

3. C. Feletti, L. Mambretti, C. Mereghetti, B. Palano.
   Computational power of opaque robots.
   In 3rd International Symposium on Algorithmic Foundations of Dynamic Networks (SAND'24), Proceedings,
   Eds. A. Casteigts, F. Kuhn, Leibniz International Proceedings in Informatics (LIPIcs) 292, pp. 13:1-13:19, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2024.
   DOI: 10.4230/LIPIcs.SAND.2024.13

4. C. Feletti, C. Mereghetti, B. Palano.
   O(log n)-time uniform circle formation for asynchronous opaque luminous robots.
   In 27th International Conference on Principles of Distributed Systems (OPODIS'23), Proceedings,
   Eds. A. Bessani, X. Defago, J. Nakamura, K. Wada, Y. Yamauchi, Leibniz International Proceedings in Informatics (LIPIcs) 286, pp. 5:1-5:21, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2023.
   DOI: 10.4230/LIPIcs.OPODIS.2023.5

5. C. Mereghetti, B. Palano, P. Raucci.
   Latvian quantum finite state automata for unary languages.
   In 13th International Workshop on Non-classical models of automata and applications (NCMA'23), Proceedings,
   Eds. R. Freund, B. Nagy, Electronic Proceedings in Theoretical Computer Science (EPTCS) 388, pp. 63-78, EPTCS.org, 2023.
   DOI: 10.4204/EPTCS.388.8

6. C. Feletti, C. Mereghetti, B. Palano, P. Raucci.
   Uniform circle formation for fully, semi-, and asynchronous opaque robots with lights.
   In 23rd Italian Conference on Theoretical Computer Science (ICTCS'22), Proceedings,
   Eds. U. Dal Lago, D. Gorla, CEUR WORKSHOP PROCEEDINGS 3284, pp. 207-221, CEUR-WS.org, 2022.
   ISSN: 1613-0073, URL: https://ceur-ws.org/Vol-3284/8511.pdf

7. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
   Iterated transduction on unary languages.
   In 22nd Italian Conference on Theoretical Computer Science (ICTCS'21), Proceedings,
   Eds. C. Sacerdoti Coen, I. Salvo, CEUR WORKSHOP PROCEEDINGS 3072, pp. 87-92, CEUR-WS.org, 2021.
   ISSN: 1613-0073, URL: https://ceur-ws.org/Vol-3072/paper7.pdf

8. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
   Iterated uniform finite-state transducers on unary languages.
   In 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'21). Proceedings.
   Lecture Notes in Computer Science 12607, pp. 218-232, Springer, 2021.
   DOI: 10.1007/978-3-030-67731-2_16

9. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
   Iterated uniform finite-state transducers: descriptional complexity of nondeterminism and two-way motion.
   In 22th International Workshop on Descriptional Complexity of Formal Systems (DCFS'20), Proceedings,
   Lecture Notes in Computer Science 12442, pp. 117-129, Springer, 2020.
   DOI: 10.1007/978-3-030-62536-8_10

10. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
    Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power.
    In 16th International Conference Computability in Europe 2020 (CiE'20), Proceedings,
    Lecture Notes in Computer Science 12098, pp. 87-99, Springer, 2020.
    DOI: 10.1007/978-3-030-51466-2_8

11. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
    Iterated uniform finite-state transducers.
    In 20th Italian Conference on Theoretical Computer Science (ICTCS'19), Proceedings,
    Eds. A. Cherubini, N. Sabadini, S. Tini, CEUR WORKSHOP PROCEEDINGS 2504, pp. 52-57, CEUR-WS.org, 2019.
    ISSN: 1613-0073, URL: https://ceur-ws.org/Vol-2504/paper6.pdf

12. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano.
    Descriptional complexity of iterated uniform finite-state transducers.
    In 21th International Workshop on Descriptional Complexity of Formal Systems (DCFS'19), Proceedings,
    Lecture Notes in Computer Science 11612, pp. 223-234, Springer, 2019.
    DOI: 10.1007/978-3-030-23247-4_17

13. C. Feletti, C. Mereghetti, B. Palano.
    Uniform circle formation for swarms of opaque robots with lights.
    In 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'18), Proceedings,
    Lecture Notes in Computer Science 11201, pp. 317-332, Springer, 2018.
    DOI: 10.1007/978-3-030-03232-6_21

14. M.P. Bianchi, C. Mereghetti, B. Palano.
    On the power of one-way automata with quantum and classical states.
    In 19th International Conference on Implementation and Application of Automata (CIAA'14), Proceedings,
    Lecture Notes in Computer Science 8587, pp. 84-97, Springer, 2014.
    BEST PAPER AWARD (SHENG YU AWARD)
    DOI: 10.1007/978-3-319-08846-4_6

15. S. Jakobi, K. Meckel, C. Mereghetti, B. Palano.
    Queue automata of constant length.
    In 15th International Workshop on Descriptional Complexity of Formal Systems (DCFS'13), Proceedings,
    Lecture Notes in Computer Science 8031, pp. 124-135, Springer, 2013.
    DOI: 10.1007/978-3-642-39310-5_13

16. V. Geffert, A. Malcher, K. Meckel, C. Mereghetti, B. Palano.
    A direct construction of finite automata for pushdown store languages.
    In 15th International Workshop on Descriptional Complexity of Formal Systems (DCFS'13), Proceedings,
    Lecture Notes in Computer Science 8031, pp. 90-101, Springer, 2013.
    DOI: 10.1007/978-3-642-39310-5_10

17. M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, M. Wendlandt.
    Input-driven queue automata: finite turns, decidability, and closure properties.
    In 18th International Conference on Implementation and Application of Automata (CIAA'13), Proceedings,
    Lecture Notes in Computer Science 7982, pp. 232-243, Springer, 2013.
    DOI: 10.1007/978-3-642-39274-0_21

18. M.P. Bianchi, C. Mereghetti, B. Palano.
    Size lower bounds for quantum automata.
    In 11th International Conference on Unconventional Computation and Natural Computation (UCNC'13), Proceedings,
    Lecture Notes in Computer Science 7956, pp. 19-30, Springer, 2013.
    DOI: 10.1007/978-3-642-39074-6_4

19. Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano.
    Boolean language operations on nondeterministic automata with a pushdown of constant height.
    In 8th International Computer Science Symposium in Russia (CSR'13), Proceedings,
    Lecture Notes in Computer Science 7913, pp. 100-111, Springer, 2013.
    DOI: 10.1007/978-3-642-38536-0_9

20. A. Malcher, K. Meckel, C. Mereghetti, B. Palano.
    On pushdown store languages.
    In 13th Italian Conference on Theoretical Computer Science 2012 (ICTCS'12), Proceedings,
    Eds. P.Massazza et alt., pp. 168-171, 2012.

21. Z. Bednárová, V. Geffert, C. Mereghetti, B. Palano.
    Removing nondeterminism in constant height pushdown automata.
    In 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS'12), Proceedings,
    Lecture Notes in Computer Science 7386, pp. 76-88, Springer, 2012.
    DOI: 10.1007/978-3-642-31623-4_6

22. A. Malcher, K. Meckel, C. Mereghetti, B. Palano.
    Descriptional complexity of pushdown store languages.
    In 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS'12), Proceedings,
    Lecture Notes in Computer Science 7386, pp. 209-221, Springer, 2012.
    DOI: 10.1007/978-3-642-31623-4_16

23. Z. Bednárová, V. Geffert, C. Mereghetti, 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'11), Proceedings,
    Lecture Notes in Computer Science 6808, pp. 80-92, Springer, 2011.
    DOI: 10.1007/978-3-642-22600-7_7

24. A. Malcher, C. Mereghetti, B. Palano.
    Descriptional complexity of two-way pushdown automata with restricted head reversals.
    In 13th International Workshop on Descriptional Complexity of Formal Systems (DCFS'11), Proceedings,
    Lecture Notes in Computer Science 6808, pp. 248-260, Springer, 2011.
    DOI: 10.1007/978-3-642-22600-7_20

25. M.P. Bianchi, C. Mereghetti, B. Palano, G. Pighizzini.
    Probabilistic vs. nondeterministic unary automata.
    In 2nd International Workshop on Non-classical models of automata and applications (NCMA'10), Proceedings,
    Eds. H. Bordihn, R. Freund, M. Holzer, M. Kutrib, F. Otto, Osterreichischen Computer Gesellschaft, pp. 33-34, book@ocg.at series, 2010.
    ISBN: 9783854032564

26. C. Choffrut, A. Malcher, C. Mereghetti, B. Palano.
    On the expressive power of FO[+].
    In 4th International Conference on Language and Automata Theory and Applications (LATA'10), Proceedings,
    Lecture Notes in Computer Science 6031, pp. 190-201, Springer, 2010.
    DOI: 10.1007/978-3-642-13089-2_16

27. V. Geffert, C. Mereghetti, G. Pighizzini.
    One pebble versus log n bits.
    In International Workshop on Non-classical models of automata and applications (NCMA'09), Proceedings,
    Eds. H. Bordihn, R. Freund, M. Holzer, M. Kutrib, F. Otto, pp. 121-133, Osterreichischen Computer Gesellschaft, book@ocg.at series, 2009.
    ISBN: 9783854032564

28. A. Malcher, C. Mereghetti, B. Palano.
    Logical description of structured and XML languages.
    In 11th Italian Conference on Theoretical Computer Science 2009 (ICTCS'09), Proceedings,
    Eds. A. Cherubini, M. Coppo, G. Persiano, pp. 161-167, 2009.

29. V. Geffert, C. Mereghetti, B. Palano.
    More concise representation of regular languages by automata and regular expressions.
    In 12th International Conference on Developments in Language Theory (DLT'08), Proceedings,
    Lecture Notes in Computer Science 5257, pp. 359-370, Springer, 2008.
    DOI: 10.1007/978-3-540-85780-8_28

30. A. Malcher, C. Mereghetti, B. Palano.
    Sublinearly space bounded iterative arrays.
    In 12th International Conference on Automata and Formal Languages (AFL'08), Proceedings,
    Eds. E. Csuhaj-Varjú, Z. Ésik, pp. 292-301, Balatonfured, Hungary, 2008.
    ISBN: 9789633113677

31. V. Geffert, C. Mereghetti, B. Palano.
    Descriptional Complexity Issues Concerning Regular Languages.
    In 18th Theorietag Automaten und Formale Sprachen, Proceedings,
    Eds. M. Holzer, M. Kutrib, A. Malcher, pp. 11-22, Giessen, Germany, 2008.
    ISBN: 9783000259203

32. A. Malcher, C. Mereghetti, B. Palano.
    Recent results on iterative arrays with small space bounds.
    In AUTOMATA 2008, EPSRC Workshop on Cellular Automata Theory and Applications, Proceedings,
    Eds. A.Adamatzky et al., pp. 222-226, Bristol, United Kingdom, Luniver Press, 2008
    ISBN: 9781905986163

33. C. Mereghetti.
    The descriptional power of sublogarithmic resource bounded Turing machines.
    In 9th International Workshop on Descriptional Complexity of Formal Systems (DCFS'07), Proceedings,
    Eds. V. Geffert, G. Pighizzini, pp. 12-26, High Tatras, Slovakia, 2007.
    ISBN: 9788070976883

34. C. Mereghetti, B. Palano.
    Quantum automata for some multiperiodic languages.
    In 8th International Workshop on Descriptional Complexity of Formal Systems (DCFS'06), Proceedings,
    Eds. H. Lung, G. Pighizzini, pp. 199-210, Las Cruces, New Mexico, 2006.

35. V. Geffert, C. Mereghetti, G. Pighizzini.
    Complementing two-way finite automata.
    In 9th International Conference on Development in Language Theory (DLT'05), Proceedings,
    Lecture Notes in Computer Science 3572, pp. 260-271, Springer, 2005.
    DOI: 10.1007/11505877_23

36. A. Bertoni, C. Mereghetti, B. Palano.
    Some formal methods for analyzing quantum automata.
    In 7th International Workshop on Descriptional Complexity of Formal Systems (DCFS'05), Proceedings,
    Eds. C. Mereghetti, B. Palano, G. Pighizzini, D. Wotschke, pp. 1-14, Univ. Milano, Como, 2005.

37. A. Bertoni, C. Mereghetti, B. Palano.
    Approximating stochastic events by quantum automata.
    In ERATO International Conference on Quantum Information Science 2003, Proceedings, Kyoto, Japan, 2003.

38. A. Bertoni, C. Mereghetti, B. Palano.
    Lower bounds on the size of quantum automata accepting unary languages.
    In 8th Italian Conference on Theoretical Computer Science 2003 (ICTCS'03), Proceedings,
    Lecture Notes in Computer Science 2841, pp. 86-96, Springer, 2003.
    DOI: 10.1007/978-3-540-45208-9_8

39. A. Bertoni, C. Mereghetti, B. Palano.
    Quantum computing: 1-way quantum automata.
    In 7th International Conference on Development in Language Theory (DLT'03), Proceedings,
    Lecture Notes in Computer Science 2710, pp. 1-20, Springer 2003.
    DOI: 10.1007/3-540-45007-6_1

40. V. Geffert, C. Mereghetti, G. Pighizzini.
    Converting two-way nondeterministic unary automata into simpler automata.
    In 26th International Symposium on Mathematical Foundations of Computer Science 2001 (MFCS'01), Proceedings,
    Lecture Notes in Computer Science 2136, pp. 398-407, Springer 2001.
    DOI: 10.1007/3-540-44683-4_35

41. C. Mereghetti, B. Palano, G. Pighizzini.
    On the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata.
    In 3rd International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS'01), Proceedings,
    pp. 141-148, Univ. Otto Von Guericke, Magdeburg, 2001.

42. C. Mereghetti, B. Palano.
    Upper bounds on the size of one-way quantum finite automata.
    In 7th Italian Conf. on Theoretical Computer Science 2001 (ICTCS'01), Proceedings,
    Lecture Notes in Computer Science, pp. 123-135, Springer 2001.
    DOI: 10.1007/3-540-45446-2_8

43. C. Mereghetti, G. Pighizzini.
    Unary automata simulations and cyclic languages.
    In 1st International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS'99), Proceedings,
    pp. 145-153, Univ. Otto Von Guericke, Magdeburg, 1999.

44. C. Mereghetti, G. Pighizzini.
    Optimal simulations between unary automata.
    In 15th International Symposium on Theoretical Aspects of Computer Science 1998 (STACS'98), Proceedings,
    Lecture Notes in Computer Science 1373, pp. 139-149, Springer, 1998.
    DOI: 10.1007/BFb0028556

45. C. Mereghetti, B. Palano.
    Threshold circuits for some matrix operations. consequences on regular and probabilistic languages.
    In 6th Italian Conference on Theoretical Computer Science (ICTCS'98), Proceedings,
    pp. 216-227, World Scientific, 1998.
    ISBN: 9814544302

46. A. Bertoni, C. Mereghetti, G. Pighizzini.
    Strong optimal lower bounds for Turing machines that accept nonregular languages.
    In 20th International Symposium on Mathematical Foundations of Computer Science 1995 (MFCS'95), Proceedings,
    Lecture Notes in Computer Science 969, pp. 309-318, Springer Verlag, 1995.
    DOI: 10.1007/3-540-60246-1_137

47. A. Bertoni, C. Mereghetti, G. Pighizzini.
    On languages accepted with simultaneous complexity bounds and their ranking problem.
    In 19th International Symposium on Mathematical Foundations of Computer Science 1994 (MFCS'94), Proceedings,
    Lecture Notes in Computer Science 841, pp. 245-255, Springer Verlag, 1994.
    DOI: 10.1007/3-540-58338-6_71

48. C. Mereghetti.
    On space bounded Turing machines with a constant number of input head inversions.
    In 4h Italian Conference on Theoretical Computer Science (ICTCS'92), Proceedings,
    pp. 269-277, World Scientific, 1992.
    ISBN: 9810212585

1. C. Mereghetti, B. Palano.
   Computing the Cartier-Foata normal form and the height of traces by threshold circuits.
   Workshop on Trace Theory and Code Parallelization.
   Eds. A. Bertoni, M. Goldwurm, S.C. Reghizzi. Tech. Rep. n. 263-00, Dipartimento di Scienze dell'Informazione, Università di Milano, 2000.

1. A. Malcher, K. Meckel, . Mereghetti, B. Palano.
   Descriptional complexity of pushdown store languages.
   Tech. Rep. n. 1203, Institut für Informatik, J. Liebig Universität, Giessen, Deutschland, 2012.
   

2. C. Choffrut, A. Malcher, C. Mereghetti, B. Palano.
   Logical description of structured languages.
   Tech. Rep. n. 324-09, Dipartimento di Scienze dell'Informazione, Università di Milano, 2009.
   

3. A. Malcher, C. Mereghetti, B. Palano.
   Logical description of structured and XML-languages.
   Tech. Rep. n. 319-08, Dipartimento di Scienze dell'Informazione, Università di Milano, 2008.
   

4. A. Malcher, C. Mereghetti, B. Palano.
   Sublinearly space bounded iterative arrays.
   Tech. Rep. n. 1/07, Institut für Informatik, J.W. Goethe Universität, Frankfurt am Main, Deutschland, 2007.
   

5. C. Mereghetti, B. Palano.
   The complexity of minimum difference cover.
   Tech. Rep. n. 300-04, Dipartimento di Scienze dell'Informazione, Università di Milano, 2004.
   

6. C. Mereghetti.
   Basi di dati e sistemi informativi. Lecture Notes in Data Base and Information Systems.
   Dipartimento di Informatica, Sistemistica e Comunicazione, Università di Milano - Bicocca, 2002.
   

7. C. Mereghetti, B. Palano, G. Pighizzini.
   On the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata.
   Tech. Rep. n. 267-01, Dipartimento di Scienze dell'Informazione, Università di Milano, 2001.
   

8. C. Mereghetti, B. Palano.
   Upper bounds on the size of one-way quantum finite automata.
   Tech. Rep. n. 266-01, Dipartimento di Scienze dell'Informazione, Università di Milano, 2001.
   

9. A. Bertoni, C. Mereghetti.
   Theoretical Computer Science. Lecture Notes in Theoretical Computer Science.
   Dipartimento di Scienze dell'Informazione, Università di Milano, 2001.
   URL: https://mereghetti.di.unimi.it/it/dispense/compl.pdf

10. C. Mereghetti, B. Palano.
    Quantum finite automata and transducers.
    Tech. Rep. n. 246-00, Dipartimento di Scienze dell'Informazione, Università di Milano, 2000.
    

11. C. Mereghetti, B. Palano.
    Matrix powering in constant depth.
    Tech. Rep. n. 245-00, Dipartimento di Scienze dell'Informazione, Università di Milano, 2000.
    

12. C. Mereghetti, B. Palano.
    The parallel complexity of deterministic and probabilistic automata.
    Tech. Rep. n. 242-99, Dipartimento di Scienze dell'Informazione, Università di Milano, 1999.
    

13. A. Bertoni, C. Mereghetti, G. Pighizzini.
    Space and reversals complexity of nonregular languages.
    Tech. Rep. n. 224-98, Dipartimento di Scienze dell'Informazione, Università di Milano, 1998.
    

14. O. D'Antona, C. Mereghetti, F. Zamparini.
    The 224 non-chordal graphs on less than 10 vertices whose chromatic polynomial has no complex roots.
    Tech. Rep. n. 220-98, Dipartimento di Scienze dell'Informazione, Università di Milano, 1998.
    

15. L. Colucci, O. D'Antona, C. Mereghetti.
    Fibonacci and Lucas numbers as cumulative connection constants.
    Tech. Rep. n. 219-98, Dipartimento di Scienze dell'Informazione, Università di Milano, 1998.
    

16. C. Mereghetti, B. Palano.
    Threshold circuits for some matrix operations. Consequences on regular and probabilistic languages.
    Tech. Rep. n. 218-98, Dipartimento di Scienze dell'Informazione, Università di Milano, 1998.
    

17. S. Basagni, C. Mereghetti, S. Panizza.
    A coloured stochastic Petri net model for dining philosophers.
    Tech. Rep. n. 202-97, Dipartimento di Scienze dell'Informazione, Università di Milano, 1997.
    

18. V. Geffert, C. Mereghetti, G. Pighizzini.
    Alternation and the sublogarithmic complexity measure SPACE x REVERSALS.
    Tech. Rep. n. 165-96, Dipartimento di Scienze dell'Informazione, Università di Milano, 1996.
    

19. E. Damiani, O. D'Antona, C. Mereghetti.
    On the coefficients of chromatic polynomials expansions.
    Tech. Rep. n. 164-96, Dipartimento di Scienze dell'Informazione, Università di Milano, 1996.
    Presented at the 2nd International Conference on Graph Theory, Bled, Slovenija, 1995.

20. C. Mereghetti.
    On entropy.
    Tech. Rep. n. 163-96, Dipartimento di Scienze dell'Informazione, Università di Milano, 1996.
    Also published in Collected Works Dedicated to G.-C. Rota.

• C. Mereghetti.
  Space, reversals, and ambiguity bounded Turing machines.
  PhD Thesis, Università di Torino/Milano, 1996.
  

• C. Mereghetti.
  The complexity of counting and ranking functions defined on classes of formal languages.
  MSc Thesis, Dipartimento di Scienze dell'Informazione, Università di Milano, 1991.
  

Dipartimento di Informatica "Giovanni Degli Antoni" Università degli Studi di Milano via Celoria 18, 20133 Milano, Italy office: Room 6008, 6th floor phone: +39 02 503 16342 mail: carlo.mereghetti@unimi.it