Linda Pagli LIST OF SCIENTIFIC PUBLICATION

A JOURNAL PAPERS

A1 F. Luccio, L. Pagli: "On the Height of Height Balanced Trees" IEEE Transaction on Computers, C-25 (1976) 87-90.

A2 E. Lodi, F. Luccio, L. Pagli, N. Santoro: "Random Access in a List Environment" Information Systems 2 (1976) 11-17.

A3 F. Luccio, L. Pagli: "Rebalancing Height Balanced Trees" IEEE Transaction on Computers, C-27 (1978) 386-396.

A4 E. Lodi, F. Luccio, C. Mugnai, L. Pagli: "On Two Dimensional Data Organization I" Fundamenta Informaticae, 2 (1978) 211-226.

A5 W. Lipsky, E. Lodi, F. Luccio, C. Mugnai, L. Pagli: "On Two Dimentional Data Organization II" Fundamenta Informaticae, 3 (1978) 245-260.

A6 F. Luccio, L. Pagli: "Power Trees" Comm. of the ACM, 21 11 (1978) 942-947.

A7 M. Limina, E. Lodi, F. Luccio, M.E. Occhiuto, L. Pagli, M.T. Rubino: "Meccanizzazione di un Provveditorato agli Studi dal Punto di Vista Informatico: Il Problema del Trasferimento dei Professori” Rivista di Informatica, 9 1 (1979) 25-33.

A8 L. Pagli: "Height Balanced Multiway Trees" Information Systems, 4 (1979) 227-234.

A9 G.C. Bongiovanni, F. Luccio, L. Pagli: "The Problem of Quasi Sorting" Calcolo, 16 4 (1979) 415-430.

A10 F. Luccio, L. Pagli: "A Comment on Generalized AVL Trees" Comm. of the A.C.M., 23 7 (1980) 394-395.

A11 M. Missikoff, L. Pagli: "A Note on Optimal Allocation of Files in a Simmetrical and Homogeneus Computer Network" Information Systems, 5 (1980) 149-150.

A12 M.A. Bonuccelli, L. Pagli: "Incompletely Specified Sequential Machines With Output Constraints". Digital Processes, 1981.

A13 F. Luccio, L. Pagli: "A Linear Algorithm to determine Minimal Spanning Forest in Chain Graphs" Information Processing Letters, 15 (1982) 1-4.

A14 M.A. Bonuccelli, E. Lodi, L. Pagli: "External Sorting in VLSI" IEEE Transaction on Computers, C-33 10 (1984) 931-934.

A15 M.A Bonuccelli, E.Lodi, F.Luccio, P.Maestrini, L.Pagli: "VLSI Algorithms and Architecture for Relational Operations" Calcolo, 22 1 (1985) 63-80. Reprinted in: A.R. Hurson, L.L. Miller and S.H. Pakzad, Eds, Parallel Architectures for Database Systems, IEEE Comp. Soc. Press, Washington,D.C.1989.

A16 M.A. Bonuccelli, E.Lodi, F. Luccio, P. Maestrini, L.Pagli: "A Realistic Approach to VLSI Relational Data Base Processing" Annals of Discrete Mathemathics, 25 (1985) 91-108.

A17 L. Pagli: "Self Adjusting Hash Tables" Information Processing Letters, 21 (1985) 23-25.

A18 E. Lodi, L. Pagli: "Finding the Visibility among Vertical Segments: A VLSI Approach". IEEE Transaction on Computers, C-35 10 (1986) 923-928.

A19 E. Lodi, F. Luccio, L. Pagli: "A Preliminary Study on Diagonal Channel Routing Model" Algorithmica, 4 (1989) 585-597.

A20 E. Lodi, F. Luccio, L.Pagli: "Channel Routing for Strictly Multiterminal Nets", Integration (1989) 8,143-163.

A21 F. Luccio, L. Pagli: "On the upper bound on the rotation distance of binary trees", Inf. Proc. Lett. 31 (1989) 57-60.

