Transducers and repetitions (Q1820587): Difference between revisions

The factor transducer of a word associates to each of its factors (or subwords) their first occurrence. Optimal bounds on the size of minimal factor transducers together with an algorithm for building them are given. Analogous results and a simple algorithm are given for the case of subsequential suffix transducers. Algorithms are applied to repetition searching in words.

0 references

zbMATH Keywords

factor transducer of a word

0 references

subsequential suffix transducers

0 references

Algorithms

0 references

repetition searching in words

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0304-3975(86)90041-1

0 references

cites work

Efficient string matching

0 references

On the computational power of pushdown automata

0 references

The theory of languages

0 references

Optimal off-line detection of repetitions in a string

0 references

Q3859267

0 references

The smallest automaton recognizing the subwords of a text

0 references

A fast string searching algorithm

0 references

Q3673134

0 references

Q3692898

0 references

Fast Pattern Matching in Strings

0 references

Q3659988

0 references

Q3690246

0 references

A Space-Economical Suffix Tree Construction Algorithm

0 references

Q3885189

0 references

Compression of individual sequences via variable-rate coding

0 references

Identifiers

zbMATH Open document ID

0615.68053

0 references

DOI

10.1016/0304-3975(86)90041-1

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

journals/tcs/Crochemore86

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1820587

@@ Property / cites work @@
+Efficient string matching
@@ Property / cites work: Efficient string matching / rank @@
+Normal rank
@@ Property / cites work @@
+On the computational power of pushdown automata
@@ Property / cites work: On the computational power of pushdown automata / rank @@
+Normal rank
@@ Property / cites work @@
+The theory of languages
@@ Property / cites work: The theory of languages / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal off-line detection of repetitions in a string
+Normal rank
@@ Property / cites work @@
+Q3859267
@@ Property / cites work: Q3859267 / rank @@
+Normal rank
@@ Property / cites work @@
+The smallest automaton recognizing the subwords of a text
+Normal rank
@@ Property / cites work @@
+A fast string searching algorithm
@@ Property / cites work: A fast string searching algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+Q3673134
@@ Property / cites work: Q3673134 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3692898
@@ Property / cites work: Q3692898 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Pattern Matching in Strings
@@ Property / cites work: Fast Pattern Matching in Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Q3659988
@@ Property / cites work: Q3659988 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3690246
@@ Property / cites work: Q3690246 / rank @@
+Normal rank
@@ Property / cites work @@
+A Space-Economical Suffix Tree Construction Algorithm
+Normal rank
@@ Property / cites work @@
+Q3885189
@@ Property / cites work: Q3885189 / rank @@
+Normal rank
@@ Property / cites work @@
+Compression of individual sequences via variable-rate coding
+Normal rank
@@ Property / DBLP publication ID @@
+journals/tcs/Crochemore86
@@ Property / DBLP publication ID: journals/tcs/Crochemore86 / rank @@
+Normal rank