Search

Your search keyword '"Laura Giambruno"' showing total 12 results
Start Over Author "Laura Giambruno" Search Limiters Full Text
12 results on '"Laura Giambruno"'

1. Representing prefix and border tables: results on enumeration

Author

Julien Clément, Laura Giambruno, Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Dipartimento di Matematica e Applicazioni [Palermo], Università di Palermo, ANR-09-BLAN-0011,BOOLE(2009), and ANR-13-BS02-0003,DynA3S,Dynamique des algorithmes du pgcd : une approche Algorithmique, Analytique, Arithmétique et Symbolique(2013)

Subjects
Discrete mathematics, Sequence, Image (category theory), 010102 general mathematics, String (computer science), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Inverse, Order (ring theory), [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], 0102 computer and information sciences, Data_CODINGANDINFORMATIONTHEORY, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, Computer Science Applications, Prefix, Mathematics (miscellaneous), 010201 computation theory & mathematics, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Combinatorial class, 0101 mathematics, Mathematics
Abstract

For some text algorithms, the real measure for the complexity analysis is not the string itself but its structure stored in its prefix table or equivalently border table. In this paper, we define the combinatorial class of prefix lists, namely a sequence of integers together with their size, and an injection ψ from the class of prefix tables to the class of prefix lists. We call a valid prefix list the image by ψ of a prefix table. In particular, we describe algorithms converting a prefix/border table to a prefix list and inverse linear algorithms from computing from a prefix list L = ψ(P) two words respectively in a minimal size alphabet and on a maximal size alphabet with P as prefix table. We then give a new upper bound on the number of prefix tables for strings of length n (on any alphabet) which is of order (1 + ϕ)n (with $\varphi=\frac{1+\sqrt{5}}{2}$ the golden mean) and also present a corresponding lower bound.

Published
2017
Full Text
View/download PDF

2. Dictionary-symbolwise flexible parsing

Author

Maxime Crochemore, Alessio Langiu, Filippo Mignosi, Laura Giambruno, Antonio Restivo, Crochemore, M, Giambruno, L, Langiu, A, Mignosi, F, Restivo, A, Crochemore, Maxime, Informatics, King‘s College London, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Matematica e Applicazioni [Palermo], Università degli studi di Palermo - University of Palermo, CROCHEMORE, M, GIAMBRUNO, L, LANGIU, A, MIGNOSI, F, RESTIVO, A, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Università di Palermo

Subjects
Theoretical computer science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Data_CODINGANDINFORMATIONTHEORY, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Directed acyclic graph, Theoretical Computer Science, Constant (computer programming), 020204 information systems, Encoding (memory), Optimal parsing, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Stringology, Symbolwise text compression, Time complexity, Lossless compression, Parsing, Settore INF/01 - Informatica, Dictionary-based compression, Optimal Parsing, Lossless Data Compression, DAG, Prefix, Computational Theory and Mathematics, Text compression, 010201 computation theory & mathematics, Algorithm, computer, Bottom-up parsing, Data compression
Abstract

Linear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbolwise compressor our algorithm can be implemented in O(nlogn) time. We further present some experimental results that show the effectiveness of the dictionary-symbolwise approach.

Published
2012
Full Text
View/download PDF

3. A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay

Author

Laura Giambruno, Jean Néraud, Carla Selmi, Sabrina Mantaci, Giambruno, L., Mantaci, S., Néraud, J., Selmi, C., Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), and Springer

Subjects
Prefix code, Strongly connected component, Theoretical computer science, Generalization, deciphering delay, Data_CODINGANDINFORMATIONTHEORY, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Encoding (memory), 0202 electrical engineering, electronic engineering, information engineering, Code (cryptography), Computer Science (miscellaneous), prefix (free) code, unlabeled graph, Mathematics, Code, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], 020206 networking & telecommunications, strongly connected component, transducer, Prefix, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], 010201 computation theory & mathematics, Graph (abstract data type), Algorithm, Decoding methods
Abstract

Girod’s encoding method has been introduced in order to efficiently decode from both directions messages encoded by using finite prefix codes. In the present paper, we generalize this method to finite codes with a finite deciphering delay. In particular, we show that our decoding algorithm can be realized by a deterministic finite transducer. We also investigate some properties of the underlying unlabeled graph.

Published
2015
Full Text
View/download PDF

