Talk:Suffix automaton

A fact from Suffix automaton appeared on Wikipedia's Main Page in the Did you know column on 22 November 2020 (check views). The text of the entry was as follows:

Did you know... that although the suffix automaton, a data structure used in computer science, was introduced in 1983, it appeared in a 1973 scholarly article as an auxiliary structure?

A record of the entry may be seen at Wikipedia:Recent additions/2020/November. The nomination discussion and review may be seen at Template:Did you know nominations/Suffix automaton.

Wikipedia

Computer science Low‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Low

This article has been rated as Low-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

CSB tag removed[edit]

I removed

because CorenSearchBot recognized the article as a copy of itself. Bug report here. QVVERTYVS (hm?) 20:34, 7 October 2014 (UTC)[reply]

Merge suffix automaton and directed acyclic word graph[edit]

Suffix automaton and directed acyclic word graph are same things. --Abionab (talk) 04:05, 1 November 2015 (UTC)[reply]

Minimality of the automaton.[edit]

The article didn't require the automaton to be minimal and deterministic. I added that requirement, because it is how the suffix automaton is usually defined in the literature. See e.g. the well-cited papers:

Blumer, Anselm, et al. "The smallest automation recognizing the subwords of a text." Theoretical computer science 40 (1985): 31-55.

Ukkonen, Esko. "On-line construction of suffix trees." Algorithmica 14.3 (1995): 249-260.

I also defined DAWG to be the state graph of the suffix automaton without designated accepting or rejecting states as in Blumer's paper.

Rewrite[edit]

I expanded and rewrote the article. I hope everything is correct. — Preceding unsigned comment added by Jnalanko (talk • contribs) 07:45, 23 June 2018 (UTC)[reply]

Another rewrite[edit]

Hi there! I'm the author of the featured article ru:Суффиксный автомат about this subject in Russian Wikipedia. I'm currently working on its translation and want to merge it with current version. Work in progress is here, feel free to leave any comments and/or suggestions. adamant.pwn — contrib/talk 03:02, 2 September 2020 (UTC)[reply]