La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time)
type: Item
instance of: scholarly article
title: La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time)
zbMATH Open document ID: 0663.68090
DOI: 10.1016/0304-3975(88)90116-8
author: Jean-Claude Spehner
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: First we give here an on-line construction of a transducer \({\mathfrak F}(L)\) which recognizes all the factors of a finite language L and positions each factor as a factor of a word from L. \({\mathfrak F}(L)\) can be twice smaller than the partial automaton introduced by \textit{A. Blumer}, \textit{J. Blumer}, \textit{D. Haussler}, \textit{R. McConnel} and \textit{A. Ehrenfeucht} [J. Assoc. Comput. Mach. 34, 578-595 (1987)] which recognizes the same words. Though, the complexity of the construction of \({\mathfrak F}(L)\) is in \(O(\| L\| \cdot (| A| +\min (| L|,\quad lg\max)))\) where \(| L|\) and \(| A|\) are respectively the cardinality of L and of its alphabet A, \(\| L\|\) is the sum of the lengths of the words from L and lgmax is the maximal length of these words and not in \(O(\| L\|).\) Then we build a second transducer \({\mathfrak F}'(L)\) which has the same states as \({\mathfrak F}(L)\) and which finds, for each factor u of L and each letter a of A such that ua is not a factor of L, the largest right factor of ua which is a factor of L. \({\mathfrak F}'(L)\) generalizes the transducer we have introduced for a unique word [Theor. Comput. Sci. 48, 35-52 (1986; Zbl 0626.68058)]. The determination of \({\mathfrak F}'(L)\) is in \(O(\| L\| \cdot | A|).\) By using the transducers \({\mathfrak F}(L)\) and \({\mathfrak F}'(L)\), we obtain an algorithm which finds all the occurrences of the factors of L in a text in time linear in the length of the text and independently of the cardinality of the alphabet of this text. This algorithm can be used in computing to find and modify a family of identifiers in a program. Linguists can also determine all the words of a same family or related to a same concept - paronym words may be eliminated.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4085055
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90116-8
OpenAlex ID: W2094579735
cites work: Efficient string matching
cites work: Q3859267
cites work: Q3217631
cites work: The smallest automaton recognizing the subwords of a text
cites work: Complete inverted files for efficient text retrieval and analysis
cites work: A fast string searching algorithm
cites work: A Space-Economical Suffix Tree Construction Algorithm
cites work: Q3690247
cites work: Q3692898
cites work: Transducers and repetitions
cites work: Q4430284
cites work: Q4079524
cites work: Fast Pattern Matching in Strings
cites work: Q3659988
cites work: Linear Automaton Transformations
cites work: La reconnaissance des facteurs d'un mot dans un texte
cites work: Sur les automates qui reconnaissent une famille de langages. (On the automata which accept a family of languages)
description: scientific article; zbMATH DE number 4085055