A22 A.A. Bertossi, E. Lodi, F. Luccio, L. Pagli: "String matching with weighted errors" Theor. Comp. Sci. 73 73 (1990) 319-328.

A23 E.Lodi, F. Luccio, L. Pagli: "Routing in the Time Square mode", Inf. Proc. Lett. 35 (1990) 41-48.

A24 F. Luccio, L. Pagli: "Efficient algorithms for some tree matching problems", Inf. Proc. Lett. 39 (1991) 51-57.

A25 A.A. Bertossi, E. Lodi, F. Luccio, L. Pagli: "A parallel solution to the approximate string matching problem" Computer Journal 35 5 (1992) 524-526.

A26 R. Francese, L. Pagli, D. Parente, M. Talamo: "A new model for random access", Calcolo 29 1 (1992) 143-155.

A27 F. Luccio, L. Pagli: "The p-shovelers problem (computing with time varying data)", Sigact News 23 2 (1992) 72-75.

A28 A. Nayak, L. Pagli, N. Santoro: "Combinatorial and graph problems arising in the analysis of catastrofic fault patterns". Congressus Numerantium 88, (1992) 7-20.

A29 A. Nayak, L. Pagli, N. Santoro, "Efficient construction of catastrophic patterns for VLSI reconfigurable arrays", Integration-The VLSI Journal 15, (1993) 133-150

A30 F. Luccio, L. Pagli: "A model of sequential computation based on pipelined access to memory", Mathematical System Theory 26 (1993) 343-356.

A31 E. Lodi, F. Luccio, L. Pagli: "Diagonal channel routing with vias at unit distance", Calcolo 30 (1993) 3, 274-287.

A32 L.Pagli, G.Pucci: "Counting the number of fault patterns in redundant VLSI arrays", Information Processing Letters 50 (1994) 337-342.

A33 F. Luccio, L. Pagli: "Approximate matching for two families of trees", Information and Computation 123 1 (1995) 11-119.

A34 A. Nayak, L. Pagli, N. Santoro: "On Testing for Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy", Integration-The VLSI Journal 20 (1996) 327-342.

A35 P.Ferragina, F.Luccio, L.Pagli: '”Maintaining B-trees in a Two Level PRAM 'd3, Processori Dedicati”, a cura di L.Lopriore, F. Luccio e M. Marinaro. Progetto Finalizzato C.N.R. 'Sistemi Informatici e Calcolo Parallelo ', ed. Franco Angeli, Milano 1995.

A36 F. Luccio, L.Pagli: “Introducing Spatial Graphs “ Congressus Numerantium 110, (1995) 33-41.

A37 F. Luccio, L.Pagli: “An insight on PRAM computational bounds” Information Processing Letters 63 (1997) 331-336.

A38 Luccio F., L. Pagli, "Normal matrices, pseudo-cubes and pseudo-products". Congressus Numerantium 127 (1997) 33-56.

A39 F. Luccio, L.Pagli: '”Computing with time-varying data:sequential complexity and parallel speed-up” Mathematical System Theory 31, 1 (1998) 5-26. .

A40 R. De Prisco, A. Monti, L. Pagli: “Testing and Reconfiguration of VLSI Linear arrays” Theoretical Computer Science 197 (1998) 171-188.

A41 F. Luccio, L.Pagli: “On a new boolean function with applications” IEEE Transaction on Computers 48, 3 (1999) 296-310.

A42 F. Luccio, M. Mahafzah, M.Omari, L.Pagli “Masked Interval Routing: A New Routing Scheme” The Computer Journal 43, 2 (2000) 121-129.

A43 F. Luccio, L.Pagli: '”The death of the monster” ACM SIGACT News 4, 31 (2000) 130-133.

A44 P. Crescenzi, A. Del Lungo, R. Grossi, E. Lodi, L. Pagli, G. Rossi: "Text Sparsification via Local Maxima" Theoretical Computer Science 304,1 (2003) 361-364.

