469:
454:
109:
136:
140:
231:
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2003). "Converting two-way nondeterministic unary automata into simpler automata".
489:
166:
by results on sublogarithmic space complexity classes and on the complexity of searching for a lexicographically maximal string.
484:
163:
156:
311:
Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimal simulation of self-verifying automata by deterministic automata".
266:
Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni (2014). "Two-way automata making choices only at the endmarkers".
89:
59:
399:
Allender, Eric; Bruschi, Danilo; Pighizzini, Giovanni (1993). "The complexity of computing maximal word functions".
346:
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (1998). "Sublogarithmic Bounds on Space and
Reversals".
101:
108:, where he is a full professor since 2001. Pighizzini serves as the Steering Committee Chair of the annual
494:
93:
63:
144:
112:
105:
73:
32:
424:
381:
275:
416:
373:
328:
293:
248:
210:
183:
Mereghetti, Carlo; Pighizzini, Giovanni (2001). "Optimal
Simulations between Unary Automata".
408:
363:
355:
320:
285:
240:
200:
192:
152:
148:
124:
97:
42:
468:
128:
453:
132:
244:
478:
385:
428:
359:
196:
420:
377:
332:
324:
297:
289:
252:
214:
412:
368:
205:
131:
over a one-letter alphabet, In particular, in his joint paper with
280:
447:
463:
459:
226:
224:
135:
and
Mereghetti he presented the first simulation of
69:
55:
38:
28:
21:
8:
467:
452:
110:Descriptional Complexity of Formal Systems
18:
367:
279:
204:
151:. Jointly with Jirásková, he determined
137:two-way nondeterministic finite automata
175:
16:Italian theoretical computer scientist
141:two-way deterministic finite automata
127:tradeoffs between different types of
104:. He earned his PhD in 1993 from the
7:
14:
164:computational complexity theory
157:self-verifying finite automata
90:theoretical computer scientist
1:
245:10.1016/S0304-3975(02)00403-6
233:Theoretical Computer Science
123:Pighizzini obtained optimal
60:Theoretical Computer Science
490:Italian computer scientists
313:Information and Computation
268:Information and Computation
162:He also contributed to the
149:2DFA vs. 2NFA open question
511:
360:10.1137/S0097539796301306
348:SIAM Journal on Computing
197:10.1137/S009753979935431X
185:SIAM Journal on Computing
79:
48:
401:Computational Complexity
325:10.1016/j.ic.2010.11.017
290:10.1016/j.ic.2014.08.009
102:two-way finite automata
485:Italian mathematicians
147:, contributing to the
119:Research contributions
94:formal language theory
92:known for his work in
64:formal language theory
466:Bibliography Server
96:and particularly in
460:Giovanni Pighizzini
113:academic conference
106:University of Milan
86:Giovanni Pighizzini
74:University of Milan
33:University of Milan
23:Giovanni Pighizzini
413:10.1007/BF01275489
145:Savitch's theorem
83:
82:
50:Scientific career
502:
471:
456:
451:
450:
448:Official website
433:
432:
396:
390:
389:
371:
343:
337:
336:
308:
302:
301:
283:
263:
257:
256:
239:(1–3): 189–203.
228:
219:
218:
208:
191:(6): 1976–1992.
180:
153:state complexity
125:state complexity
98:state complexity
43:state complexity
19:
510:
509:
505:
504:
503:
501:
500:
499:
475:
474:
446:
445:
442:
437:
436:
398:
397:
393:
345:
344:
340:
310:
309:
305:
265:
264:
260:
230:
229:
222:
182:
181:
177:
172:
129:finite automata
121:
62:
29:Alma mater
24:
17:
12:
11:
5:
508:
506:
498:
497:
492:
487:
477:
476:
473:
472:
457:
441:
440:External links
438:
435:
434:
407:(4): 368–391.
391:
354:(1): 325–340.
338:
319:(3): 528–535.
303:
258:
220:
174:
173:
171:
168:
120:
117:
88:is an Italian
81:
80:
77:
76:
71:
67:
66:
57:
53:
52:
46:
45:
40:
39:Known for
36:
35:
30:
26:
25:
22:
15:
13:
10:
9:
6:
4:
3:
2:
507:
496:
495:Living people
493:
491:
488:
486:
483:
482:
480:
470:
465:
461:
458:
455:
449:
444:
443:
439:
430:
426:
422:
418:
414:
410:
406:
402:
395:
392:
387:
383:
379:
375:
370:
365:
361:
357:
353:
349:
342:
339:
334:
330:
326:
322:
318:
314:
307:
304:
299:
295:
291:
287:
282:
277:
273:
269:
262:
259:
254:
250:
246:
242:
238:
234:
227:
225:
221:
216:
212:
207:
202:
198:
194:
190:
186:
179:
176:
169:
167:
165:
160:
158:
154:
150:
146:
142:
138:
134:
130:
126:
118:
116:
114:
111:
107:
103:
99:
95:
91:
87:
78:
75:
72:
68:
65:
61:
58:
54:
51:
47:
44:
41:
37:
34:
31:
27:
20:
404:
400:
394:
351:
347:
341:
316:
312:
306:
271:
267:
261:
236:
232:
188:
184:
178:
161:
122:
115:since 2006.
85:
84:
70:Institutions
49:
369:2434/178756
479:Categories
206:2434/35121
170:References
421:1016-3328
378:0097-5397
333:0890-5401
298:0890-5401
281:1110.1263
274:: 71–86.
253:0304-3975
215:0097-5397
386:37853723
133:Geffert
429:886700
427:
419:
384:
376:
331:
296:
251:
213:
143:using
56:Fields
425:S2CID
382:S2CID
276:arXiv
464:DBLP
417:ISSN
374:ISSN
329:ISSN
294:ISSN
249:ISSN
211:ISSN
462:at
409:doi
364:hdl
356:doi
321:doi
317:209
286:doi
272:239
241:doi
237:295
201:hdl
193:doi
155:of
139:by
100:of
481::
423:.
415:.
403:.
380:.
372:.
362:.
352:28
350:.
327:.
315:.
292:.
284:.
270:.
247:.
235:.
223:^
209:.
199:.
189:30
187:.
159:.
431:.
411::
405:3
388:.
366::
358::
335:.
323::
300:.
288::
278::
255:.
243::
217:.
203::
195::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.