Carlo Mereghetti

According to our database, Carlo Mereghetti authored at least 73 papers between 1994 and 2024.

Collaborative distances:

• Dijkstra number of five.
• Erdős number of three.

2024

On Properties of Languages Accepted by Deterministic Pushdown Automata with Translucent Input Letters.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano, Priscilla Raucci, Matthias Wendlandt

Proceedings of the Implementation and Application of Automata, 2024

Computational Power of Opaque Robots.

Caterina Feletti, Lucia Mambretti, Carlo Mereghetti, Beatrice Palano

Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks, 2024

Deterministic Pushdown Automata with Translucent Input Letters.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano, Priscilla Raucci, Matthias Wendlandt

Proceedings of the Developments in Language Theory - 28th International Conference, 2024

2023

Iterated uniform finite-state transducers on unary languages.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., August, 2023

Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

J. Autom. Lang. Comb., 2023

Latvian Quantum Finite State Automata for Unary Languages.

Carlo Mereghetti, Beatrice Palano, Priscilla Raucci

Proceedings of the 13th International Workshop on Non-Classical Models of Automata and Applications, 2023

𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots.

Caterina Feletti, Carlo Mereghetti, Beatrice Palano

Proceedings of the 27th International Conference on Principles of Distributed Systems, 2023

2022

Descriptional complexity of iterated uniform finite-state transducers.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Inf. Comput., 2022

Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Fundam. Informaticae, 2022

Uniform Circle Formation for Fully Semi-, and Asynchronous Opaque Robots with Lights.

Caterina Feletti, Carlo Mereghetti, Beatrice Palano, Priscilla Raucci

Proceedings of the 23rd Italian Conference on Theoretical Computer Science, 2022

2021

Guest Column: Quantum Finite Automata: From Theory to Practice.

Carlo Mereghetti, Beatrice Palano

SIGACT News, 2021

The descriptional power of queue automata of constant length.

Sebastian Jakobi, Katja Meckel, Carlo Mereghetti, Beatrice Palano

Acta Informatica, 2021

Iterated Transduction on Unary Languages.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Proceedings of the 22nd Italian Conference on Theoretical Computer Science, 2021

2020

Photonic Realization of a Quantum Finite Automaton.

Carlo Mereghetti, Beatrice Palano, Simone Cialdi, Valeria Vento, Matteo G. A. Paris, Stefano Olivares

CoRR, 2020

Deterministic and Nondeterministic Iterated Uniform Finite-State Transducers: Computational and Descriptional Power.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Proceedings of the Beyond the Horizon of Computability, 2020

2019

Iterated Uniform Finite-State Transducers.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Proceedings of the 20th Italian Conference on Theoretical Computer Science, 2019

2018

Uniform Circle Formation for Swarms of Opaque Robots with Lights.

Caterina Feletti, Carlo Mereghetti, Beatrice Palano

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2018

2017

Quantum finite automata: Advances on Bertoni's ideas.

Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2017

Boolean language operations on nondeterministic automata with a pushdown of constant height.

Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano

J. Comput. Syst. Sci., 2017

2015

Deterministic input-driven queue automata: Finite turns, decidability, and closure properties.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano, Matthias Wendlandt

Theor. Comput. Sci., 2015

On the Power of One-Way Automata with Quantum and Classical States.

Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano

Int. J. Found. Comput. Sci., 2015

2014

Size lower bounds for quantum automata.

Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2014

Removing nondeterminism in constant height pushdown automata.

Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Inf. Comput., 2014

Complexity of Promise Problems on Classical and Quantum Automata.

Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano

Proceedings of the Computing with New Resources, 2014

2013

Input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties.

Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano, Matthias Wendlandt

Proceedings of the Implementation and Application of Automata, 2013

Queue Automata of Constant Length.

Sebastian Jakobi, Katja Meckel, Carlo Mereghetti, Beatrice Palano

Proceedings of the Descriptional Complexity of Formal Systems, 2013

A Direct Construction of Finite State Automata for Pushdown Store Languages.

Viliam Geffert, Andreas Malcher, Katja Meckel, Carlo Mereghetti, Beatrice Palano

Proceedings of the Descriptional Complexity of Formal Systems, 2013

2012

Descriptional complexity of two-way pushdown automata with restricted head reversals.

Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2012

The size-cost of Boolean operations on constant height deterministic pushdown automata.

Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2012

Descriptional Complexity of Pushdown Store Languages.

Andreas Malcher, Katja Meckel, Carlo Mereghetti, Beatrice Palano

J. Autom. Lang. Comb., 2012

On Inverse Operations and Their Descriptional Complexity.

Maria Paola Bianchi, Markus Holzer, Sebastian Jakobi, Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini

J. Autom. Lang. Comb., 2012

Special Issue: Non-Classical Models of Automata and Applications III (NCMA-2011).

Rudolf Freund, Markus Holzer, Carlo Mereghetti, Friedrich Otto, Beatrice Palano

RAIRO Theor. Informatics Appl., 2012

First-order logics: some characterizations and closure properties.