4. On the Number of Prefix and Border Tables

Author

Laura Giambruno, Julien Clément, Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Dipartimento di Matematica e Informatica [Palermo], and Università degli studi di Palermo - University of Palermo

Subjects
Discrete mathematics, Prefix, Combinatorics, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], String (computer science), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Order (ring theory), Stirling number, Golden ratio, Kraft's inequality, Table (information), Upper and lower bounds, Mathematics
Abstract

For some text algorithms, the real measure for the complexity analysis is not the string itself but its structure stored in its prefix table (or border table, as border and prefix tables can be proved to be equivalent). We give a new upper bound on the number of prefix tables for strings of length n (on any alphabet) which is of order (1 + φ) n (with \(\varphi={{1+\sqrt{5}}\over{2}}\) the golden mean) and present also a lower bound.

Published
2014
Full Text
View/download PDF

5. A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay

Author

Carla Selmi, Laura Giambruno, Sabrina Mantaci, Jean Néraud, Yen H.C., Ibarra O.H., Giambruno L., Mantaci S., Néraud J., and Selmi C.

Subjects
Discrete mathematics, Prefix code, Strongly connected component, Settore INF/01 - Informatica, Generalization, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Prefix, 010201 computation theory & mathematics, Encoding (memory), 0202 electrical engineering, electronic engineering, information engineering, Code (cryptography), Alphabet, Girod's encoding, codes, finite deciphering delay, Decoding methods, Mathematics
Abstract

In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers associated to different keys have an isomorphic non trivial strongly connected component.

Published
2012
Full Text
View/download PDF

6. ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS

Author

Alessio Langiu, Laura Giambruno, Maxime Crochemore, Crochemore, M, Giambruno, L, Langiu, A, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Matematica e Applicazioni [Palermo], Università degli studi di Palermo - University of Palermo, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Università di Palermo

Subjects
minimal automata, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Timed automaton, deterministic automata, Büchi automaton, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Deterministic automaton, 0202 electrical engineering, electronic engineering, information engineering, Computer Science (miscellaneous), Two-way deterministic finite automaton, Nondeterministic finite automaton, Mathematics, online construction, Discrete mathematics, Settore INF/01 - Informatica, Powerset construction, Pushdown automaton, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 010201 computation theory & mathematics, Probabilistic automaton, 020201 artificial intelligence & image processing, Finite set of word, Algorithm, Computer Science::Formal Languages and Automata Theory
Abstract

In this paper we describe a "light" algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on real dictionaries, on biological sequences and on the sets of suffixes (resp. factors) of a set of words that shows how our automaton is near to the minimal one. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton. We moreover construct linear algorithms for the insertion and deletion of a word in a finite set, directly from the constructed automaton.

Published
2012
Full Text
View/download PDF

7. On the size of transducers for bidirectional decoding of prefix codes

Author

Laura Giambruno, Sabrina Mantaci, Giambruno, L, and Mantaci, S

Subjects
Discrete mathematics, Prefix code, Block code, Settore INF/01 - Informatica, General Mathematics, Concatenated error correction code, prefix code, List decoding, Serial concatenated convolutional codes, Sequential decoding, Linear code, Computer Science Applications, Prefix, bilateral decoding, Variable length code, transducers, Algorithm, Computer Science::Formal Languages and Automata Theory, Software, Mathematics
Abstract

