Selected Talks by Giovanni Pighizzini

Selected Talks by Giovanni Pighizzini

(since 2007)

Turn Complexity and Bounded Languages.
17th International Conference on Automata and Formal Languages (AFL 2026), Kosice, Slovakia.
September 9th, 2026
Full version
Turn Complexity of Context-free Languages, Pushdown and One-Counter Automata.
29th International Conference on Developments in Language Theory (DLT 2025), Seoul, South Korea.
August 19th, 2025
Full version
Push Complexity: Optimal Bounds and Unary Inputs.
28th International Conference on Implementation and Application of Automata (CIAA 2024), Akita, Japan.
September 4th, 2024
Full version
Once-Marking and Always-Marking 1-Limited Automata.
16th International Conference on Automata and Formal Languages (AFL 2023), Eger, Hungary.
September 6th, 2023
Full version
Two-way Automata and Related Models: Power and Complexity.
La Primavera dell'Informatica Teorica, Italian Chapter of the EATCS
June 23rd, 2022
Full version
Limited Automata: Power and Complexity.
20th Italian Conference on Theoretical Computer Science (ICTCS 2019), Como, Italy.
September 11th, 2019
Full version
Limited Automata: Properties, Complexity and Variants.
21th International Conference on Descriptional Complexity of Formal Systems (DCFS 2019), Kosice, Slovakia.
July 17th, 2019
Full version
Limited Automata and Unary Languages.
21th International Conference on Developments in Language Theory (DLT 2017), Liège, Belgium.
August 9th, 2017.
Full version
Restricted Turing Machines and Language Recognition. Part I - Part II
10th International Conference on Language and Automata Theory and Applications (LATA 2016), Prague, Czech Republic
March 17th-March 18th, 2016
Full version: Part I - Part II
Investigations on Automata and Languages over a Unary Alphabet.
Formal Languages and Automata: Models, Methods, and Applications, Napoli, Italy.
January 15th, 2016.
Full version
Optimal State Reductions of Automata with Partially Specified Behaviors.
41th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), Pec pod Sněžkou,5 Czech Republic.
January 27th, 2015.
Full version
Two-Way Automata and Descriptional Complexity.
IFIP Conference on Theoretical Computer Science TCS 2014, Rome, Italy.
September 3rd, 2014.
Full version
Investigations on Automata and Languages over a Unary Alphabet.
19th International Conference Implementation and Application of Automata (CIAA 2014), Giessen, Germany.
August 1st, 2014.
Full version
Strongly Limited Automata.
6th Workshop on Non-Classical Models for Automata and Applications (NCMA 2014), Kassel, Germany.
July 28th, 2014.
Full version
Automi two-way e complessità descrizionale.
Dipartimento di Matematica e Informatica
Università di Palermo.
March 6th, 2014.
Full version
Abstract
Parikh Equivalence and Descriptional Complexity.
Workshop on Descriptional and Computational Complexity of Formal Languages, Porto, Portugal.
January 24th, 2014.
Full version
Limited Automata and Descriptional Complexity.
Workshop PRIN 2013, Milano.
November 28th, 2013.
Full version
Limited Automata and Context-Free Languages.
5th Workshop on Non-Classical Models for Automata and Applications (NCMA 2013), Umeå, Sweden.
August 13th, 2013.
Full version
Limited Automata and Regular Languages.
15th Workshop on Descriptional Complexity of Formal Systems (DCFS 2013), London, Ontario, Canada.
July 23rd, 2013.
Full version
Two-way Finite Automata: Old and Recent Results.
Automata and JAC 2012, La Marana, Corsica, France.
September 19th, 2012.
Abstract
Full version
Determinism versus Nondeterminism in Two-way Finite Automata. Recent Results around the Sakoda and Sipser Question.
4th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2012), Fribourg, Switzerland.
August 24th, 2012.
Full version
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata.
16th International Conference on Developments in Language Theory (DLT 2012), Taipei, Taiwan.
August 15th, 2012.
Full version
Two-Way Automata Characterizations of L/poly versus NL.
7th International Computer Science Symposium in Russia (CSR 2012), Nizhny Novgorod, Russia.
Best paper award
July 5th, 2012.
Full version
Two-Way Automata Making Choices Only at the Endmarkers.
6th International Conference on Language and Automata Theory and Applications (LATA 2012), A Coruña, Spain.
March 7th, 2012.
Full version
Parikh's Theorem and Descriptional Complexity.
38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), Spindleruv Mlýn, Czech Republic.
January 23th, 2012.
Full version
Two-way Unary Automata versus Logarithmic Space.
LIAFA, Paris, France.
December 9th, 2011.
Abstract
New Results Related to the Sakoda and Sipser Question.
Institute of Computer Science, P.J. Safarik University, Kosice, Slovakia.
November 7th, 2011.
Abstract
Risultati recenti intorno al problema di Sakoda e Sipser.
DSI, Milano.
October 20th, 2011.
Abstract
Descriptional Complexity and Regular Languages.
Modèles de Calcul, Complexité & Combinatoire,
Laboratorie I3S, Université Nice Sophia Antipolis
May 19th, 2011.
Abstract
Removing Nondeterminism from Two-Way Automata.
Invited talk at Automata, Semigroups and Applications' days, Porto, Portugal.
June 22th, 2010.
Abstract
Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata.
9th Latin American Symposium LATIN 2010: Theoretical Informatics, Oaxaca, Mexico.
April 20th, 2010.
Converting Self-Verifying Automata into Deterministic Automata.
3rd International Conference Language and Automata Theory and Applications, LATA 2009, Tarragona, Spain.
April 7th, 2009.
Nondeterministic One-Tape Off-Line Turing Machines
ABCDays on List Automata, Forgetting Automata, and Restarting Automata, Prague.
March 28th, 2009.
Descriptional Complexity of Automata and Languages.
DICo/DSI, Milano.
December 10th, 2008.
Deterministic Pushdown Automata and Unary Languages.
Mathematical Institute, Slovak Academy of Science, Kosice, Slovakia.
November 13th, 2008.
Abstract
Simulating Unary Context-Free Grammars and Pushdown Automata with Finite Automata.
Institute of Computer Science, P.J. Safarik University, Kosice, Slovakia.
November 12th, 2008.
Abstract
Deterministic Pushdown Automata and Unary Languages.
13th Conference on Implementation and Application of Automata, CIAA 2008, San Francisco, California.
July 23th, 2008.
Eliminating the Nondeterminism from Two-Way Finite Automata.
Institut für Informatik, Goethe Universität, Frankfurt am Main, Germany.
December 11th, 2007.

September 2026, Giovanni Pighizzini