Recent Papers by Giovanni Pighizzini

G. Pighizzini and L. Prigioniero.
Pushdown automata and constant height: decidability and bounds.
Acta Informatica, 2022. In Press.
B. Guillon, G. Pighizzini, L. Prigioniero, D. Průša.
Converting nondeterministic two-way automata into small deterministic linear-time machines.
Information and Computation, 104938, 2022. In Press.
G. Pighizzini, B. Rovan, Š. Sádovský.
Usefulness of information and decomposability of unary regular languages.
Information and Computation, 104868, 2022. In Press.
G. Pighizzini, L. Prigioniero, Š. Sádovský.
1-Limited Automata: Witness Languages and Techniques.
Journal of Automata, Languages and Combinatorics, 27(1-3), 229-244, 2022.
G. Pighizzini, L. Prigioniero, Š. Sádovský.
Performing Regular Operations with 1-Limited Automata.
In Proceedings of DLT 2022,
Lecture Notes in Computer Science 13257, pages 239-250, 2022.
B. Guillon, G. Lavado, G. Pighizzini, L. Prigioniero.
Weakly and Strongly Irreversible Regular Languages.
International Journal of Foundations of Computer Science, 33(3&4), 263-284, 2022.
M. Kutrib, N. Moreira, G. Pighizzini, R. Reis.
Hot Current Topics of Descriptional Complexity.
In Advancing Research in Information and Communication Technology - IFIP's Exciting First 60+ Years,
IFIP Advances in Information and Communication Technology 600, pages 3-28, 2021.
G. Pighizzini, B. Rovan, Š. Sádovský.
Usefulness of Information and Unary Languages.
In Proceedings of LATA 2021,
Lecture Notes in Computer Science 12638, pages 131-142, 2021.
G. Pighizzini and L. Prigioniero.
Non-Self-Embedding Grammars and Descriptional Complexity.
Fundamenta Informaticae, 180(1-2), 103-122, 2021.
B. Guillon, G. Pighizzini, L. Prigioniero.
Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata.
International Journal of Foundations of Computer Science, 31(8), 1133-1157, 2020.
G. Pighizzini and L. Prigioniero.
Pushdown Automata and Constant Height: Decidability and Bounds.
In Proceedings of DCFS 2019,
Lecture Notes in Computer Science 11612, pages 260-271, 2019.
G. Pighizzini.
Limited Automata: Properties, Complexity and Variants.
In Proceedings of DCFS 2019,
Lecture Notes in Computer Science 11612, pages 57-73, 2019.
Slides of the presentation: Full version - Handout
G. Pighizzini and L. Prigioniero.
Limited automata and unary languages.
Information and Computation, 266, 60-74, 2019.
B. Guillon, G. Pighizzini, L. Prigioniero, D. Průša.
Two-way automata and one-tape machines: read only versus linear time.
In Proceedings of DLT 2018,
Lecture Notes in Computer Science 11088, pages 366-378, 2018.
B. Guillon, G. Pighizzini, L. Prigioniero.
Non-self-embedding grammars, constant height pushdown automata and limited automata.
In Proceedings of CIAA 2018,
Lecture Notes in Computer Science 10977, pages 186-197, 2018.
M. Kutrib, G. Pighizzini, M. Wendlandt.
Descriptional complexity of limited automata.
Information and Computation, 259(2), 259-276, 2018.
G.J. Lavado, G. Pighizzini, and L. Prigioniero.
Weakly and Strongly Irreversible Regular Languages.
In Proceedings of AFL 2017,
Electronic Proceedings in Theoretical Computer Science, 252, 143-156, 2017.
G. Pighizzini and L. Prigioniero.
Non-Self-Embedding Grammars and Descriptional Complexity.
In Proceedings of the 9th Workshop Non-Classical Models of Automata and Applications (NCMA 2017), 197-209, 2017.
G. Pighizzini and L. Prigioniero.
Limited Automata and Unary Languages.
In Proceedings of DLT 2017,
Lecture Notes in Computer Science 10396, pages 308-219, 2017.
Slides of the presentation: Full version - Handout
P. Campadelli, M. Goldwurm, and G. Pighizzini.
Alberto Bertoni: A scientist and a friend.
Theoretical Computer Science, 664, 2-11, 2017.
N. Moreira, G. Pighizzini, and R. Reis.
Optimal state reductions of automata with partially specified behaviors.
Theoretical Computer Science, 658, 235-245, 2017.
G. Pighizzini.
Strongly Limited Automata.
Fundamenta Informaticae, 148(3-4), 369-392, 2016.
G.J. Lavado, G. Pighizzini, and L. Prigioniero.
Minimal and Reduced Reversible Automata.
In Proceedings of DCFS 2016,
Lecture Notes in Computer Science 9777, pages 168-179, 2016.
An extended version is available on arXiv.
G. Pighizzini.
Restricted Turing Machines and Language Recognition.
In Proceedings of LATA 2016,
Lecture Notes in Computer Science 9618, pages 42-56, 2016.
Slides of the presentation: Full version Part I Part II- Handout Part I Part II
G. Pighizzini.
Investigations on Automata and Languages Over a Unary Alphabet.
International Journal of Foundations of Computer Science, 26(7), 827-850, 2015.
G. Pighizzini.
Guest Column: One-Tape Turing Machine Variants and Language Recognition.
SIGACT News, 46(3), 37-55, 2015.
Also available on arXiv.
N. Moreira, G. Pighizzini, and R. Reis.
Universal Disjunctive Concatenation and Star.
In Proceedings of DCFS 2015,
Lecture Notes in Computer Science 9118, pages 197-208, 2015.
C.A. Kapoutsis and Giovanni Pighizzini.
Two-Way Automata Characterizations of L/poly versus NL.
Theory of Computing Systems, 56(4), 662-685, 2015.
G. Pighizzini and A. Pisoni.
Limited Automata and Context-Free Languages.
Fundamenta Informaticae, 136(1-2), 157-176, 2015.
N. Moreira, G. Pighizzini, and R. Reis.
Optimal State Reductions of Automata with Partially Specified Behaviors.
In Proceedings of SOFSEM 2015,
Lecture Notes in Computer Science 8939, pages 339-351, 2015.
Slides of the presentation: Full version - Handout
G. Pighizzini and A. Pisoni.
Limited Automata and Regular Languages.
International Journal of Foundations of Computer Science , 25(7), 897-916, 2014.
V. Geffert, B. Guillon, and G. Pighizzini.
Two-way automata making choices only at the endmarkers.
Information and Computation, 239, 71-86, 2014.
M. Kutrib, A. Malcher, and G. Pighizzini.
Oblivious two-way finite automata: Decidability and complexity.
Information and Computation, 237, 294-302, 2014.
G.J. Lavado, G. Pighizzini, and S. Seki.
Operational State Complexity under Parikh Equivalence.
In Proceedings of DCFS 2014,
Lecture Notes in Computer Science 8614, pages 294-305, 2014.
G. Pighizzini.
Investigations on Automata and Languages over a Unary Alphabet.
In Proceedings of CIAA 2014,
Lecture Notes in Computer Science 8587, pages 42-57, 2014.
Slides of the presentation: Full version - Handout
G. Pighizzini.
Strongly Limited Automata.
In Proceedings of the 6th Workshop Non-Classical Models for Automata and Applications (NCMA 2014), 191-206, 2014.
Slides of the presentation: Full version - Handout
M. Kutrib and G. Pighizzini.
Recent Trends in Descriptional Complexity of Formal Languages.
Bulletin of the EATCS 111, 70-86, 2013.
G. Pighizzini.
Two-Way Finite Automata: Old and Recent Results.
Fundamenta Informaticae, 126(2-3), 225-246, 2013.
G. Pighizzini and A. Pisoni.
Limited Automata and Context-Free Languages.
In Proceedings of the 5th Workshop Non-Classical Models for Automata and Applications (NCMA 2013), 209-223, 2013.
Slides of the presentation: Full version - Handout
G.J. Lavado, G. Pighizzini, and S. Seki.
Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata.
Information and Computation, 228-229, 1-15, 2013.
G. Pighizzini and A. Pisoni.
Limited Automata and Regular Languages.
In Proceedings of DCFS 2013,
Lecture Notes in Computer Science 8031, pages 253-264, 2013.
Slides of the presentation: Full version - Handout
A. Malcher and G. Pighizzini.
Descriptional Complexity of Bounded Context-Free Languages.
Information and Computation, 227, 1-20, 2013.
G. Pighizzini.
Two-Way Finite Automata: Old and Recent Results.
In Proceedings of Automata and JAC 2012,
EPTCS 90, pages 3-20, 2012.
Slides of the presentation: Full version - Handout
G. Pighizzini.
Recent Results around the Sakoda and Sipser Question.
In Proceedings of the 4rd Workshop Non-Classical Models for Automata and Applications (NCMA 2012), pages 27-32, 2012.
Slides of the presentation: Full version - Handout
M.P. Bianchi and G. Pighizzini.
Normal forms for unary probabilistic automata.
RAIRO Theoretical Informatics and Applications, 2012.
C.A. Kapoutsis and Giovanni Pighizzini.
Reversal Hierarchies for Small 2DFAs.
In Proceedings of MFCS 2012,
Lecture Notes in Computer Science 7464, pages 554-565, 2012.
G.J. Lavado, G. Pighizzini, and S. Seki.
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata.
In Proceedings of DLT 2012,
Lecture Notes in Computer Science 7410, pages 284-295, 2012.
Slides of the presentation: Full version - Handout
M.P. Bianchi, M. Holzer, S. Jakobi, and G. Pighizzini.
On Inverse Operations and Their Descriptional Complexity.
In Proceedings of DCFS 2012,
Lecture Notes in Computer Science, 7386, pages 89-102, 2012.
C.A. Kapoutsis and Giovanni Pighizzini.
Two-Way Automata Characterizations of L/poly versus NL.
In Proceedings of CSR 2012,
Lecture Notes in Computer Science 7353, pages 217-228, 2012.
Best Paper Award
Slides of the presentation: Full version - Handout
M. Kutrib, A. Malcher , and G. Pighizzini.
Oblivious Two-Way Finite Automata: Decidability and Complexity.
In Proceedings of LATIN 2012,
Lecture Notes in Computer Science 7256, pages 518-529, 2012.
V. Geffert, B. Guillon, and G. Pighizzini.
Two-Way Automata Making Choices Only at the Endmarkers.
In Proceedings of LATA 2012,
Lecture Notes in Computer Science 7183, pages 264-276, 2012.
An extended report is also available.
Slides of the presentation: Full version - Handout
V. Geffert and G. Pighizzini.
Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata.
Algorithmica, 63(3), 571-587, 2012.
G.J. Lavado and G. Pighizzini.
Parikh's Theorem and Descriptional Complexity.
In SOFSEM 2012: Theory and Practice of Computer Science,
Lecture Notes in Computer Science 7147, pages 361-372, 2012.
Slides of the presentation: Full version - Handout
M.P. Bianchi, C. Mereghetti, B. Palano, and G. Pighizzini.
On the Size of Unary Probabilistic and Nondeterministic Automata.
Fundamenta Informaticae, 112(2-3), 119-135, 2011.
M.P. Bianchi and G. Pighizzini.
Normal Forms for Unary Probabilistic Automata.
In Proceedings of the 3rd Workshop Non-Classical Models for Automata and Applications (NCMA 2011), 89-102, 2011.
V. Geffert and G. Pighizzini.
Two-way unary automata versus logarithmic space.
Information and Computation, 209, 1016-1025, 2011.
G. Jirásková and G. Pighizzini.
Optimal simulation of self-verifying automata by deterministic automata.
Information and Computation, 209, 528-535, 2011.
V. Geffert, C. Mereghetti, and G. Pighizzini.
One Pebble Versus epsilon * log n Bits.
Fundamenta Informaticae, 104(1-2), 55-69, 2010.
V. Geffert and G. Pighizzini.
Two-Way Unary Automata versus Logarithmic Space.
In Developments in Language Theory 2010, Proceedings,
Lecture Notes in Computer Science 6224, pages 197-208, 2010.
V. Geffert and G. Pighizzini.
Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata.
In Proceedings of LATIN 2010.
Lecture Notes in Computer Science 6034, pages 196-207, 2010.
Slides of the presentation.
T. Ang, G. Pighizzini, N. Rampersad, J. Shallit .
Automata and Reduced Words in the Free Group.
Preprint, 2009.
V. Geffert, C. Mereghetti, and G. Pighizzini.
One pebble versus log n bits.
In Proceedings of the Workshop Non-Classical Models for Automata and Applications (NCMA), 121-133, 2009.
G. Pighizzini.
Deterministic Pushdown Automata and Unary Languages.
International Journal of Foundations of Computer Science , 20(4), 629-645, 2009.
G. Pighizzini.
Nondeterministic one-tape off-line Turing machines and their time complexity.
Journal of Automata, Languages and Combinatorics 14:107-124, 2009.
Presented at the worskhop ABCDays on List Automata, Forgetting Automata, and Restarting Automata, Prague, 2009.
Slides of the presentation.
G. Jirásková and G. Pighizzini.
Converting Self-Verifying Automata into Deterministic Automata.
In Proceedings of LATA 2009.
Lecture Notes in Computer Science 5457, pages 458-468, 2009.
Slides of the presentation.
G. Pighizzini.
Deterministic Pushdown Automata and Unary Languages.
In Proceedings of the 13th Conference on Implementation and Application of Automata, CIAA 2008.
Lecture Notes in Computer Science 5148, pages 232-241, 2008.
Slides of the presentation.
E. Magalini and G. Pighizzini.
A pumping condition for ultralinear languages.
International Journal of Foundations of Computer Science , 18(6), 1303-1312, 2007.
A. Malcher and G. Pighizzini.
Descriptional Complexity of Bounded Context-Free Languages.
In Developments in Language Theory 2007, Proceedings,
Lecture Notes in Computer Science 4588, pages 312-323, 2007.
V. Geffert, C. Mereghetti, and G. Pighizzini.
Complementing Two-Way Finite Automata.
Information and Computation, 205, 1173-1187, 2007.
D. Bruschi and G. Pighizzini.
String distances and intrusion detection: Bridging the gap between formal languages and computer security.
RAIRO Theoretical Informatics and Applications 40, 303-313, 2006.
V. Geffert, C. Mereghetti, and G. Pighizzini.
Complementing Two-Way Finite Automata.
In Developments in Language Theory 2005, Proceedings,
Lecture Notes in Computer Science 3572, pages 260-271, 2005.
F. Mera and G. Pighizzini.
Complementing Unary Nondeterministic Automata.
Theoretical Computer Science 330:349-360, 2005.
Presented at the Workshop Descriptional Complexity of Formal Systems (DCFS 2003), MTA SZTAKI, Budapest, 2003.
V. Geffert, C. Mereghetti, and G. Pighizzini.
Converting Two-Way Nondeterministic Unary Automata into Simpler Automata.
Theoretical Computer Science 295:189-203, 2003.
M. Domaratzki , G. Pighizzini, and J. Shallit.
Simulating finite automata with context-free grammars.
Information Processing Letters 84(6): 339-344, 2002.
G. Pighizzini, J. Shallit, M.-w. Wang.
Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds.
Journal of Computer and System Sciences 65: 393-414, 2002.
C. Choffrut and G. Pighizzini.
Distances between languages and reflexivity of relations.
Theoretical Computer Science 286:117-138, 2002.
G. Pighizzini and J. Shallit.
Unary Language Operations, State Complexity and Jacobsthal's Function.
International Journal of Foundations of Computer Science 13,1: 145-159, 2002.
V. Geffert, C. Mereghetti, and G. Pighizzini.
Converting Two-Way Nondeterministic Unary Automata into Simpler Automata.
In Mathematical Foundations of Computer Science 2001, Proceedings,
Lecture Notes in Computer Science 2136, pages 398-407, 2001.
C. Mereghetti, B. Palano and G. Pighizzini.
Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata.
RAIRO Theoretical Informatics and Applications 5:455-490, 2001.
Presented at the workshop Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS 2001), Vienna, Austria, 2001.
C. Mereghetti and G. Pighizzini.
Optimal Simulations Between Unary Automata.
SIAM Journal on Computing 30:1976-1992, 2001.
G. Pighizzini.
How Hard Is Computing the Edit Distance?
Information and Computation, 165:1-13, 2001.
M. Milani and G. Pighizzini.
Tight bounds on the simulation of unary probabilistic automata by deterministic automata.
Journal of Automata, Languages and Combinatorics 6:481-492, 2001.
Presented at the worskhop Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS2000), London, Ontario, Canada, 2000.
G. Pighizzini.
Unary language concatenation and its state complexity.
Implementation and Application of Automata (CIAA 2000), London, Ontario, Canada, 2000,
Lecture Notes in Computer Science 2088, pages 252-262, 2001.
G. Pighizzini.
Unary Pushdown Automata and Auxiliary Space Lower Bounds.
In Mathematical Foundations of Computer Science 2000, Proceedings,
Lecture Notes in Computer Science 1893, pages 599-608, 2000.
C. Mereghetti and G. Pighizzini.
Two-Way Automata Simulations and Unary Languages.
Journal of Automata, Languages and Combinatorics 5:287-300, 2000.
C. Mereghetti and G. Pighizzini.
Unary Automata Simulations and Cyclic Languages.
Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS'99)
Magdeburg, Germany, 1999.
V. Geffert , C. Mereghetti and G. Pighizzini.
Sublogarithmic Bounds on Space and Reversals.
SIAM Journal on Computing 28:325--340, 1999.
C. Mereghetti and G. Pighizzini.
Optimal Simulations Between Unary Automata.
In Symposium on Theoretical Aspects of Computer Science 1998, Proceedings,
Lecture Notes in Computer Science 1373, pages 139-149, 1998.
A. Bertoni, C. Mereghetti, and G. Pighizzini.
Space and Reversals Complexity of Nonregular Languages.
Manuscript, 1998.
C. Choffrut and G. Pighizzini.
Distances between languages and reflexivity of relations.
In Mathematical Foundations of Computer Science 1997, Proceedings,
Lecture Notes in Computer Science 1295, pages 199-208, 1997.
S. Jesi, G. Pighizzini, and N. Sabadini.
Probabilistic asynchronous automata.
Mathematical Systems Theory29:5-31, 1996.
C. Mereghetti and G. Pighizzini.
A remark on middle space bounded alternating Turing machines.
Information Processing Letters 56:229-232, 1995.
A. Bertoni, C. Mereghetti, and G. Pighizzini.
Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages.
In Mathematical Foundations of Computer Science 1995, Proceedings,
Lecture Notes in Computer Science 969, pages 309-318, 1995.
G. Pighizzini.
How hard is to compute the edit distance.
In Fundamentals of Computation Theory 1995, Proceedings,
Lecture Notes in Computer Science 865, pages 383-392, 1995.
D. Bruschi and G. Pighizzini.
A parallel version of Earley's algorithm.
Tech. Rep. 114-94. Dipartimento di Scienze dell'Informazione. Univ. of Milan, 1994.
A. Bertoni, C. Mereghetti, and G. Pighizzini.
An optimal lower bound for nonregular languages.
Information Processing Letters 50:289-292, 1994. Corrigendum. ibid., 52:339, 1994.
A. Bertoni, C. Mereghetti, and G. Pighizzini.
On Languages Accepted with Simultaneous Complexity Bounds and Their Ranking Problems.
In Mathematical Foundations of Computer Science 1994, Proceedings,
Lecture Notes in Computer Science 841, pages 245-255, 1994.
G. Pighizzini.
Asynchronous Automata versus Asynchronous Cellular Automata.
Theoretical Computer Science 132:74-207, 1994.
D. Bruschi, G. Pighizzini, and N. Sabadini.
On the Existence of Minimum Asynchronous Automata and on the Equivalence Problem for Unambiguous Regular Trace Languages.
Information and Computation 108:262-285, 1994.
A. Bertoni, G. Mauri, G. Pighizzini, and N. Sabadini.
Algebraic and informational aspects of Zielonka's Theorem.
In C. Bonzini, A. Cherubini, and C. Tibiletti (eds.), Semigroups, pages 17-26, World Scientific, 1993.
E. Allender, D. Bruschi, and G. Pighizzini.
The complexity of computing maximal word functions.
Computational complexity 3:368-391, 1993.
G. Pighizzini.
Synthesis of Nondeterministic Asynchronous Automata.
In M. Droste and Y. Gurevich (eds.), Semantics of Programming Languages and Model Theory,
Algebra, Logic and Applications, vol. 5, Gordon and Breach Science Publ., OPA (Amsterdam), pages 109-126, 1993.
G. Pighizzini.
A parallel Minimum Distance Error-Correcting Context-Free Parser.
In A. Marchetti Spaccamela, P. Mentrasti, M. Venturini Zilli (eds.),
Theoretical Computer Science, Proceedings of the Fourth Italian Conference,
World Scientific, pages 305-316, 1992.
P. Bonizzoni, G. Mauri, G. Pighizzini, and N. Sabadini.
Recognizing Sets of Labelled Acyclic Graphs.
In A. Podelski and M. Nivat (eds.),
Tree automata and Languages,
Elsevier Publishers (North Holland), pages 201-224, 1992.

August 2022, Giovanni Pighizzini