On-line construction of a small automaton for a finite set of words (Q2909196)

The paper presents the first stage of a semi-incremental algorithm for constructing a minimal, deterministic, acyclic finite automaton. The language of the automaton is a finite set of finite words, so it can be used e.g. for representing dictionaries. The input is a set of words sorted on lexicogrphic order of the reversed words. The main algorithm described in the text appears to be correct. However, the are a few problems with the article.NEWLINENEWLINEIt is not sufficient to give a new algorithm for a problem that already has some solutions. It should be demonstrated that the new algorithm is at least in some respect better than the other ones. The authors make a few claims about their solution, mainly that it is ``extremely fast'', and that the automaton it delivers is close to the minimal one. They present results of their experiments that aim to demonstrate that the automata they produce are indeed very small. While the authors are aware of related work, they make absolutely no attempt to compare their results with those of other algorithms.NEWLINENEWLINEThe authors claim that their algorithm is ``light''. If they mean simple, it is not any ``lighter'' than other algorithms. If they mean fast, and indeed they claim that their algorithm ``allows an extremely fast compiling of the set of words'', they should provide results of experiments that support that claim. The authors give computational complexity of their algorithm, which is the same or similar (the same under some assumptions) to the other algorithms they cite.NEWLINENEWLINEThe authors present some data on the relation of the size of the automata they produce to the size of the equivalent minimal automata. However, they make no attempt to compare that size to the size of an intermediate automaton in Revuz's algorithm and in Watson's algorithm. Especially Revuz's algorithm needs much attention here because the input data is sorted in exactly the same way. The first stage in Revuz's algorithm produces a pseudo-minimal automaton. As such, it is interesting because it can be used for implementation of arbitrary (not only minimal) hashing. The size of the automaton produced by the new algorithm is not smaller than that of the pseudo-minimal one, but the relation of the automata is not investigated in the paper.NEWLINENEWLINEIn what follows I list minor problems and typos I noticed:NEWLINENEWLINE page 281, last line: ``many software'' -- software is not countable.NEWLINENEWLINEpage 282, line 19: while referring to the reference [7], the authors write about ``an algorithm'', when that paper describes two different incremental algorithms.NEWLINENEWLINEpage 283, definitions: definitions of a suffix and a factor should also be given; an automaton and an alphabet have the same letter in different fonts, which makes it more difficult to distinguish.NEWLINENEWLINEpage 283, line 15/16 from the bottom: ``obtained reversing'' -- ``obtained by reversing''.NEWLINENEWLINEpage 283, line 11 from the bottom: ``will recognizes'' -- either ``will recognize'' or better ``recognizes''.NEWLINENEWLINESubsection 2.2: In-degreee-Control and other ``Controls'' -- did the authors mean ``check''?NEWLINENEWLINEpage 285, line 10: when referring to Lemma 2, which is several pages later on, the page number should be given.NEWLINENEWLINEpage 287, line 4: ``it is also reported the right construction of the automaton'' -- the right construction of the automaton is also reported.NEWLINENEWLINEpage 287, line 4: ``We have proved the following:'' -- this has not happened, at least not yet.NEWLINENEWLINEpage 288: this should go after the pseudo code is given so that the construction details are clear.NEWLINENEWLINEpage 290, first line below the algorithm Add-word: ``such a function'' -- that function.NEWLINENEWLINEpage 291, line 3 from the bottom: ``such a function'' -- that function.NEWLINENEWLINEpage 293, line 1: ``In what follow'' -- In what follows, ``investigated on some'' -- investigated some.NEWLINENEWLINEpage 294, line 1 from the bottom: ``We can find in'' -- missing direct object.NEWLINENEWLINEpage 295, line 2 from the bottom: ``removing \(r\) by the set'' -- removing \(r\) from the set.NEWLINENEWLINESubsection 5.1.: no pseudo-code given.