Transducers and Repetitions

Maxime Crochemore · Theoretical Computer Science · 1986

Summary

Optimal bounds on the size of minimal factor transducers together with an algorithm for building them are given and analogue results and a simple algorithm are given for the case of subsequential suffix transducers.

Type: article
Published: 1986-06-01
Cited by: 243
References: 19
Access: Open access
DOI: https://doi.org/10.1016/0304-3975(86)90041-1
OpenAlex: https://openalex.org/W2154104338
Semantic Scholar: https://api.semanticscholar.org/CorpusID:8482161

Keywords

Suffix, Repetition (rhetorical device), Simple (philosophy), Algorithm, Factor (programming language)

References

Principles of Compiler Design (Addison-Wesley series in computer science and information processing)Alfred V. Aho, Jeffrey D. Ullman — 1977
Linear size finite automata for the set of all subwords of a word - an outline of resultsAnselm Blumer, J. Blumer, Andrzej Ehrenfeucht — 1983
Transductions and context-free languagesJean Berstel — 1979
Principles of Compiler DesignAlfred V. Aho, Jeffrey D. Ullman — 1977
The Design and Analysis of Computer AlgorithmsAlfred V. Aho, John E. Hopcroft — 1974
The Smallest Automaton Recognizing the Subwords of a TextAnselm Blumer, J. Blumer, David Haussler — 1985
Fast Pattern Matching in StringsDonald E. Knuth, James H. Morris, Vaughan Pratt — 1977
Optimal Off-Line Detection of Repetitions in a StringAlberto Apostolico, F. P. Preparata — 1983
A fast test for unique decipherability based on suffix treesMichael Rodeh — 1982
Efficient string matchingAlfred V. Aho, Margaret J. Corasick — 1975
A Space-Economical Suffix Tree Construction AlgorithmEdward M. McCreight — 1976
Compression of individual sequences via variable-rate codingJ. Ziv, A. Lempel — 1978
A fast string searching algorithmRobert S. Boyer, J Strother Moore — 1977
Recherche linéaire d'un carré dans un motMaxime Crochemore — 1983
Linear Pattern Matching AlgorithmsPeter Weiner — 1973
Optimal Factor TransducersMaxime Crochemore — 1985
PRINCIPLES OF COMPILER DESIGNM. Ganaga Durga, T. G. Manikumar, M Ganga Durga — 2019
Linear Time Recognition of Squarefree StringsM. Main, Richard J. Lorentz — 1985

Cited by

Suffix trees and their applications in string algorithmsRoberto Grossi, Giuseppe F. Italiano — 1993
Search Problems for Speech and Audio SequencesMehryar Mohri, Eugene Weinstein — 2009
Minimizing incomplete automataMarie-Pierre Béal, Maxime Crochemore — 2008
A Hybrid Indexing Method for Approximate String MatchingGonzalo Navarro, Ricardo Baeza-yates — 2007
Automates et algorithmes sur les motsDominique Perrin — 1989
Efficient String Matching on Packed TextsDany Breslauer, Leszek Gąsieniec — 1996
Testing Square-Freeness of Strings Compressed by Balanced Straight Line ProgramWataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara — 2009
Utilización de un índice métrico para búsqueda aproximada de patronesVerónica Ludueña, Gonzalo Navarro — 2005
Algorithms for Memory HierarchiesUlrich Meyer — 2003
COMPUTING REPETITIONS IN STRINGS: CURRENT ALGORITHMS & THE COMBINATORICS OF FUTURE ONES.Evguenia Kopylov — 2010
Efficient computation of regularities in strings and applicationsMunina Yusufu — 2009
USING SUFFIX ARRAYS FOR LEMPEL-ZIV DATA COMPRESSIONAnisa Al-Hafidh — 2009
Efficient Development of Lexical Language Resources and their RepresentationMatej Rojc, Zdravko Kačič — 2003
Mathematical Foundations of Computer Science 2012Branislav Rovan, Vladimiro Sassone, Peter Widmayer — 2012
Indexing trees by pushdown automata for nonlinear tree pattern matchingJan Trávníček, Jan Janoušek, B. Melichar — 2011
Finding Maximal Pairs with Bounded GapGerth Stølting Brodal, Rune B. Lyngsø, Christian N. S. Pedersen — 1999
The Architecture of a Software Library for String ProcessingArtur Czumaj, Paolo Ferragina, Leszek Gąsieniec — 1997
Algebra of programmingRichard Bird, Oege de Moor — 1997
On the construction and application of compressed text indexesWing-Kai Hon — 2004
On the complexity of computing the order of repetition of a stringJuhani Karhumäki, Wojciech Plandowski, WOJCIECH RYTTER — 2000

Transducers and Repetitions

Summary

Keywords

References

Cited by

Related papers