Dr Kyriakos Sgarbas (Κυριάκος Σγάρμπας, google:sgarbas) was born in Athens, Greece, in 1966. He is an Assistant Professor at the Department of Electrical and Computer Engineering of the University of Patras, Greece (http://www.upatras.gr) and an Instructor at the School of Science and Technology of the Hellenic Open University (http://www.eap.gr). His research interests include Symbolic and Quantum Artificial Intelligence and Computational Linguistics (http://publicationslist.org/sgarbas). He is a member of IEEE (http://www.ieee.org), ACM (http://www.acm.org), EETN (http://www.eetn.gr), and TEE (http://www.tee.gr).
Abstract: Natural language text analysis presupposes the encoding of morphological phenomena. In this article, we present some particularities of Modern Greek and the way these are encoded in the presented electronic lexicon. The project plan of its development combined both simple planning algorithms and more elaborate ones for the generation and recognition processes. The resulted lexicon exhibits fast access to its contents and easy content management. It is re-usable and modular enough to support existing NLP applications.
Abstract: This paper presents a quantum probability splitter, i.e. a quantum circuit that modifies the probability amplitudes of a qubit so that the probability on the selected basis state is halved. It also presents a potential application of this circuit related to qubit preparation: it shows how a qubit is prepared to a superposition of any valid pair of basis states probabilities, by repeated application of the quantum probability splitter.
Abstract: Background: The immune response to viral infection is a temporal process, represented by a dynamic and complex network of gene and protein interactions. Here, we present a reverse engineering strategy aimed at capturing the temporal evolution of the underlying Gene Regulatory Networks (GRN). The proposed approach will be an enabling step towards comprehending the dynamic behavior of gene regulation circuitry and mapping the network structure transitions in response to pathogen stimuli.
Results: We applied the Time Varying Dynamic Bayesian Network (TV-DBN) method for reconstructing the gene regulatory interactions based on time series gene expression data for the mouse C57BL/6J inbred strain after infection with influenza A H1N1 (PR8) virus. Initially, 3500 differentially expressed genes were clustered with the use of k-means algorithm. Next, the successive in time GRNs were built over the expression profiles of cluster centroids. Finally, the identified GRNs were examined with several topological metrics and available protein-protein and protein-DNA interaction data, transcription factor and KEGG pathway data.
Conclusions: Our results elucidate the potential of TV-DBN approach in providing valuable insights into the temporal rewiring of the lung transcriptome in response to H1N1 virus.
Abstract: Anxiety disorders are considered the most prevalent of mental disorders. Nevertheless, the exact reasons that provoke them to patients remain yet not clearly specified, while the literature concerning the environment for monitoring and treatment support is rather scarce warranting further investigation. Toward this direction, in this study a context-aware approach is proposed, aiming to provide medical supervisors with a series of applications and personalized services targeted to exploit the multiparameter contextual data collected through a long-term monitoring procedure. More specifically, an application that assists the archiving and retrieving of the patients' health records was developed, and four treatment supportive services were considered. The three of them focus on the discovery of possible associations between the patient's contextual data; the last service aims at predicting the stress level a patient might suffer from, in a given context. The proposed approach was experimentally evaluated quantitatively (in terms of computational efficiency and time requirements) and qualitatively by experts on the field of mental health domain. The feedback received was very encouraging and the proposed approach seems quite useful to the anxiety disorders' treatment.
Abstract: This paper addresses the problem of automatic induction of the normalized form (lemma) of regular and mildly irregular words with no direct supervision using language-independent algorithms. More specifically, two string distance metric models (i.e. the Levenshtein Edit Distance algorithm and the Dice Coefficient similarity measure) were employed in order to deal with the automatic word lemmatization task by combining two alignment models based on the string similarity and the most frequent inflectional suffixes. The performance of the proposed model has been evaluated quantitatively and qualitatively. Experiments were performed for the Modern Greek and English languages and the results, which are set within the state-of-the-art, have showed that the proposed model is robust (for a variety of languages) and computationally efficient. The proposed model may be useful as a pre-processing tool to various language engineering and text mining applications such as spell-checkers, electronic dictionaries, morphological analyzers etc.
Abstract: This paper introduces a statistical framework for extracting medical domain knowledge from heterogeneous corpora. The acquired information is incorporated into a natural language understanding agent and applied to DIKTIS, an existing web-based educational dialogue system for the chemotherapy of nosocomial and community acquired pneumonia, aiming at providing a more intelligent natural language interaction. Unlike the majority of existing dialogue understanding engines, the presented system automatically encodes semantic representation of a user's query using Bayesian networks. The structure of the networks is determined from annotated dialogue corpora using the Bayesian scoring method, thus eliminating the tedious and costly process of manually coding domain knowledge. The conditional probability distributions are estimated during a training phase using data obtained from the same set of dialogue acts. In order to cope with words absent from our restricted dialogue corpus, a separate offline module was incorporated, which estimates their semantic role from both medical and general raw text corpora, correlating them with known lexical-semantically similar words or predefined topics. Lexical similarity is identified on the basis of both contextual similarity and co-occurrence in conjunctive expressions. The evaluation of the platform was performed against the existing language natural understanding module of DIKTIS, the architecture of which is based on manually embedded domain knowledge.
Abstract: This study presents an algorithm for the transformation of DAWGs (Directed Acyclic Word Graphs) into equivalent Word Lattices (WLs). WLs are used in several applications (e.g. speech processing, language modeling etc.), whereas DAWGs as special cases of FSA (Finite State Automata) have a rich theoretical background. Although these two data structures have a resemblance, the transformation between the two forms is not at all trivial. The presented algorithm works for both deterministic and non-deterministic DAWGs.
Abstract: In this paper, we present an on-line algorithm for adding words (strings) in deterministic directed acyclic word graphs (DAWGs) i.e. acyclic deterministic finite-state automata (DFAs). The proposed algorithm performs optimal insertion, meaning that if applied to a minimal DAWG, the DAWG after the insertion will also be minimal. The time required to add a new word is O(n) with respect to the size of the DAWG. Repetitive application of the proposed insertion algorithm can be used to construct minimal deterministic DAWGs incrementally, although the algorithm is not time-efficient for building minimal DAWGs from a set of words: to build a DAWG of n words this way, O(n^2) time is required. However, the algorithm is quite useful in cases where existing minimal DAWGs have to be updated rapidly (e.g. speller dictionaries), since each word insertion traverses only a limited portion of the graph and no additional minimization operation is required. This makes the process very efficient to be used on-line. This paper provides a proof of correctness for the algorithm, a calculation of its time-complexity and experimental results.
Abstract: The automation of Directory Assistance Services (DAS) through speech is one of the most difficult and demanding applications of human-computer interaction because it deals with very large vocabulary recognition issues. In this paper, we present a spoken dialogue system for automating DAS.1 Taking into account the major difficulties of this endeavor a stepwise approach was adopted. In particular, two prototypes D1.1 (basic approach) and D1.2 (improved version) were developed successively. The results of D1.1 evaluation were used to refine D1.1 and gradually led to D1.2 that was also improved using a feedback approach. Furthermore, the system was extended and optimized so that it can be utilized in real-world conditions. We describe the general architecture and the three stages of the system''s development in detail. Evaluation results concerning both the speech recognizer''s accuracy and the overall system''s performance are provided for all prototypes. Finally, we focus on techniques that handle large vocabulary recognition issues. The use of Directed Acyclic Word Graphs (DAWGs) and context-dependent phonological rules resulted in search space reduction and therefore in faster response, and also in improved accuracy.
Abstract: The WATCHER project aims to automate the extraction of language resources from the Internet via an intelligent agent called the âWATCHERâ. This agent (in its final form) will be able to actively search and collect subject-specific and language-specific texts and build corpora and lexicons from them. Although the resources will still have to be checked for validity after their collection, the proposed method requires the minimum of human interaction. Apart from its ability to collect these resources automatically, the WATCHER will also be able to track the evolution of a target language over time by collecting resources annually and presenting their analysis in annual reports. The WATCHER is still under development. This paper presents an overview of its architecture and functionality, and reports recent progress.
Abstract: This paper presents an implementation of a syntactic parser for the Modern Greek language based on the PC-PATR formalism. The Modern Greek language presents a high flexibility in its syntactic structure. The various phrasal categories (noun phrases, verb phrases, prepositional, and adverbial phrases) can be ordered in almost any permutation so as to build valid sentences. The allowable combinations of lexical categories (nouns, verbs, adjectives, etc.) forming the above phrases, as well as the combinations of these phrases, forming clauses, are encoded according to the PC-PATR formalism and are presented in this paper. The presented rules cover the majority of the syntactic phenomena of the Modern Greek language, adequate for speech and natural language applications.
Abstract: This report confronts the problem of automatic conversion from graphemic to phonetic transcription and vice versa for the Modern Greek language. A single representation is used for both directions of word transformation, based on PCKIMMO, a development environment originally used for the implementation of two-level morphological processors. The fifty-two two-level rules that are presented have been tested on a set of the 10,000 most frequent Modern Greek words and they describe the Greek phonology in adequate detail for use by a speech-processing system.
Notes: This paper addresses the problem of the automatic conversion of Greek words from graphemic to phonetic form and vice-versa using Two-Level rules. The proposed method obtains a consistent bi-directional conversion using only one set of transformation rules. The presented converter utilises 52 Two-Level rules which have been checked for correctness in the set of 10,000 most frequent Greek words as derived from general purpose text corpora. This implementation describes the pholological phenomena of Modern Greek in adequate detail to be used in speech processing systems and it is fully compatible with the morphological processor described in "A PC-KIMMO-Based Morphological Description of Modern Greek".
Abstract: This paper describes a temporal parser (TEMPO) introducing a semantic approach to the detection and analysis of quantifiers of time within simple texts. TEMPO processes expressions which implicitly contain a date, like "last Sunday", "two days ago" etc., and extracts the exact date. It uses a keyword-driven parsing technique to spot the quantifiers and then separates segments of the sentence around the keywords and passes them to a semantic DCG parser. Though developed for Greek, the presented scheme can be easily transferred to other languages. TEMPO might prove useful in the automatic processing of special kings of documents which require the extraction of time information, such as applications, legal documents, contracts, etc.
Notes: This paper addresses the development of a semantic analyzer for temporal expressions based on a keyword-driven parsing technique and Definite Clause Grammar. It describes improvements over a previous paper ("A Temporal Analyzer for Unrestricted Text"). In the new version the analyzer can detect five different types of temporal expressions and can extract semantic information of any combination of them in unrestricted depth.
Abstract: In this paper we present two algorithms for building lexicons in Directed Acyclic Word-Graphs (DAWGs). The two algorithms, one for deterministic and the other for non-deterministic DAWGs, can be used instead of the traditional subset construction method. Although the proposed algorithms do not produce the optimal DAWG (i.e., the one with the minimum number of states), they are simple, fast and able to build the DAWG incrementally, as new words are added to the lexicon. Thus, building large lexicons in a DAWG structure becomes an easy task, even for a modest computer.
Notes: In this paper we describe two algorithms for constructing lexicons in Directed Acyclic Word Graphs (DAWG). The first algorithm builds deterministic graphs while the second one builds non-deterministic graphs. These algorithms can be used instead of the traditional subset construction method giving the advantage of speed and the incremental construction, since they are able to actually add new words in an already existing graph, slightly modifying its structure. The use of DAWG-based lexicons greatly facilitates the speech and natural language processing tasks since content addressable search can be easily performed in DAWGs.
Abstract: This paper demonstrates the use of genetic algorithms in game-playing and it examines whether a genetic algorithm could replace the heuristic evaluation functions that are commonly used in that field. Using a simple but non-trivial board game as an example, the paper shows how a genetic algorithm learns by playing the game by itself and how it develops an acceptable strategy without deep searching in the problem state-space.
Abstract: This paper presents the implementation of a morphological processor for the Modern Greek language. The processor is based on the two-level morphology model introduced by Koskenniemi (1983). The presented description is complete for all regular Greek nouns, adjectives, and verbs which constitute the basis of the entire Greek declension system. Modern Greek is a highly inflectional language. The thirty-six two-level rules and the structure of sixty-three declension categories presented in the Appendices have been developed using the PC-KIMMO environment and are compatible with PC-KIMMO version 2.0 software. Irregular forms do exist in Greek morphology but at present they are faced separately and they are not included in this implementation. Sample results and the base lines of the two-level model are also presented.
Notes: This paper describes the development of a morphological parser for the Modern Greek language, based on the Two-Level morphological model. The parser uses 36 rules that determine both directions of transformation: analysis and synthesis. The presented description is complete for all regular nouns, adjectives and verbs. The significant theoretical value of the paper is that it proves that the morphological phenomena of Modern Greek can be adequately represented by the general framework of the Two-Level morphological model.
Notes: This paper describes the structure of a flexible semantic parser suitable for Natural Language Processing applications. Its architectural originality is based on a set of independent modules, each one functioning as a semantic sub-parser. The parser is considered "flexible" because it does not perform strict syntactic analysis based on predefined structures and lexicon but instead it tries to extract the maximum possible amount of information even from sentences that contain syntactic irregularities and unknown words. Although this flexibility has the drawback of making the parser application dependent, the parser can be easily modified by the addition on new modules or the modification of the existing ones. The proposed structure allows independent and (using the appropriate hardware) parallel function of its modules thus facilitating the development of real-time large-knowledge-base applications.
Notes: This paper describes the results of the "Spoken Language Engineering" workgroup of the Socrates "Thematic Network in Speech Communication Sciences" project. This workgroup, after studying for three years many existing relevant courses in European Universities and having already proposed a unified syllabus in the area of Spoken Language Processing both in graduate and post-graduate level, it has completed its work by examining and recording the available sources of teaching material for this purpose. This research was focused on computer-based instructional & educational aids that are accessible through the Internet. In this work a collection of notable web-sites is presented, grouped by subject, with brief content analysis and evaluation according to their possible use in the intended syllabus.
Notes: This chapter describes the work of the Socrates working group in "European Masters in Language and Speech", which concerns the development of a interdepartmental post-graduate curriculum among European Universities which will lead to a Master in Language and Speech. Ten European Universities have started this cooperation since 1997. The programme is scheduled to receive the first students in September 1999.
Notes: This report presents the results of the work group on "Spoken Language Engineering" initiated in the framework of Socrates "Thematic Network on Speech Communication Sciences". The program covers over 100 Departments in European Universities that teach Phonetics, Spoken Language Engineering and Speech & Language Therapy and aims to the recording of the current situation of the education in the aforementioned fields, to its analysis and finally to the conclusion of proposals for the improvement of the educational status provided by the Universities. The report presents results of a study concerning whether the courses taught at European Universities are in accordance with the skills requested by the speech industry and introduces a full graduate level Spoken Language Engineering curricullum with emphasis in computer-assisted and distant learning.
Abstract: Teaching introduction to computing courses, especially to first year college students, is a challenging endeavor given the increasing difficulty of today's students with programming and algorithmic thinking. In this paper the experience of introducing collaborative and project based approaches in a first year University course is reported. Both synchronous collaborative learning approaches and asynchronous collaboration through group project work have been introduced in the course using Python as a programming language. The effect of use of these approaches in students' attitude towards Computer Science and their performance is discussed here.
Abstract: A large Greek-English Dictionary with 81,515 entries, 192,592 translations into English and 50,106 usage examples with their translation has been developed in combined printed and electronic (DVD) form. The electronic dictionary features unique facilities for searching the entire or any part of the Greek and English section, and has incorporated a series of speech and language processing tools which may efficiently assist learners of Greek and English. This paper presents the human-machine interface of the dictionary and the most important tools, i.e. the TTS-synthesizers for Greek and English, the lemmatizers for Greek and English, the Grapheme-to-Phoneme converter for Greek and the syllabification system for Greek.
Abstract: While anxiety disorders exhibit an impressive spread especially in western societies, context-awareness seems a promising technology to provide assistance to physicians in psychotherapy sessions. In the present paper an approach addressing the assistance of the anxiety disordersâ treatment is proposed. The suggested method employs the a priori association rule mining algorithm in order to achieve dynamic update of patient profiles according to generated rules describing the underlying relations between patientsâ main context conditions and their stress level. This method was evaluated by therapists specializing in the mental health domain and the feedback received was very encouraging with respect to the assistance dynamic patient profiles offer, during CBT sessions.
Abstract: In the present work we have implemented the Edit
Distance (also known as Levenshtein Distance) on a
dictionary-based algorithm in order to achieve the
automatic induction of the normalized form (lemma) of
regular and mildly irregular words with no direct
supervision. The algorithm combines two alignment
models based on the string similarity and the most
frequent inflexional suffixes.
In our experiments, we have also examined the
language-independency (i.e. independency of the specific
grammar and inflexional rules of the language) of the
presented algorithm by evaluating its performance on the
Modern Greek and English languages. The results were
very promising as we achieved more than 95% of
accuracy for the Greek language and more than 96% for
the English language. This algorithm may be useful to
various text mining and linguistic applications such as
spell-checkers, electronic dictionaries, morphological
analyzers, search engines etc.
Abstract: In the present work we used a word clustering algorithm based on the
perplexity criterion, in a Dialogue Act detection framework in order to model
the structure of the speech of a user at a dialogue system. Specifically, we
constructed an n-gram based model for each target Dialogue Act, computed
over the word classes. Then we evaluated the performance of our dialogue
system on ten different types of dialogue acts, using an annotated database
which contains 1,403,985 unique words. The results were very promising since
we achieved about 70% of accuracy using trigram based models.
Abstract: This paper overviews the basic principles and recent advances in the emerging field of Quantum Computation (QC), highlighting its potential application to Artificial Intelligence (AI). The paper provides a very brief introduction to basic QC issues like quantum registers, quantum gates and quantum algorithms and then it presents references, ideas and research guidelines on how QC can be used to deal with some basic AI problems, such as search and pattern matching, as soon as quantum computers become widely available.
Abstract: This paper describes the application of decision-tree based induction techniques for automatic extraction of
phonetic knowledge for the Greek language. We compare the ID3 algorithm and Quinlanâs C4.5 model by
applying them to two pronunciation databases. The extracted knowledge is then evaluated quantitatively. In
the ten cross-fold validation experiments that are conducted, the decision tree models are shown to produce
an accuracy higher than 99.96% when trained and tested on each dataset.
Abstract: In this paper, we present an alternative idea for the data retrieval from directed acyclic word graphs
(DAWG). The proposed algorithm is adequate for both the deterministic (DFA) and the nondeterministic
(NFA) finite state automata and can be used instead of other traditional data extraction
methods. The suggested algorithm is capable of retrieving the data contained in such data structures
in a quite simple and fast way and can be used in several applications which are treating of finite state
automata, natural language processing and data mining. Such applications are the following: lexicon
building, morphological processing, speech recognition, DNA analysis etc. This paper also provides
experimental verification of the correctness of the algorithm and several experimental results.
Notes: This paper presents and analyzes an incremental algorithm for the construction of Acyclic Non-deterministic Finite-state Automata (NFA). Automata of this type are quite useful in computational linguistics, especially for storing lexicons. The proposed algorithm produces compact NFAs, i.e. NFAs that do not contain equivalent states. Unlike Deterministic Finite-state Automata (DFA), this property is not sufficient to ensure minimality, but still the resulting NFAs are considerably smaller than the minimal DFAs for the same languages.
Notes: The Watcher project aims to automate the extraction of language resources from the Internet via an intelligent agent called the âWatcherâ. This agent will be able to actively search and collect subject-specific and language-specific texts and build corpora and lexicons based on them. Although the resources will have still to be checked for validity after their collection, the proposed method requires the minimum of human interaction. Apart from its ability to collect these resources automatically, Watcher will also be able to track the evolution of a target language over time by collecting resources annually and presenting their analysis in annual reports. Watcher is still under development. This paper presents an overview of its architecture and functionality and reports recent progress.
Notes: This paper briefly presents educational and research activities at the University of Patras in Speech Technology. The paper is addressed mainly to the associated countries of the European Union, in the framework of Socrates Thematic Network in Speech Communication Sciences. Curricula concerning the European Masters in Language and Speech are also presented, along with statistics concerning related educational and research activities.
Notes: Some speech recognition applications, like automatic telephone directory services, require very large vocabularies, e.g. surnames, firstnames, city names, etc. In the network-based language models those words, single or within context, constitute all the possible paths of a finite-state network which is traversed during the recognition process in order to produce the best candidate output. In this paper we present a method of replacement of word-based networks by phoneme-based ones, thus reducing their size without affecting the valid phoneme combinations that compose the word utterances. This way the recognition accuracy is preserved while obtaining real-time response. As the size of the lexicon grows, the gain in response time becomes more evident. This method has been used in the task of surname recognition to an interactive directory servicing system Experimental results produced by Entropic's HΤΠApplication Programming Interface (ÎAPI) have proved the efficiency of the proposed method.
Notes: This paper presents a straightforward approach to the problem of morphological processing. Specifically, a DAWG (Directed Acyclic Word Graph) is used to store both the lexicon and the accompanied morphological information, in such a way that both morphological analysis and synthesis can be reduced to a search in the graph. We have used the algorithms described in "Two Algorithms for Incremental Construction of Directed Acyclic Word Graphs" for the creation and update of the structure and the morphological information presented in "A PC-KIMMO-Based Morphological Analysis of Modern Greek" and "A Morphological Description of Modern Greek using the Two-Level Model".
Notes: This paper presents a morphological description of the Modern Greek language based on the Two-Level morphology model. The implementation uses 36 rules that describe diphthogs, stress shift, syllabism, augmentation and other relevant phenomena of the Modern Greek morphology, covering nouns, adjectives, regular verbs and participles as verb moods. This paper complements the previous one "A PC-KIMMO-Based Morphological Description of Modern Greek", explaining in detail the coding of the declinable parts of speech and the 30.000-lemma lexicon that was used in the description.
Notes: This paper describes the model, the structure, the procedures and the contents of the "European Masters in Language and Speech", an inter-European post-graduate syllabus which has been created by the combined effort of 11 European Universities and has started since 1999 under the auspices of ISCA and of EACL.
Notes: This paper examines the automatic word conversion between graphemic and phonetic transcription using three different methods: hidden Markov models, phonetic rules and finite-state transducers. The strong and weak points of each method are examined in comparison to each other and quantitative results are presented concerning development prototypes in integrated systems.
Notes: This paper describes a method for automatic extraction of language resources from the Internet using an intelligent agent that we call the "Watcher". This project focuses on the development of the required infrastructure in the framework of ELSNET (http:/www.elsnet.org) in order to provide language resources and related information to its members. The Watcher will be able to function without supervision and gather automatically text corpora and lexicons according to subject-specific and language-specific search criteria. The proposed method minimizes the human intervention in the process of language resources collection. As described in the paper, the Watcher has the additional ability to track the evolution of a language over time and record the results in automatically generated annual reports.
Notes: This report describes the research activities of the Wire Communication Laboratory (WCL) of the Department of Electrical and Computer Engineering, University of Patras , Greece, in the field of Natural Language Processing. The research focuses automatic analysis and synthesis of the Modern Greek language in lexical, morphological, syntactic, semantic and pragmatic levels and includes dialogue models and extraction of stylistic information from texts.
Notes: Description of a morphological information representation model suitable for inflectionally rich languages. The proposed model is composed by a set of independent modules, each one examining different aspects of the input word. A communication protocol is also defined fot the transfer of information among the modules. This model has been developed in Prolog as an executable representation. It also enables the rearrangement of the modules thus resulting in modification of the functionality of the whole system.
Notes: This paper describes the development of a semantic analyzer of temporal expressions for Modern Greek, This analyzer locates and analyzes expressions like "next Tuesday", "2 days ago", etc. and returns the corresponding date. The analyzer is modular and can be used in any application that demands the extraction of date information from natural language texts. Although built for Modern Greek, the described technique can be extended to other languages as well.
Notes: This PhD dissertation addresses problems that belong to the lexical, grammatic, morphologic, syntactic and semantic levels of natural language processing and proposes novel rule based Artificial Intelligence analysis techniques for their confrontation. In particular, it describes the use of Directed Acyclic Word Graphs (DAWG) for the lexical level so that content addressable word search can be facilitated, the use of the Two-Level model for the morphological analysis utilizing parallel finite-state transducers, the development of a syntactic analyzer based on a feature-based grammatical formalism for the determination and parsing of word groups in sentences, the development of a semantic analyzer for temporal expressions and the finally the development of a preprocessing module for interface with speech recognition systems.
Notes: This diploma dissertation presents the architecture and functionality of a natural language understanding system, based on artificial intelligence methods. The presented system utilizes grammatic, syntactic, semantic and pragmatic rules in order to process the input sentences. The system is also able to answer to natural language questions concerning the content of the facts it has understood. Special effort has been given towards the imitation of the way that a human realizes common speech. Thus the system has been designed to understand elliptic sentences, assumming the missing entities that a human could assume under the same conditions.
Notes: This report provides a proof that the incremental algorithm for deterministic DAWGs originally presented in "Two Algorithms for Incremental Construction of Directed Acyclic Word Graphs" performs optimal insertion, meaning that if applied to a minimal DAWG, the DAWG after the insertion will also be minimal. Repetitive application of the insertion algorithm can be used to construct minimal deterministic DAWGs (i.e. minimal acyclic DFSAs) incrementally. To add a new word using this algorithm, O(n) time is required, with respect to the size of the DAWG. To build a complete DAWG of n words this way, O(n2) time is required. However, the algorithm is quite useful in cases where existing minimal DAWGs have to be updated rapidly (e.g. speller dictionaries), since each word insertion traverses only a limited portion of the graph and no additional minimization operation is needed. This makes the process very efficient to be used on-line. This report also includes a proof of correctness, a complexity calculation and additional experimental results for the algorithm.
