Efficient algorithms on the Moore family associated to an implicational system.
Page 1
Bertet, Karell, Nebut, Mirabelle (2004)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Auber, David, Delest, Maylis, Domenger, Jean-Philippe, Dulucq, Serge (2006)
Journal of Graph Algorithms and Applications
Dejan Simić, Dušan Starčević (1999)
The Yugoslav Journal of Operations Research
Chen, Wei-Mei, Hwang, Hsien-Kuei, Tsai, Tsung-Hsi (2003)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre (2009)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We present an on-line linear time and space algorithm to check if an integer array is the border array of at least one string built on a bounded or unbounded size alphabet . First of all, we show a bijection between the border array of a string and the skeleton of the DFA recognizing , called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a skeleton of SMA...
Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre (2008)
RAIRO - Theoretical Informatics and Applications
We present an on-line linear time and space algorithm to check if an integer array f is the border array of at least one string w built on a bounded or unbounded size alphabet Σ. First of all, we show a bijection between the border array of a string w and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a...
Page 1