A45 V. Ciriani, F. Luccio, L.Pagli: "SPP synthesis of modular multipliers" Integration:the VLSI journal 36, 3 (2003) 103-118.

A46 P. Flocchini, E. Lodi, F. Luccio, L. Pagli and N.Santoro: "Dynamic Monopolies in Tori" Discrete Applied Mathematics 137 (2004) 197-212.

A47 A. Bernasconi,V. Ciriani, F. Luccio, L.Pagli: "Fast three-level logic minimization based on function regularities" IEEE Transaction on Computer-Aied Design of Circuits and Systems 8, 22 (2003) 1005-1016.

A48 F. Luccio, L.Pagli: "Distributed Construction of Almost-Edge-Disjoint Spanning Trees via Dense trees." I+D Computacion n, 2, 2 (2003) 79-86.

A49 G. Franceschini, R.Grossi, J.I. Munro, L. Pagli: "Implicit B-trees: a new data structure for the dictionary problem." Journal of Computer and Systems Sciences 68, 4 (2004) 788-807.

A50 A. Bernasconi,V. Ciriani, F. Luccio, L.Pagli: "Exploiting regularities for Boolean Function Synthesis. Theory of Computing Systems 4, 7 (2006) 485-501.

A51 G. Franceschini, F. Luccio, L. Pagli: "Dense Trees" Journal of Discrete Algorithms 4 (2006) 455-474.

A52 P. Flocchini, A. Mesa Enriques, L.Pagli, G. Prencipe, N. Santoro: "Point-of-Failure Swap Rerouting: Computing the Optimal Swaps Distributively" IEICE Special Issue on Parallel/Distributed Computing and Networking, E89-D, 2 (2006) 700-708.

A53. Bernasconi,V. Ciriani, F. Luccio, L.Pagli: "Synthesis of autosymmetric functions in a new 3-levels form" Theory of Computing Systems, (to appear).

A54 F. Luccio, A. Mesa Enriques ,L.Pagli: "K-restricted rotation distance between binary trees" Information Processing Letters, 102 (2007) 175-180.

A55 S.Cleary, F. Luccio, L.Pagli: "Refined upper bounds for Right–arm Rotation Distances” Theoretical Computer Science 377 (2007) 277-281.

A56 F. Luccio, N. Santoro, L.Pagli: “Network Decontamination with Local Majority-Based Immunization” International Journal on Foundation of Computer Science, 18 (2007) 3, 457-474.

A 56 F. Luccio, A. Mesa Enriquez, P. Olivares Rieumont, L. Pagli: "Bottom-up Subtree Isomorphism for Unordered Labeled Trees, International Journal of Pure and Applied Mathematics, 38 (2007) 3, 325-343.

A' RECENT PAPERS AND TECHNICAL REPORTS

B CONFERENCE PAPERS

B1 E. Lodi, F. Luccio, L. Pagli, N. Santoro: "Problemi di Partizione e Ricerca su Strutture Informative" Convegno di Informatica Teorica, Mantova 1974.

B2 E. Lodi, F. Luccio, C. Mugnai, L. Pagli: "A Preliminary Investigation on Two Dimensional Data Organization" Congresso AICA, Milano 1976.

B3 F. Luccio, L. Pagli: "Polynomial B-Balanced Trees" Proc. 15-th Allerton Conference, (1977) 8-15.

B4 F. Luccio, L. Pagli: "A Versatile Interconnection Pattern Laid on O(n) Area" Proc. 10-th Ifip Conference on Syst. Modelling and Optimization, (1981) 596-604.

B5 F. Luccio, L. Pagli: "Minimal Spanning Forests in Binary Trees" Proc. 20-th Allerton Conference, (1982) 914-923.

