Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Giovanni Pighizzini
2010 – today
- 2013
[j39]Giovanni Pighizzini: Two-Way Finite Automata: Old and Recent Results. Fundam. Inform. 126(2-3): 225-246 (2013)- [j38]Andreas Malcher, Giovanni Pighizzini: Descriptional complexity of bounded context-free languages. Inf. Comput. 227: 1-20 (2013)
- [j37]Giovanna J. Lavado, Giovanni Pighizzini, Shinnosuke Seki: Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata. Inf. Comput. 228: 1-15 (2013)
- [c33]
- [c32]
- 2012
- [j36]Viliam Geffert, Giovanni Pighizzini: Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata. Algorithmica 63(3): 571-587 (2012)
- [j35]
- [j34]Maria Paola Bianchi, Giovanni Pighizzini: Normal forms for unary probabilistic automata. RAIRO - Theor. Inf. and Applic. 46(4): 495-510 (2012)
- [j33]
- [c31]Christos A. Kapoutsis, Giovanni Pighizzini: Two-Way Automata Characterizations of L/poly versus NL. CSR 2012: 217-228
- [c30]Maria Paola Bianchi, Markus Holzer, Sebastian Jakobi, Giovanni Pighizzini: On Inverse Operations and Their Descriptional Complexity. DCFS 2012: 89-102
- [c29]Giovanna J. Lavado, Giovanni Pighizzini, Shinnosuke Seki: Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata. Developments in Language Theory 2012: 284-295
- [c28]Viliam Geffert, Bruno Guillon, Giovanni Pighizzini: Two-Way Automata Making Choices Only at the Endmarkers. LATA 2012: 264-276
- [c27]Martin Kutrib, Andreas Malcher, Giovanni Pighizzini: Oblivious Two-Way Finite Automata: Decidability and Complexity. LATIN 2012: 518-529
- [c26]Christos A. Kapoutsis, Giovanni Pighizzini: Reversal Hierarchies for Small 2DFAs. MFCS 2012: 554-565
- [c25]
- [c24]Giovanna J. Lavado, Giovanni Pighizzini: Parikh's Theorem and Descriptional Complexity. SOFSEM 2012: 361-372
- [c23]
- [i6]Giovanna J. Lavado, Giovanni Pighizzini, Shinnosuke Seki: Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent One-Way and Two-Way Deterministic Automata. CoRR abs/1212.1346 (2012)
- 2011
- [j32]Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini: On the Size of Unary Probabilistic and Nondeterministic Automata. Fundam. Inform. 112(2-3): 119-135 (2011)
- [j31]Galina Jirásková, Giovanni Pighizzini: Optimal simulation of self-verifying automata by deterministic automata. Inf. Comput. 209(3): 528-535 (2011)
- [j30]Viliam Geffert, Giovanni Pighizzini: Two-way unary automata versus logarithmic space. Inf. Comput. 209(7): 1016-1025 (2011)
- [c22]Maria Paola Bianchi, Giovanni Pighizzini: Normal Forms for Unary Probabilistic Automata. NCMA 2011: 89-102
- [e7]Markus Holzer, Martin Kutrib, Giovanni Pighizzini (Eds.): Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings. Lecture Notes in Computer Science 6808, Springer 2011, ISBN 978-3-642-22599-4
- [i5]Viliam Geffert, Bruno Guillon, Giovanni Pighizzini: Two-Way Automata Making Choices Only at the Endmarkers. CoRR abs/1110.1263 (2011)
- 2010
- [j29]Viliam Geffert, Giovanni Pighizzini, Carlo Mereghetti: One Pebble Versus epsilon * log n Bits. Fundam. Inform. 104(1-2): 55-69 (2010)
- [j28]Jürgen Dassow, Giovanni Pighizzini, Bianca Truthe: Editorial. Journal of Automata, Languages and Combinatorics 15(1/2): 5 (2010)
- [c21]Viliam Geffert, Giovanni Pighizzini: Two-Way Unary Automata versus Logarithmic Space. Developments in Language Theory 2010: 197-208
- [c20]Viliam Geffert, Giovanni Pighizzini: Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata. LATIN 2010: 196-207
- [c19]Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini: Probabilistic vs. Nondeterministic Unary Automata. NCMA 2010: 33-44
- [e6]Ian McQuillan, Giovanni Pighizzini (Eds.): Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems. EPTCS 31, 2010
2000 – 2009
- 2009
- [j27]Giovanni Pighizzini: Deterministic Pushdown Automata and Unary Languages. Int. J. Found. Comput. Sci. 20(4): 629-645 (2009)
- [j26]Giovanni Pighizzini: Nondeterministic One-Tape Off-Line Turing Machines. Journal of Automata, Languages and Combinatorics 14(1): 107-124 (2009)
- [j25]
- [c18]Galina Jirásková, Giovanni Pighizzini: Converting Self-verifying Automata into Deterministic Automata. LATA 2009: 458-468
- [c17]Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: One Pebble Versus log(n) Bits. NCMA 2009: 121-134
- [e5]Jürgen Dassow, Giovanni Pighizzini, Bianca Truthe (Eds.): Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems. EPTCS 3, 2009
- [i4]Andreas Malcher, Giovanni Pighizzini: Descriptional complexity of bounded context-free languages. CoRR abs/0905.1045 (2009)
- [i3]
- [i2]Giovanni Pighizzini: Nondeterministic one-tape off-line Turing machines and their time complexity. CoRR abs/0905.1271 (2009)
- [i1]Thomas Ang, Giovanni Pighizzini, Narad Rampersad, Jeffrey Shallit: Automata and Reduced Words in the Free Group. CoRR abs/0910.4555 (2009)
- 2008
- [j24]
- [c16]
- [e4]Cezar Câmpeanu, Giovanni Pighizzini (Eds.): 10th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2008, Charlottetown, Prince Edward Island, Canada, July 16-18, 2008. University of Prince Edward Island 2008, ISBN 978-0-919013-56-8
- 2007
- [j23]Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: Complementing two-way finite automata. Inf. Comput. 205(8): 1173-1187 (2007)
- [j22]Enzo Magalini, Giovanni Pighizzini: A Pumping Condition for Ultralinear Languages. Int. J. Found. Comput. Sci. 18(6): 1303-1312 (2007)
- [j21]
- [c15]Andreas Malcher, Giovanni Pighizzini: Descriptional Complexity of Bounded Context-Free Languages. Developments in Language Theory 2007: 312-323
- [e3]Viliam Geffert, Giovanni Pighizzini (Eds.): 9th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2007, High Tatras, Slovakia, July 20 - 22, 2007. University of Kosice, Slovakia 2007, ISBN 978-80-7097-688-3
- 2006
- [j20]Danilo Bruschi, Giovanni Pighizzini: String distances and intrusion detection: Bridging the gap between formal languages and computer security. ITA 40(2): 303-313 (2006)
- [e2]Hing Leung, Giovanni Pighizzini (Eds.): 8th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2006, Las Cruces, New Mexico, USA, June 21 - 23, 2006. Proceedings. New Mexico State University, Las Cruces, New Mexico, USA 2006
- 2005
- [j19]Filippo Mera, Giovanni Pighizzini: Complementing unary nondeterministic automata. Theor. Comput. Sci. 330(2): 349-360 (2005)
- [c14]Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: Complementing Two-Way Finite Automata. Developments in Language Theory 2005: 260-271
- [e1]Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini, Detlef Wotschke (Eds.): 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30 - July 2, 2005. Proceedings. Università degli Studi di Milano, Milan, Italy 2005
- 2003
- [j18]Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: Converting two-way nondeterministic unary automata into simpler automata. Theor. Comput. Sci. 295: 189-203 (2003)
- [c13]Carlo Mereghetti, Giovanni Pighizzini: The World of Unary Languages: A Quick Tour. Grammars and Automata for String Processing 2003: 275-284
- [c12]Filippo Mera, Giovanni Pighizzini: Complementing Unary Nondeterministic Automata. DCFS 2003: 174-185
- 2002
- [j17]Giovanni Pighizzini, Jeffrey Shallit: Unary Language Operations, State Complexity and Jacobsthal's Function. Int. J. Found. Comput. Sci. 13(1): 145-159 (2002)
- [j16]Michael Domaratzki, Giovanni Pighizzini, Jeffrey Shallit: Simulating finite automata with context-free grammars. Inf. Process. Lett. 84(6): 339-344 (2002)
- [j15]Giovanni Pighizzini, Jeffrey Shallit, Ming-wei Wang: Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds. J. Comput. Syst. Sci. 65(2): 393-414 (2002)
- [j14]Christian Choffrut, Giovanni Pighizzini: Distances between languages and reflexivity of relations. Theor. Comput. Sci. 286(1): 117-138 (2002)
- 2001
- [j13]
- [j12]Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini: Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. ITA 35(5): 477-490 (2001)
- [j11]Massimiliano Milani, Giovanni Pighizzini: Tight Bounds on the Simulation of Unary Probabilistic Automata by Deterministic Automata. Journal of Automata, Languages and Combinatorics 6(4): 481-492 (2001)
- [j10]Carlo Mereghetti, Giovanni Pighizzini: Optimal Simulations between Unary Automata. SIAM J. Comput. 30(6): 1976-1992 (2001)
- [c11]Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini: On the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. DCFS 2001: 141-148
- [c10]Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: Converting Two-Way Nondeterministic Unary Automata into Simpler Automata. MFCS 2001: 398-407
- 2000
- [j9]Carlo Mereghetti, Giovanni Pighizzini: Two-Way Automata Simulations and Unary Languages. Journal of Automata, Languages and Combinatorics 5(3): 287-300 (2000)
- [c9]
- [c8]
1990 – 1999
- 1998
- [j8]Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: Sublogarithmic Bounds on Space and Reversals. SIAM J. Comput. 28(1): 325-340 (1998)
- [c7]Carlo Mereghetti, Giovanni Pighizzini: Optimal Simulations Between Unary Automata. STACS 1998: 139-149
- 1997
- [c6]Christian Choffrut, Giovanni Pighizzini: Distances Between Languages and Reflexivity of Relations. MFCS 1997: 199-208
- 1996
- [j7]S. Jesi, Giovanni Pighizzini, Nicoletta Sabadini: Probabilistic Asynchronous Automata. Mathematical Systems Theory 29(1): 5-31 (1996)
- 1995
- [j6]Carlo Mereghetti, Giovanni Pighizzini: A Remark on Middle Space Bounded Alternating Turing Machines. Inf. Process. Lett. 56(4): 229-232 (1995)
- [c5]
- [c4]Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini: Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages. MFCS 1995: 309-318
- 1994
- [j5]Danilo Bruschi, Giovanni Pighizzini, Nicoletta Sabadini: On the Existence of Minimum Asynchronous Automata and on the Equivalence Problem for Unambiguous Regular Trace Languages. Inf. Comput. 108(2): 262-285 (1994)
- [j4]Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini: An Optimal Lower Bound for Nonregular Languages. Inf. Process. Lett. 50(6): 289-292 (1994)
- [j3]Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini: Corrigendum: An Optimal Lower Bound for Nonregular Languages. Inf. Process. Lett. 52(6): 339 (1994)
- [j2]Giovanni Pighizzini: Asynchronous Automata Versus Asynchronous Cellular Automata. Theor. Comput. Sci. 132(2): 179-207 (1994)
- [c3]Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini: On Languages Accepted with Simultaneous Complexity Bounds and Their Ranking Problem. MFCS 1994: 245-255
- 1993
- [j1]Eric Allender, Danilo Bruschi, Giovanni Pighizzini: The Complexity of Computing Maximal Word Functions. Computational Complexity 3: 368-391 (1993)
- 1992
- [p1]Paola Bonizzoni, Giancarlo Mauri, Giovanni Pighizzini, Nicoletta Sabadini: Recognizing sets of labelled acyclic graphs. Tree Automata and Languages 1992: 201-224
- 1991
- [c2]Danilo Bruschi, Giovanni Pighizzini: The Complexity of Computing Maximal Word Functions. FCT 1991: 157-167
1980 – 1989
- 1988
- [c1]Danilo Bruschi, Giovanni Pighizzini, Nicoletta Sabadini: On the Existence of the Minimum Asynchronous Automaton and on Decision Problems for Unambiguous Regular Trace Languages. STACS 1988: 334-345
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-15 21:39 CEST by the dblp team