Christian Choffrut, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Acta Informatica, 2012

2011

On the Size of Unary Probabilistic and Nondeterministic Automata.

Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini

Fundam. Informaticae, 2011

2010

Trace monoids with idempotent generators and measure-only quantum automata.

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Nat. Comput., 2010

Sublinearly Space Bounded Iterative Arrays.

Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Int. J. Found. Comput. Sci., 2010

More concise representation of regular languages by automata and regular expressions.

Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Inf. Comput., 2010

One Pebble Versus epsilon * log n Bits.

Viliam Geffert, Giovanni Pighizzini, Carlo Mereghetti

Fundam. Informaticae, 2010

Probabilistic vs. Nondeterministic Unary Automata.

Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini

Proceedings of the Second Workshop on Non-Classical Models for Automata and Applications - NCMA 2010, Jena, Germany, August 23, 2010

On the Expressive Power of FO[ + ].

Christian Choffrut, Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Proceedings of the Language and Automata Theory and Applications, 2010

Quantum Automata and Periodic Events.

Carlo Mereghetti, Beatrice Palano

Proceedings of the Scientific Applications of Language Methods., 2010

2009

One Pebble Versus log(n) Bits.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Proceedings of the Workshop on Non-Classical Models for Automata and Applications - NCMA 2009, Wroclaw, Poland, August 31, 2009

Logical Description of Structured and XML Languages.

Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Proceedings of the Theoretical Computer Science, 11th Italian Conference, 2009

2008

Testing the Descriptional Power of Small Turing Machines on Nonregular Language Acceptance.

Carlo Mereghetti

Int. J. Found. Comput. Sci., 2008

Recent results on iterative arrays with small space bounds.

Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Proceedings of the Automata 2008: Theory and Applications of Cellular Automata, 2008

2007

Quantum automata for some multiperiodic languages.

Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2007

Complementing two-way finite automata.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Inf. Comput., 2007

The Descriptional Power of Sublogarithmic Resource Bounded Turing Machines.

Carlo Mereghetti

Proceedings of the 9th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2007, High Tatras, Slovakia, July 20, 2007

2006

Some formal tools for analyzing quantum automata.

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2006

The complexity of minimum difference cover.

Carlo Mereghetti, Beatrice Palano

J. Discrete Algorithms, 2006

Quantum finite automata with control language.

Carlo Mereghetti, Beatrice Palano

RAIRO Theor. Informatics Appl., 2006

2005

Small size quantum automata recognizing some regular languages.

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2005

Some formal methods for analyzing quantum automata.

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30, 2005

2003

Converting two-way nondeterministic unary automata into simpler automata.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Theor. Comput. Sci., 2003

Golomb Rulers And Difference Sets For Succinct Quantum Automata.

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Int. J. Found. Comput. Sci., 2003

Lower Bounds on the Size of Quantum Automata Accepting Unary Languages.

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Proceedings of the Theoretical Computer Science, 8th Italian Conference, 2003

Quantum Computing: 1-Way Quantum Automata.

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

The World of Unary Languages: A Quick Tour

Carlo Mereghetti, Giovanni Pighizzini

Proceedings of the Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, 2003

2002

The Parallel Complexity of Deterministic and Probabilistic Automata.

Carlo Mereghetti, Beatrice Palano

J. Autom. Lang. Comb., 2002

On the Size of One-way Quantum Finite Automata with Periodic Behaviors.

Carlo Mereghetti, Beatrice Palano

RAIRO Theor. Informatics Appl., 2002

2001

Optimal Simulations between Unary Automata.

Carlo Mereghetti, Giovanni Pighizzini

SIAM J. Comput., 2001

Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata.

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini

RAIRO Theor. Informatics Appl., 2001

The 224 non-chordal graphs on less than 10 vertices whose chromatic polynomials have no complex roots.

Ottavio M. D'Antona, Carlo Mereghetti, Fabio Zamparini

Discret. Math., 2001

Upper Bounds on the Size of One-Way Quantum Finite Automata.

Carlo Mereghetti, Beatrice Palano

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

On the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata.

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini

Proceedings of the Third International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures - DCAGRS 2001, Vienna, Austria, July 20, 2001

2000

Two-Way Automata Simulations and Unary Languages.

Carlo Mereghetti, Giovanni Pighizzini

J. Autom. Lang. Comb., 2000

Threshold circuits for iterated matrix product and powering.

Carlo Mereghetti, Beatrice Palano

RAIRO Theor. Informatics Appl., 2000

1998

Sublogarithmic Bounds on Space and Reversals.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

SIAM J. Comput., 1998

1995

A Remark on Middle Space Bounded Alternating Turing Machines.

Carlo Mereghetti, Giovanni Pighizzini

Inf. Process. Lett., 1995

Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages.

Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994

Corrigendum: An Optimal Lower Bound for Nonregular Languages.

Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini

Inf. Process. Lett., 1994

An Optimal Lower Bound for Nonregular Languages.

Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini

Inf. Process. Lett., 1994

On Languages Accepted with Simultaneous Complexity Bounds and Their Ranking Problem.

Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994