B6 M.A. Bonuccelli, E. Lodi, F. Luccio, P. Maestrini, L. Pagli: "A VLSI Tree Machine For Relational Data Bases" IEEE Conf. proc. of 10-th Int. Symp. on Computer Architecture, (1983) 67-73.

B7 M.A. Bonuccelli, E. Lodi, F. Luccio, P. Maestrini, L. Pagli: "VLSI Mesh of Trees for Data Base Processing".Proc. of CAAP, 8-th Coll. on Trees in Algebra and Programming, (1983) 155-166.

B8 E. Lodi, L. Pagli: "A VLSI Algorithm for a Visibility Problem" Proc.of the International Workshop on Parallel Computing and VLSI, (1984) 125-134.

B9 E. Lodi, L. Pagli: "Some new results on a Restricted Channel Routing Problem" Proc. Aegean Workshop on Parallel Computing and VLSI, (1986) 133-143.

B10 A. A. Bertossi, E. Lodi, F. Luccio, L. Pagli: "Approximate String Matching with Context-Dependency" Proc. 20-th Allerton Conference, (1987).

B11 A. A. Bertossi, E. Lodi, F. Luccio, L. Pagli: "Context-dependent string matching" Proc. of Sequences, (1988) 25-40.

B12 E. Lodi, F. Luccio, L. Pagli: "A 4d channel router for a two layer diagonal model". Aegean workshop on parallel computing and VLSI, jun. '88.

B13 F. Luccio, L. Pagli: "Sequential computation based on pipelined access to memory", Proc. 27-th Allerton Conf. (1989) 702-710.

B14 F. Luccio, L. Pagli: "Simple solution for approximate tree matching problems "Proc. of Tapsoft '91 (1991) 193-201.

B15 R. Grossi, F. Luccio, L. Pagli: "Coding trees as strings for approximate tree matching" Proc. of Sequences 91 (1991).

B16 A. Nayak, L. Pagli, N. Santoro: "Efficient construction of Catastophic Patterns for VLSI Reconfigurable Arrays with bidirectional links". 4-th Int. Conf. on Computig and Information, Toronto 1992.

B17 B.De Iaco, F. Luccio, L. Pagli: "Palindromic Trees", Proc. 30-th Allerton Conference, (1992) 585-593.

B18 F.Luccio, L.Pagli and G.Pucci. "Three non conventional paradigms of parallel computation". In: F.Meyer auf der Heide et al., Eds.: Parallel Architectures and their Efficient Use, (1992) LNCC 678, Springer Verlag, Berlin

B19 A. Nayak, L. Pagli, N. Santoro: "Efficient construction of Catastophic Patterns for VLSI reconfigurable VLSI Arrays“ IEEE Int. Work. on Defects and Fault Tolerance in VLSI systems, Dallas 1992.

B20 F. Luccio, L. Pagli: "The p-shovelers problem (computing with time-varying data)", Proc. of 4-th IEEE Symp. on Parallel and Distibuted Processing (1992), 188-193.

B21 B.De Iaco, R. Grossi, F. Luccio, L. Pagli: "Instances of pattern detection and matching in discrete structures", with In: Proceedings 3rd International Conference on Advances in Pattern Recognition and Digital Techniques (Calcutta 1993)

B22 F. Luccio, L.Pagli: "PRAM bounds based on data movement", with L. Pagli. In: Proc. DIMACS Workshop on Organizing and Moving Data in Parallel Computers (Princeton 1994).

B23 F. Luccio, L.Pagli: “Computational Bounds for the Simple and MRMV PRAM “ Proc. of 6-th IEEE Symp. on Parallel and Distibuted Processing (1994), 552-557.

B24 F. Luccio and L. Pagli: "Normal Matrices, Pseudo-Cubes, Pseudo-Products" 27-th Twenty-Eighth Southeastern Int. Conf. on Combinatorics, Graph Theory and Computing, Boca Raton, Fl (1997)

