![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Giovanni Pighizzini
Person information
- affiliation: University of Milan, Italy
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j72]Giovanni Pighizzini, Luca Prigioniero, Simon Sádovský:
Performing Regular Operations with 1-Limited Automata. Theory Comput. Syst. 68(3): 465-486 (2024) - 2023
- [j71]Giovanni Pighizzini
, Luca Prigioniero
:
Pushdown automata and constant height: decidability and bounds. Acta Informatica 60(2): 123-144 (2023) - [j70]Jürgen Dassow, Martin Kutrib, Giovanni Pighizzini:
25 Editions of DCFS: Origins and Directions. Bull. EATCS 141 (2023) - [j69]Bruno Guillon
, Giovanni Pighizzini
, Luca Prigioniero
, Daniel Prusa
:
Weight-reducing Turing machines. Inf. Comput. 292: 105030 (2023) - [j68]Giovanni Pighizzini, Branislav Rovan, Simon Sádovský
:
Usefulness of information and decomposability of unary regular languages. Inf. Comput. 295(Part B): 104868 (2023) - [j67]Galina Jirásková
, Giovanni Pighizzini
:
Preface. J. Autom. Lang. Comb. 28(1-3): 3-4 (2023) - [c56]Giovanni Pighizzini
, Luca Prigioniero
:
Pushdown and One-Counter Automata: Constant and Non-constant Memory Usage. DCFS 2023: 146-157 - [c55]Giovanni Pighizzini
, Luca Prigioniero
:
Two-Way Machines and de Bruijn Words. CIAA 2023: 254-265 - [c54]Giovanni Pighizzini, Luca Prigioniero:
Forgetting 1-Limited Automata. NCMA 2023: 95-109 - [c53]Giovanni Pighizzini, Luca Prigioniero:
Once-Marking and Always-Marking 1-Limited Automata. AFL 2023: 215-227 - 2022
- [j66]Bruno Guillon
, Giovanni Pighizzini
, Luca Prigioniero
, Daniel Prusa
:
Converting nondeterministic two-way automata into small deterministic linear-time machines. Inf. Comput. 289(Part): 104938 (2022) - [j65]Bruno Guillon, Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero
:
Weakly and Strongly Irreversible Regular Languages. Int. J. Found. Comput. Sci. 33(3&4): 263-284 (2022) - [j64]Giovanni Pighizzini, Luca Prigioniero
, Simon Sádovský:
1-Limited Automata: Witness Languages and Techniques. J. Autom. Lang. Comb. 27(1-3): 229-244 (2022) - [c52]Giovanni Pighizzini, Luca Prigioniero
, Simon Sádovský:
Performing Regular Operations with 1-Limited Automata. DLT 2022: 239-250 - 2021
- [j63]Henning Fernau
, Andreas Malcher
, Giovanni Pighizzini
:
Preface to Martin Kutrib Festschrift. Acta Informatica 58(4): 241-242 (2021) - [j62]Giovanni Pighizzini, Luca Prigioniero
:
Non-Self-Embedding Grammars and Descriptional Complexity. Fundam. Informaticae 180(1-2): 103-122 (2021) - [c51]Giovanni Pighizzini
, Branislav Rovan
, Simon Sádovský
:
Usefulness of Information and Unary Languages. LATA 2021: 131-142 - [p2]Martin Kutrib
, Nelma Moreira
, Giovanni Pighizzini, Rogério Reis
:
Hot Current Topics of Descriptional Complexity. IFIP's Exciting First 60+ Years 2021: 3-28 - [i10]Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Prusa:
Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines. CoRR abs/2103.05485 (2021) - [i9]Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Prusa:
Weight-Reducing Turing Machines. CoRR abs/2103.05486 (2021) - 2020
- [j61]Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero
:
Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata. Int. J. Found. Comput. Sci. 31(8): 1133-1157 (2020) - [j60]Michal Hospodár, Galina Jirásková
, Giovanni Pighizzini:
Preface. J. Autom. Lang. Comb. 25(2-3): 81-82 (2020) - [e14]Galina Jirásková, Giovanni Pighizzini
:
Descriptional Complexity of Formal Systems - 22nd International Conference, DCFS 2020, Vienna, Austria, August 24-26, 2020, Proceedings. Lecture Notes in Computer Science 12442, Springer 2020, ISBN 978-3-030-62535-1 [contents]
2010 – 2019
- 2019
- [j59]Giovanni Pighizzini, Luca Prigioniero
:
Limited automata and unary languages. Inf. Comput. 266: 60-74 (2019) - [j58]Cezar Câmpeanu
, Giovanni Pighizzini:
Preface. Int. J. Found. Comput. Sci. 30(6-7): 827-829 (2019) - [j57]Stavros Konstantinidis, Giovanni Pighizzini:
Special section on Descriptional Complexity of Formal Systems. Theor. Comput. Sci. 798: 1 (2019) - [c50]Giovanni Pighizzini:
Limited Automata: Properties, Complexity and Variants. DCFS 2019: 57-73 - [c49]Giovanni Pighizzini, Luca Prigioniero
:
Pushdown Automata and Constant Height: Decidability and Bounds. DCFS 2019: 260-271 - [c48]Giovanni Pighizzini:
Limited Automata: Power and Complexity (text not included). ICTCS 2019 - [c47]Giovanni Pighizzini, Luca Prigioniero:
Pushdown Automata Accepting in Constant Height: Decidability and Height Bounds - Extended Abstract. ICTCS 2019: 72-77 - [e13]Barbara Catania, Rastislav Královic, Jerzy R. Nawrocki, Giovanni Pighizzini:
SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings. Lecture Notes in Computer Science 11376, Springer 2019, ISBN 978-3-030-10800-7 [contents] - 2018
- [j56]Martin Kutrib
, Giovanni Pighizzini, Matthias Wendlandt:
Descriptional complexity of limited automata. Inf. Comput. 259(2): 259-276 (2018) - [c46]Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero
, Daniel Prusa
:
Two-Way Automata and One-Tape Machines - Read Only Versus Linear Time. DLT 2018: 366-378 - [c45]Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero
:
Non-self-embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata. CIAA 2018: 186-197 - [e12]Stavros Konstantinidis, Giovanni Pighizzini:
Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Halifax, NS, Canada, July 25-27, 2018, Proceedings. Lecture Notes in Computer Science 10952, Springer 2018, ISBN 978-3-319-94630-6 [contents] - [e11]Rudolf Freund, Michal Hospodár, Galina Jirásková, Giovanni Pighizzini:
Tenth Workshop on Non-Classical Models of Automata and Applications, NCMA 2018, Košice, Slovakia, August 21-22, 2018. Österreichische Computer Gesellschaft 2018, ISBN 978-3-903035-21-8 [contents] - 2017
- [j55]Cezar Câmpeanu, Florin Manea, Giovanni Pighizzini, Jeffrey O. Shallit:
Preface. J. Autom. Lang. Comb. 22(1-3): 3-4 (2017) - [j54]Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero:
Minimal and Reduced Reversible Automata. J. Autom. Lang. Comb. 22(1-3): 145-168 (2017) - [j53]Nelma Moreira
, Giovanni Pighizzini
, Rogério Reis
:
Optimal state reductions of automata with partially specified behaviors. Theor. Comput. Sci. 658: 235-245 (2017) - [j52]Paola Campadelli, Giovanni Pighizzini, Massimiliano Goldwurm:
Preface. Theor. Comput. Sci. 664: 1 (2017) - [j51]Paola Campadelli, Massimiliano Goldwurm, Giovanni Pighizzini:
Alberto Bertoni: A scientist and a friend. Theor. Comput. Sci. 664: 2-11 (2017) - [c44]Giovanni Pighizzini, Luca Prigioniero
:
Limited Automata and Unary Languages. DLT 2017: 308-319 - [c43]Giovanni Pighizzini, Luca Prigioniero:
Non-self-embedding grammars and descriptional complexity. NCMA 2017: 197-209 - [c42]Giovanna J. Lavado
, Giovanni Pighizzini, Luca Prigioniero
:
Weakly and Strongly Irreversible Regular Languages. AFL 2017: 143-156 - [e10]Giovanni Pighizzini, Cezar Câmpeanu:
Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017, Proceedings. Lecture Notes in Computer Science 10316, Springer 2017, ISBN 978-3-319-60251-6 [contents] - 2016
- [j50]Giovanni Pighizzini:
Strongly Limited Automata. Fundam. Informaticae 148(3-4): 369-392 (2016) - [c41]Giovanna J. Lavado
, Giovanni Pighizzini, Luca Prigioniero
:
Minimal and Reduced Reversible Automata. DCFS 2016: 168-179 - [c40]Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero:
Minimal and Reduced Reversible Automata. ICTCS 2016: 234-239 - [c39]Giovanni Pighizzini:
Restricted Turing Machines and Language Recognition. LATA 2016: 42-56 - [i8]Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero:
Minimal and Reduced Reversible Automata. CoRR abs/1611.06840 (2016) - 2015
- [j49]Giovanni Pighizzini
, Andrea Pisoni:
Limited Automata and Context-Free Languages. Fundam. Informaticae 136(1-2): 157-176 (2015) - [j48]Giovanni Pighizzini:
Investigations on Automata and Languages Over a Unary Alphabet. Int. J. Found. Comput. Sci. 26(7): 827-850 (2015) - [j47]Christos A. Kapoutsis
, Giovanni Pighizzini
:
Two-Way Automata Characterizations of L/poly Versus NL. Theory Comput. Syst. 56(4): 662-685 (2015) - [j46]Giovanni Pighizzini:
Guest Column: One-Tape Turing Machine Variants and Language Recognition. SIGACT News 46(3): 37-55 (2015) - [c38]Nelma Moreira
, Giovanni Pighizzini, Rogério Reis
:
Universal Disjunctive Concatenation and Star. DCFS 2015: 197-208 - [c37]Nelma Moreira
, Giovanni Pighizzini, Rogério Reis
:
Optimal State Reductions of Automata with Partially Specified Behaviors. SOFSEM 2015: 339-351 - [e9]Giuseppe F. Italiano
, Giovanni Pighizzini, Donald Sannella:
Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I. Lecture Notes in Computer Science 9234, Springer 2015, ISBN 978-3-662-48056-4 [contents] - [e8]Giuseppe F. Italiano, Giovanni Pighizzini, Donald Sannella:
Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II. Lecture Notes in Computer Science 9235, Springer 2015, ISBN 978-3-662-48053-3 [contents] - [i7]Giovanni Pighizzini:
One-Tape Turing Machine Variants and Language Recognition. CoRR abs/1507.08582 (2015) - 2014
- [j45]Martin Kutrib
, Andreas Malcher
, Giovanni Pighizzini
:
Oblivious two-way finite automata: Decidability and complexity. Inf. Comput. 237: 294-302 (2014) - [j44]Viliam Geffert, Bruno Guillon
, Giovanni Pighizzini
:
Two-way automata making choices only at the endmarkers. Inf. Comput. 239: 71-86 (2014) - [j43]Giovanni Pighizzini
, Andrea Pisoni:
Limited Automata and Regular Languages. Int. J. Found. Comput. Sci. 25(7): 897-916 (2014) - [c36]Giovanna J. Lavado
, Giovanni Pighizzini
, Shinnosuke Seki:
Operational State Complexity under Parikh Equivalence. DCFS 2014: 294-305 - [c35]Giovanni Pighizzini:
Strongly limited automata. NCMA 2014: 191-206 - [c34]Giovanni Pighizzini:
Investigations on Automata and Languages over a Unary Alphabet. CIAA 2014: 42-57 - 2013
- [j42]Martin Kutrib
, Giovanni Pighizzini:
Recent Trends in Descriptional Complexity of Formal Languages. Bull. EATCS 111 (2013) - [j41]Giovanni Pighizzini
:
Two-Way Finite Automata: Old and Recent Results. Fundam. Informaticae 126(2-3): 225-246 (2013) - [j40]Andreas Malcher
, Giovanni Pighizzini
:
Descriptional complexity of bounded context-free languages. Inf. Comput. 227: 1-20 (2013) - [j39]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]Giovanni Pighizzini
, Andrea Pisoni:
Limited Automata and Regular Languages. DCFS 2013: 253-264 - [c32]Giovanni Pighizzini, Andrea Pisoni:
Limited automata and context-free languages. NCMA 2013: 209-223 - 2012
- [j38]Viliam Geffert, Giovanni Pighizzini
:
Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata. Algorithmica 63(3): 571-587 (2012) - [j37]Ian McQuillan, Giovanni Pighizzini:
Preface. Int. J. Found. Comput. Sci. 23(1) (2012) - [j36]Maria Paola Bianchi, Giovanni Pighizzini
:
Normal forms for unary probabilistic automata. RAIRO Theor. Informatics Appl. 46(4): 495-510 (2012) - [j35]Maria Paola Bianchi, Markus Holzer, Sebastian Jakobi, Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini:
On Inverse Operations and Their Descriptional Complexity. J. Autom. Lang. Comb. 17(2-4): 61-81 (2012) - [j34]Markus Holzer
, Martin Kutrib
, Giovanni Pighizzini
:
Preface. Theor. Comput. Sci. 449: 1 (2012) - [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]Giovanni Pighizzini:
Recent Results Around the Sakoda and Sipser Question. NCMA 2012: 27-32 - [c24]Giovanna J. Lavado
, Giovanni Pighizzini
:
Parikh's Theorem and Descriptional Complexity. SOFSEM 2012: 361-372 - [c23]Giovanni Pighizzini:
Two-Way Finite Automata: Old and Recent Results. DCM 2012: 3-20 - [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
- [j33]Maria Paola Bianchi, Carlo Mereghetti
, Beatrice Palano
, Giovanni Pighizzini
:
On the Size of Unary Probabilistic and Nondeterministic Automata. Fundam. Informaticae 112(2-3): 119-135 (2011) - [j32]Galina Jirásková
, Giovanni Pighizzini
:
Optimal simulation of self-verifying automata by deterministic automata. Inf. Comput. 209(3): 528-535 (2011) - [j31]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:
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 [contents] - [i5]Viliam Geffert, Bruno Guillon
, Giovanni Pighizzini:
Two-Way Automata Making Choices Only at the Endmarkers. CoRR abs/1110.1263 (2011) - 2010
- [j30]Viliam Geffert, Giovanni Pighizzini
, Carlo Mereghetti
:
One Pebble Versus epsilon * log n Bits. Fundam. Informaticae 104(1-2): 55-69 (2010) - [j29]Jürgen Dassow, Giovanni Pighizzini, Bianca Truthe
:
Editorial. J. Autom. Lang. Comb. 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:
Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, DCFS 2010, Saskatoon, Canada, 8-10th August 2010. EPTCS 31, 2010 [contents]
2000 – 2009
- 2009
- [j28]Giovanni Pighizzini
:
Deterministic Pushdown Automata and Unary Languages. Int. J. Found. Comput. Sci. 20(4): 629-645 (2009) - [j27]Giovanni Pighizzini:
Nondeterministic One-Tape Off-Line Turing Machines and Their Time Complexity. J. Autom. Lang. Comb. 14(1): 107-124 (2009) - [j26]Cezar Câmpeanu
, Giovanni Pighizzini
:
Preface. Theor. Comput. Sci. 410(35): 3187 (2009) - [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:
Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, DCFS 2009, Magdeburg, Germany, July 6-9, 2009. EPTCS 3, 2009 [contents] - [i4]Andreas Malcher, Giovanni Pighizzini:
Descriptional complexity of bounded context-free languages. CoRR abs/0905.1045 (2009) - [i3]Giovanni Pighizzini:
Deterministic pushdown automata and unary languages. CoRR abs/0905.1248 (2009) - [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 O. Shallit:
Automata and Reduced Words in the Free Group. CoRR abs/0910.4555 (2009) - 2008
- [j25]Viliam Geffert, Giovanni Pighizzini
:
Preface. Int. J. Found. Comput. Sci. 19(4): 747-749 (2008) - [c16]Giovanni Pighizzini
:
Deterministic Pushdown Automata and Unary Languages. CIAA 2008: 232-241 - [e4]Cezar Câmpeanu, Giovanni Pighizzini:
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 [contents] - 2007
- [j24]Viliam Geffert, Carlo Mereghetti
, Giovanni Pighizzini
:
Complementing two-way finite automata. Inf. Comput. 205(8): 1173-1187 (2007) - [j23]Enzo Magalini, Giovanni Pighizzini
:
A Pumping Condition for Ultralinear Languages. Int. J. Found. Comput. Sci. 18(6): 1303-1312 (2007) - [j22]Giovanni Pighizzini, Detlef Wotschke:
Editorial. J. Autom. Lang. Comb. 12(1-2): 5 (2007) - [j21]Hing Leung, Giovanni Pighizzini
:
Preface. Theor. Comput. Sci. 387(2): 91-92 (2007) - [c15]Andreas Malcher
, Giovanni Pighizzini:
Descriptional Complexity of Bounded Context-Free Languages. Developments in Language Theory 2007: 312-323 - [e3]Viliam Geffert, Giovanni Pighizzini:
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 [contents] - 2006
- [j20]Danilo Bruschi, Giovanni Pighizzini
:
String distances and intrusion detection: Bridging the gap between formal languages and computer security. RAIRO Theor. Informatics Appl. 40(2): 303-313 (2006) - [e2]Hing Leung, Giovanni Pighizzini:
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 [contents] - 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:
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 [contents] - 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 O. 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 O. Shallit:
Simulating finite automata with context-free grammars. Inf. Process. Lett. 84(6): 339-344 (2002) - [j15]Giovanni Pighizzini
, Jeffrey O. 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]Giovanni Pighizzini
:
How Hard Is Computing the Edit Distance? Inf. Comput. 165(1): 1-13 (2001) - [j12]Carlo Mereghetti
, Beatrice Palano
, Giovanni Pighizzini
:
Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO Theor. Informatics Appl. 35(5): 477-490 (2001) - [j11]Massimiliano Milani, Giovanni Pighizzini:
Tight Bounds on the Simulation of Unary Probabilistic Automata by Deterministic Automata. J. Autom. Lang. Comb. 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. J. Autom. Lang. Comb. 5(3): 287-300 (2000) - [c9]Giovanni Pighizzini:
Unary Pushdown Automata and Auxiliary Space Lower Bounds. MFCS 2000: 599-608 - [c8]Giovanni Pighizzini:
Unary Language Concatenation and Its State Complexity. CIAA 2000: 252-262
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. Math. Syst. 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]Giovanni Pighizzini:
How Hard is to Compute the Edit Distance. FCT 1995: 383-392 - [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. Comput. Complex. 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
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-07-01 20:42 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint