Home // COGNITIVE 2020, The Twelfth International Conference on Advanced Cognitive Technologies and Applications // View article

Induced Acyclic Subgraphs With Optimized Endpoints

Authors:
Moussa Abdenbi
Alexandre Blondin Massé
Alain Goupil

Keywords: Directed graphs; learning strategies; computationallinguistics.

Abstract:
Given a lexicon, can we build a strategy for learning specialized vocabulary? If so, how to minimize its cost while maximizing its efficiency? We provide elements of answers to these questions, by using graph theory. A lexicon is represented by a directed graph of the defining relation between words and a strategy is an ordered sequence of vertices. We focus on two graphs properties, acyclicity which helps us to avoid words with cyclic definitions and induced to consider all the arcs between chosen words. We are interested in the induced and acyclic subgraphs of a directed graph containing a fixed set of vertices. To model cost minimization, we consider an optimization criteria based on the difference between the number of sinks and the number of sources of the subgraph, which represents words which appear in several definitions. We start with a study of the complexity of finding these subgraphs and we prove that it is a Non-deterministic Polynomial-time hard (NP-hard) problem. This observation leads us to provide two approximate solutions: agreedy heuristic and a local search enriched with tabu restrictions. Finally, we evaluate the efficiency of this graph based strategy comparing with psycholinguistic based strategies, on three digital dictionaries.

Pages: 44 to 49

Copyright: Copyright (c) IARIA, 2020

Publication date: April 26, 2020

Published in: conference

ISSN: 2308-4197

ISBN: 978-1-61208-780-1

Location: Nice, France

Dates: from October 25, 2020 to October 29, 2020