Dipartimento di Informatica
Università degli Studi di Milano


Some publications by Carlo Mereghetti

International journals
In collections
International conferences and workshops
Editorships
Tecnical reports
PhD thesis, MsC thesis


International journals
  1. 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, 2017. Accepted for publication.

  2. M.P. Bianchi, C. MEREGHETTI, B. Palano.
    Quantum finite automata: Advances on Bertoni's ideas.
    Theoretical Computer Science, 664:39-53, 2017.

  3. 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.

  4. 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.

  5. M.P. Bianchi, C. MEREGHETTI, B. Palano.
    Size lower bounds for quantum automata.
    Theoretical Computer Science. 551:102-105, 2014.

  6. Z. Bednárová, V. Geffert, C. MEREGHETTI, B. Palano.
    Removing nondeterminism in constant height pushdown automata
    Information and Computation. 237:257-267, 2014.

  7. A. Malcher, K. Meckel, C. MEREGHETTI, B. Palano.
    Descriptional complexity of pushdown store languages.
    Journal of Automata Languages and Combinatorics. 17:225-244, 2012.

  8. 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.

  9. C. Choffrut, A. Malcher, C. MEREGHETTI, B. Palano.
    First-order logics: some characterizations and closure properties.
    Acta Informatica, 49:225-248, 2012.

  10. 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.

  11. A. Malcher, C. MEREGHETTI, B. Palano.
    Descriptional complexity of two-way pushdown automata with restricted head reversals.
    Theoretical Computer Science, 449:119-133, 2012.

  12. M.P. Bianchi, C. MEREGHETTI, B. Palano, G. Pighizzini.
    On the size of unary probabilistic and nondeterministic automata.
    Fundamenta informaticae, 112:119-135, 2011.

  13. V. Geffert, C. MEREGHETTI, G. Pighizzini.
    One pebble versus $\varepsilon$log n bits.
    Fundamenta informaticae, 104:55-69, 2010.

  14. V. Geffert, C. MEREGHETTI, B. Palano.
    More concise representation of regular languages by automata and regular expressions.
    Information and Computation, 208:385-394, 2010.

  15. A. Bertoni, C. MEREGHETTI, B. Palano.
    Trace monoids with idempotent generators and measure only quantum automata.
    Natural Computing, 9:383-395, 2010.

  16. A. Malcher, C. MEREGHETTI, B. Palano.
    Sublinearly space bounded iterative arrays.
    International Journal of Foundations of Computer Science, 21:843-858, 2010.

  17. 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.

  18. V. Geffert, C. MEREGHETTI, G. Pighizzini.
    Complementing two-way finite automata.
    Information and Computation, 205:1173-1187, 2007.

  19. C. MEREGHETTI, B. Palano.
    Quantum automata for some multiperiodic languages.
    Theoretical Computer Science, 387:177-186, 2007.

  20. C. MEREGHETTI, B. Palano.
    Quantum finite automata with control language.
    Theoretical Informatics and Applications, 40:315-332, 2006.

  21. A. Bertoni, C. MEREGHETTI, B. Palano.
    Some formal tools for analyzing quantum automata.
    Theoretical Computer Science, 356:14-25, 2006.

  22. C. MEREGHETTI, B. Palano.
    The complexity of minimum difference cover.
    Journal of Discrete Algorithms, 4:239-254, 2006.

  23. A. Bertoni, C. MEREGHETTI, B. Palano.
    Small size quantum automata recognizing some regular languages.
    Theoretical Computer Science, 340:394-407, 2005.

  24. 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.

  25. V. Geffert, C. MEREGHETTI, G. Pighizzini.
    Converting two-way nondeterministic unary automata into simpler automata.
    Theoretical Computer Science, 295:189-203, 2003.

  26. C. MEREGHETTI, B. Palano.
    On the size of one-way quantum finite automata with periodic behaviors.
    Theoretical Informatics and Applications, 36:277-291, 2002.

  27. C. MEREGHETTI, B. Palano.
    The parallel complexity of deterministic and probabilistic automata.
    Journal of Automata, Languages and Combinatorics, 7:95-108, 2002

  28. C. MEREGHETTI, G. Pighizzini.
    Optimal simulations between unary automata.
    SIAM Journal on Computing, 30:1976-1992, 2001.

  29. 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.

  30. 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.

  31. C. MEREGHETTI, B. Palano.
    Threshold circuits for iterated matrix product and powering.
    Theoretical Informatics and Applications,, 34:39-46, 2000.

  32. C. MEREGHETTI, G. Pighizzini.
    Two-way automata simulations and unary languages.
    Journal of Automata, Languages and Combinatorics, 5:287-300, 2000.

  33. L. Colucci, O. D'Antona, C. MEREGHETTI.
    Fibonacci and Lucas numbers as cumulative connection constants.
    The Fibonacci Quarterly, 38.2:157-164, 2000.

  34. V. Geffert, C. MEREGHETTI, G. Pighizzini.
    Sublogarithmic bounds on space and reversals.
    SIAM Journal on Computing, 28:325-340, 1998.

  35. C. MEREGHETTI, G. Pighizzini.
    A remark on middle space bounded alternating Turing machines.
    Information Processing Letters, 56:229-232, 1995.

  36. A. Bertoni, C. MEREGHETTI, G. Pighizzini.
    An optimal lower bound for nonregular languages.
    Information Processing Letters, 50:289-292, 1994.

  37. A. Bertoni, C. MEREGHETTI, G. Pighizzini.
    Corrigendum: An optimal lower bound for nonregular languages.
    Information Processing Letters, 52:339, 1994.