B25 P. Flocchini, E. Lodi, F. Luccio, L. Pagli and N.Santoro: "Irreversible dynamos in tori" Euro-Par '98 , LCNS 1470 (1998), 554-562.

B26 F. Luccio, M. Mahafzah, M.Omari, L.Pagli: 'd2Routing with the use of masks 'd3 Proc. of Sirocco 5 (1998), 188-199.

B27 F. Luccio and L. Pagli: "Dense Trees: A New Structure For Interconnection" Proc. of Distributed Data and Structures 2, Carleton Scientific (1999), 56-72.

B28 P. Flocchini, E. Lodi, F. Luccio, L. Pagli and N.Santoro: "Monotone dynamos in tori" Proc. of Sirocco 6 (1999), 152-165.

B29 F. Luccio, L. Pagli and H.Sanossian: "Irreversible dynamos in butterflies" Proc. of Sirocco 6 (1999), 204-217.

B30 F. Luccio, A. Mesa and L. Pagli: "A distributed tree data structure" Proc. of ISADCS2000, (2000) 1-6.

B31 F. Luccio and L. Pagli: "An algorithmic definition of interval with application to routing" Proc. of Sirocco 7 (2000), 227-236

B32 Y. de la Noval, F. Luccio, Y. Nunez Rodriguez and L. Pagli: "Dynamos in Three-Dimensional Meshes" CIICC'00, Tampico, Mexico

B33 Marangoni R., Savona A., Ferragina P., Pisanti N., Pagli L., Luccio F., "A method for paralogy trees construction", (Poster) GCB2000, Heidelberg, October 5-7, 2000.

B34 P. Crescenzi, A. Del Lungo, R. Grossi, E. Lodi, L. Pagli, G. Rossi: "Text Sparsification via Local Maxima" Lect. Not. in Comp. Sci. 1974, Springer-Verlag (2000) 290-301.

B35 L Flores Pacheco, G. Franceschini, F. Luccio, L. Pagli: "Decomposition of k-Dense Trees" Proc. of Distributed Data and Structures 3, Carleton Scientific (2001) 11-25.

B36 D. Gualerzi, E. Lodi, L. Pagli: "Interaction between Economic and Computational Problems arising in Internet: a Preliminary Investigation." Proc. of SSGRR (2002)

B37 A. Bernasconi, V. Ciriani, F. Luccio, L. Pagli: "Fast Three-Level Logic Minimization Based on Autosymmetry" Proc. 39th ACM/IEEE Design Automation Conference (DAC), New Orleans (2002) 425-430.

B38 A. Bernasconi, V. Ciriani, F. Luccio, L. Pagli: "Implicit Test of Regularities for Not Completely Specified Boolean Functions" Proc. of IWLS-02, (2002).

B39 F. Luccio, L.Pagli: "Two New Applications of Dynamos" Proc. 9-th Internat. Coll. on Structural Information and Communication Complexity, (2002) 247-259.

B40 G. Franceschini, R.Grossi, J.I. Munro, L. Pagli: "Implicit B-trees: New Results for the Dictionary Problem." Proc. of the 43-th Foundation of Computer Science (FOCS), (2002) 145-154.

B41 D. Gualerzi, E. Lodi, L. Pagli:"E-commerce, Intermediation and Intelligent Software Agents" Proc. of IADIS Int. Conf. WWW/Internet (2002) 515-519.