In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [ IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X . We find some bounds of such a number of states in relation with different notions of “size” of X . In particular, we give an exact formula for the number of states of transducers associated to maximal prefix codes. We moreover consider two special cases of codes: maximal uniform codes and a class of codes, that we name string-codes. We show that they represent, for maximal codes, the extreme cases with regard to the number of states in terms of different sizes. Moreover we prove that prefix codes corresponding to isomorphic trees have transducers that are isomorphic as unlabeled graphs.

Published
2012

8. Transducers for the bidirectional decoding of prefix codes

Author

Sabrina Mantaci, Laura Giambruno, Giambruno, L, and Mantaci, S

Subjects
Prefix code, General Computer Science, Settore INF/01 - Informatica, Generalization, Computer science, Girod’s encoding, Transducers, Theoretical Computer Science, Prefix, Transducer, Prefix codes, Algorithm, Decoding methods, Word (computer architecture), Computer Science(all)
Abstract

We construct a transducer for the bidirectional decoding of words encoded by the method introduced by Girod (1999) in [5] and we prove that it is bideterministic and that it can be used both for the left-to-right and the right-to-left decoding.We also give a similar construction for a transducer that decodes in both directions words encoded by a generalization of Girod’s encoding method. We prove that it has the same properties as those of the previous transducer. In addition we show that it has a single initial/final state and that it is minimal.

Published
2010

9. Complexity of operations on cofinite languages

Author

Frédérique Bassino, Cyril Nicaud, Laura Giambruno, Bassino, F, Giambruno, L, Nicaud, C, Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Matematica e Applicazioni [Palermo], Università di Palermo, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Bassino, Frédérique, Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Università degli studi di Palermo - University of Palermo, and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Nested word, Theoretical computer science, Settore INF/01 - Informatica, automata, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], regular operation, ReDoS, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Descriptive complexity theory, state complexity, 01 natural sciences, Complement (complexity), Deterministic finite automaton, 010201 computation theory & mathematics, Theory of computation, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Programming Languages, Quantum finite automata, 020201 artificial intelligence & image processing, Nondeterministic finite automaton, cofinite language, Mathematics
Abstract

International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.

Published
2010

10. The Average State Complexity of the Star of a Finite Set of Words Is Linear

Author

Frédérique Bassino, Cyril Nicaud, Laura Giambruno, Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Matematica e Applicazioni [Palermo], Università degli studi di Palermo - University of Palermo, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), ANR-07-BLAN-0330,GAMMA,Génération Aléatoire : Modèles, Méthodes et Algorithmes(2007), Bassino, F, Giambruno, L, Nicaud, C, Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Università di Palermo, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Nicaud, Cyril, and Blanc - Génération Aléatoire : Modèles, Méthodes et Algorithmes - - GAMMA2007 - ANR-07-BLAN-0330 - BLANC - VALID

Subjects
Uniform distribution (continuous), Computation, Star (game theory), 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Integer, 0202 electrical engineering, electronic engineering, information engineering, Time complexity, Finite set, Mathematics, star operation, Discrete mathematics, average case analysi, state complexity, 16. Peace & justice, Binary logarithm, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], automaton, State complexity, 010201 computation theory & mathematics, finite language, 020201 artificial intelligence & image processing, Computer Science::Formal Languages and Automata Theory
Abstract

We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.

Published
2008
Full Text
View/download PDF

11. An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid

Author

Antonio Restivo, Laura Giambruno, GIAMBRUNO L, RESTIVO A, GIAMBRUNO, L, and RESTIVO, A

Subjects
Discrete mathematics, Generator (category theory), General Mathematics, Characterization (mathematics), Computer Science Applications, Combinatorics, Prefix, Mathematics Subject Classification, Intersection, Free monoid, Product (mathematics), Rank (graph theory), Computer Science::Formal Languages and Automata Theory, Software, Automata Theory, Free Monoids, Mathematics
Abstract

We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumaki on the cha- racterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators, we prove that if H and K are two finitely generated submonoids generated by prefix sets such that the product automaton associated to H ∩ K has a given special property then �(H ∩ K) ≤ �(H)�(K )w here�(L )=m ax(0,rk(L) − 1) for any submonoid L. Mathematics Subject Classification. 68Q70, 68Q45, 20M35.

Published
2006

12. The Average State Complexity of Rational Operations on Finite Languages

Author

Cyril Nicaud, Frédérique Bassino, Laura Giambruno, Nicaud, Cyril, Blanc - Génération Aléatoire : Modèles, Méthodes et Algorithmes - - GAMMA2007 - ANR-07-BLAN-0330 - BLANC - VALID, Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Matematica e Applicazioni [Palermo], Università di Palermo, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), ANR-07-BLAN-0330,GAMMA,Génération Aléatoire : Modèles, Méthodes et Algorithmes(2007), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Università degli studi di Palermo - University of Palermo, and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Asymptotically linear, Uniform distribution (continuous), 0102 computer and information sciences, 02 engineering and technology, State (functional analysis), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], State complexity, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Computer Science (miscellaneous), 020201 artificial intelligence & image processing, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract

Submitted, 21 pages.; International audience; Considering the uniform distribution on sets of m non-empty words whose sum of lengths is n, we establish that the average state complexities of the rational operations are asymptotically linear.

Catalog

Books, media, physical & digital resources
See catalog results