Giovanni Pighizzini

Giovanni Pighizzini's AcademicInfluence.com Rankings

Giovanni Pighizzini

Computer Science

#12504

World Rank

#13365

Historical Rank

Theoretical Computer Science

#148

World Rank

#148

Historical Rank

Database

#9610

World Rank

#10144

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Giovanni Pighizzini's Degrees

PhD Computer Science University of Milan

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Giovanni Pighizzini Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Giovanni Pighizzini is an Italian theoretical computer scientist known for his work in formal language theory and particularly in state complexity of two-way finite automata. He earned his PhD in 1993 from the University of Milan, where he is a full professor since 2001. Pighizzini serves as the Steering Committee Chair of the annual Descriptional Complexity of Formal Systems academic conference since 2006.

(See a Problem?)

Giovanni Pighizzini's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Unary Language Operations, State Complexity and Jacobsthal's Function (2002) (123)
Optimal Simulations Between Unary Automata (1998) (74)
Converting Two-Way Nondeterministic Unary Automata into Simpler Automata (2003) (57)
Complementing Two-Way Finite Automata (2007) (55)
Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata (2001) (41)
Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds (2002) (38)
Two-Way Automata Simulations and Unary Languages (2000) (36)
How Hard Is Computing the Edit Distance? (2001) (34)
Complementing unary nondeterministic automata (2005) (29)
Descriptional Complexity of Formal Systems (2016) (26)
Limited Automata and Context-Free Languages (2015) (24)
Distances between languages and reflexivity of relations (2002) (24)
Limited Automata and Regular Languages (2013) (23)
Two-Way Finite Automata: Old and Recent Results (2012) (22)
Recent Trends in Descriptional Complexity of Formal Languages (2013) (22)
Nondeterministic One-Tape Off-Line Turing Machines and Their Time Complexity (2009) (21)
Optimal simulation of self-verifying automata by deterministic automata (2011) (20)
Two-way unary automata versus logarithmic space (2010) (20)
Two-Way Automata Characterizations of L/poly Versus NL (2012) (19)
An Optimal Lower Bound for Nonregular Languages (1994) (16)
Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages (1995) (15)
Deterministic Pushdown Automata and Unary Languages (2008) (15)
Asynchronous Automata Versus Asynchronous Cellular Automata (1994) (15)
Synthesis of nondeterministic asynchronous automata (1993) (14)
Tight Bounds on the Simulation of Unary Probabilistic Automata by Deterministic Automata (2001) (13)
Simulating finite automata with context-free grammars (2002) (13)
Sublogarithmic Bounds on Space and Reversals (1999) (13)
Descriptional complexity of bounded context-free languages (2007) (12)
Two-way automata making choices only at the endmarkers (2011) (12)
Unary Language Concatenation and Its State Complexity (2000) (12)
Minimal and Reduced Reversible Automata (2016) (11)
Operational State Complexity under Parikh Equivalence (2014) (10)
Weakly and Strongly Irreversible Regular Languages (2017) (9)
Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata (2012) (9)
On the Existence of Minimum Asynchronous Automata and on the Equivalence Problem for Unambiguous Regular Trace Languages (1994) (8)
On the Size of Unary Probabilistic and Nondeterministic Automata (2011) (8)
Limited Automata and Unary Languages (2019) (8)
On Languages Accepted with Simultaneous Complexity Bounds and Their Ranking Problem (1994) (8)
On the Existence of the Minimum Asynchronous Automaton and on Decision Problems for Unambiguous Regular Trace Languages (1988) (8)
Descriptional complexity of limited automata (2017) (7)
A Remark on Middle Space Bounded Alternating Turing Machines (1995) (7)
Non-self-embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata (2018) (6)
The complexity of computing maximal word functions (1991) (6)
Normal forms for unary probabilistic automata (2012) (6)
Automata and Reduced Words in the Free Group (2009) (6)
Two-Way Automata and One-Tape Machines - Read Only Versus Linear Time (2018) (5)
Strongly Limited Automata (2016) (5)
Pushdown Automata and Constant Height: Decidability and Bounds (2019) (4)
Non-self-embedding grammars and descriptional complexity (2017) (4)
Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata (2012) (4)
An optimal lower bound for nonregular languages : Information processing letters 50 (6) (27 June 1994) 289-292 (1994) (4)
String distances and intrusion detection: Bridging the gap between formal languages and computer security (2006) (4)
Probabilistic asynchronous automata (1996) (4)
Parikh's Theorem and Descriptional Complexity (2012) (3)
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata (2012) (3)
Recognizing sets of labelled acyclic graphs (1992) (3)
Limited Automata: Properties, Complexity and Variants (2019) (3)
Converting Self-verifying Automata into Deterministic Automata (2009) (3)
Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata (2010) (3)
Optimal State Reductions of Automata with Partially Specified Behaviors (2015) (3)
Unary automata simulations and cyclic languages (1999) (2)
Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, DCFS 2009, Magdeburg, Germany, July 6-9, 2009 (2009) (2)
Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines (2021) (2)
Guest Column: One-Tape Turing Machine Variants and Language Recognition (2015) (2)
Oblivious two-way finite automata: Decidability and complexity (2012) (2)
Universal Disjunctive Concatenation and Star (2015) (2)
Reversal Hierarchies for Small 2DFAs (2012) (2)
Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems: Preface (2009) (2)
Mathematical Foundations of Computer Science 2015 (2015) (2)
Corrigendum: An Optimal Lower Bound for Nonregular Languages (1994) (2)
Investigations on Automata and Languages Over a Unary Alphabet (2014) (2)
9th International Workshop on Descriptional Complexity of Formal Systems : High tatras, Slovakia, July 2o-22 2007 : Proceedings (2007) (2)
The World of Unary Languages: A Quick Tour (2003) (2)
Descriptional Complexity of Formal Systems (2015) (1)
On Inverse Operations and Their Descriptional Complexity (2012) (1)
Mathematical Foundations of Computer Science 2015 (2015) (1)
Unary Pushdown Automata and Auxiliary Space Lower Bounds (2000) (1)
One Pebble Versus log(n) Bits. (2009) (1)
Usefulness of Information and Unary Languages (2021) (1)
Weight-Reducing Turing Machines (2021) (1)
Operational State Complexity under Parikh Equivalence ? (Extended Abstract) (2014) (1)
Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, DCFS 2010, Saskatoon, Canada, 8-10th August 2010 (2010) (1)
Usefulness of information and decomposability of unary regular languages (2022) (1)
Probabilistic vs. Nondeterministic Unary Automata (2010) (1)
Algebraic and informational aspects of Zielonka's Theorem (1993) (1)
A Parallel Minimum Distance Error-Correcting Context-Free Parser (1992) (1)
Preface (1992) (0)
Efficient descriptions of unary languages by context-free grammars and pushdown automata (2002) (0)
F L ] 6 O ct 2 01 1 Two-Way Automata Making Choices Only at the Endmarkers Viliam Geffert (2018) (0)
Two-way finite automata with restricted nondeterminism and descriptional complexity Internship report − (2013) (0)
Preface to Martin Kutrib Festschrift (2021) (0)
Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems: Preface (2010) (0)
Recent Results Around the Sakoda and Sipser Question (2012) (0)
Preface (2017) (0)
A Pumping Condition for Ultralinear Languages (2007) (0)
Preface (2020) (0)
Performing Regular Operations with 1-Limited Automata (2022) (0)
Alberto Bertoni: A scientist and a friend (2017) (0)
How Hard is to Compute the Edit Distance (1995) (0)
Pushdown Automata Accepting in Constant Height: Decidability and Height Bounds - Extended Abstract (2019) (0)
Hot Current Topics of Descriptional Complexity (2021) (0)
Special section on Descriptional Complexity of Formal Systems (2019) (0)
Distances between Languages and Reeexivity of Relations 1 (2007) (0)
Tenth Workshop on Non-Classical Models of Automata and Applications, NCMA 2018, Košice, Slovakia, August 21-22, 2018 (2018) (0)
Two-Way Automata Characterizations of L/poly Versus NL (2014) (0)
Restricted Turing Machines and Language Recognition (2016) (0)
Descriptional Complexity of Formal Systems (2014) (0)
Editorial (2007) (0)
Limited Automata: Power and Complexity (text not included) (2019) (0)
Proceedings of the 13th international conference on Descriptional complexity of formal systems (2011) (0)
Descriptional Complexity of Formal Systems: 22nd International Conference, DCFS 2020, Vienna, Austria, August 24–26, 2020, Proceedings (2020) (0)
The Formal Language Theory Column (2015) (0)
One Pebble Versus epsilon * log n Bits (2009) (0)
On some succinct representations of regular languages : extended abstract (2018) (0)
Editorial (2010) (0)
1-Limited Automata: Witness Languages and Techniques (2022) (0)
Preface (2021) (0)

This paper list is powered by the following services:

Other Resources About Giovanni Pighizzini

What Schools Are Affiliated With Giovanni Pighizzini?

Giovanni Pighizzini is affiliated with the following schools:

Giovanni Pighizzini's Academic­Influence.com Rankings

Giovanni Pighizzini's Degrees

Similar Degrees You Can Earn

Why Is Giovanni Pighizzini Influential?

Giovanni Pighizzini's Published Works

Published Works

Other Resources About Giovanni Pighizzini

What Schools Are Affiliated With Giovanni Pighizzini?

Giovanni Pighizzini's AcademicInfluence.com Rankings