[Top]


In collections
  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.

  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.

  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.

[Top]


International conferences and workshops
  1. 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)

  2. 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.

  3. 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.

  4. 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.

  5. M.P. Bianchi, C. MEREGHETTI, B. Palano.
    Size lower bounds for quantum automata
    In 11th International Conference on Unconventional Computation and Natural Computation (UCNC 2013), Proceedings,
    Lecture Notes in Computer Science 7956, pp. 19-30, Springer 2013.

  6. Z. Bednárová, V. Geffert, C. MEREGHETTI, B. Palano.
    Boolean Language Operations on Nondeterministic Automata
    In 13th International Computer Science Symposium in Russia (CSR 2013), Proceedings,
    Lecture Notes in Computer Science 7913, pp. 100-111, Springer 2013.

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

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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, pp. 33-44, Osterreichischen Computer Gesellschaft, book@ocg.at series, 2010.

  13. 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.

  14. 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.

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

  16. 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.

  17. 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.

  18. 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.

  19. 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

  20. 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.

  21. 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.

  22. 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.

  23. 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.

  24. 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.

  25. 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 2003), Proceedings,
    Lecture Notes in Computer Science 2841, pp. 86-96, Springer 2003.

  26. 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.

  27. 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.

  28. 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.

  29. 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 2001), Proceedings,
    Lecture Notes in Computer Science, pp. 123-135, Springer 2001.

  30. 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.

  31. 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.

  32. 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.

  33. 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 1998), Proceedings,
    pp. 216-227, World Scientific, 1998.

  34. 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.

  35. 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.

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

[Top]


Editorships
  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.

  2. R. Freund, M. Holzer, C. MEREGHETTI, F. Otto, 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.

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

[Top]


Technical reports
  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.
    On entropy.
    Tech. Rep. n. 163-96, Dipartimento di Scienze dell'Informazione, Università di Milano, 1996.

[Top]


PhD thesis, MsC thesis

[Top]

Carlo Mereghetti
Dipartimento di Informatica
Università degli Studi di Milano
via Comelico 39, 20135 Milano, Italy
phone(fax) +39 02 503 16261(16276)
mail: mereghetti@di.unimi.it