B42 F. Luccio, A. Mesa Enriquez, P. Olivares Rieumont, L. Pagli: "Exact Rooted Subtree Matching in Sublinear Time" Proc. 9-th ANaCC/ACM/IEEE Int. Congress On Comp. Sc. (CIIC '02), (2002) 27-35.

B43 F. Luccio, L.Pagli: "Distributed Construction of Almost-Edge-Disjoint Spanning Trees via Dense trees." Proc. 9-th ANaCC/ACM/IEEE Int. Congress On Comp. Sc. (CIIC '02), (2002) 36-44.

B44 F. Luccio, L.Pagli: "From Algorithms to Criptography. A Tutorial" LATIN 2002: Theoretical Informatics, 1 (2202) 15-25.

B45 P. Flocchini, L.Pagli, G. Prencipe, N. Santoro, P. Widmayer, T. Zuva: "Computing all the Best Swap Edges Distributively" Proc. 8-th Int. Conference on Principles of Distributed Systems (OPODIS), LNCS 3544 (2004), 154-168.

B46 P. Flocchini, A. Mesa Enriques L.Pagli, G. Prencipe, N. Santoro: "Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree" Proc. of IFIP international Conference on Teoretical Computer Science (TCS) 1 (2004) 153-166.

B47 L.Pagli, G. Prencipe, T. Zuva: "Distributed Computation for Swapping a Failing Edge" Proc. International Workshop on Distributed Computing (IWDC), LNCS 3326 (2004) 28-39.

B48 P.Crescenzi, E.Lodi, L.Pagli: "The Estherithms Museum" Proc. of Fun with Algorithms (FUN), 1 (2204) 273-280.

B49 A.Almejda Ruiz, F. Luccio, A.Mesa Enriques, L.Pagli: "k-Restricted Rotation with Application to Search Tree Rebalancing" (WADS), LCNS 3608 (2005), 2-13.

B50 F. Luccio, L.Pagli: "Up-down distance between two trees” ISSADS 2006.

B51 F. Luccio, L.Pagli, N. Santoro: “ Network Decontamination with local immunization” International Parallel Distributed Processing Symposium (IPDPS) 2006.

B52 F. Luccio, L.Pagli: “Web Marshals Fighting Curly Link Farms” (FUN07) LNCS 4475 (2007), 240-248.

B53 A. Bernasconi, C. Bodei, L. Pagli:’ Knitting for fun: a recursive pullover” (FUN07), LNCS 4475 (2007), 53-65.

B54 P. Flocchini, A. Mesa Enriques L.Pagli, G. Prencipe, N. Santoro: "Distributed Computation of All Node Replacements of a Minimum Spanning Tree " (EUROPAR2007).

C BOOKS AND TEACHING MATERIALS

C1 F. Luccio, L. Pagli: "Reti Logiche e Calcolatore" ed. Boringhieri, Torino, 1986.

C2 F.Luccio, E.Lodi, L.Pagli: "Algoritmica" Progetto Strategico del C.N.R. Tecnologie e Innovazioni Didattiche, 1986.

C3 L. Pagli: "I Linguaggi di Programmazione" Voce Quadro del Dizionario Scientifico delle Scienze Fisiche; Istituto della Enciclopedia Italiana Fondata da G. Treccani.

C4 F.Luccio, L.Pagli: "La complessità degli algoritmi paralleli". Le Scienze: quaderni, La matematica della complessità, a cura di F.Luccio e L.Pagli, n.67 (1992).

C5 E. Lodi, F.Luccio, L.Pagli, X.Song: “Modelli non convenzionali per il routing di collegamenti” Processori Dedicati, a cura di L.Lopriore, F. Luccio e M. Marinaro. Progetto Finalizzato C.N.R. “Sistemi Informatici e Calcolo Parallelo”, ed. Franco Angeli, Milano 1995.

C6 F.Luccio, L.Pagli, G.Pucci: “Algoritmi e strutture dati in parallelo” Processori Dedicati, a cura di L.Lopriore, F. Luccio e M. Marinaro. Progetto Finalizzato C.N.R. “Sistemi Informatici e Calcolo Parallelo”, ed. Franco Angeli, Milano 1995.

C7 F.Luccio, L.Pagli: “Algoritmi, divinità e gente comune”, edizioni ETS, Pisa 1999.

C8 L.Pagli: “I segreti di Google” , www.ilprimoamore.com, ottobre 2006.

C9 F.Luccio, L.Pagli: “Storia matematica della rete” , Bollati Boringhieri ed., Torino, 2007.