✦ LIBER ✦

On the minimum vocabulary problem

✍ Scribed by Chandrasekharan, N. ;Sridhar, R. ;Iyengar, S.S.

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 557 KB
Volume: 38
Category: Article
ISSN: 0002-8231
DOI: 10.1002/(sici)1097-4571(198707)38:4<234::aid-asi3>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

The "minimum vocabulary problem" for a dictionary has applications in indexing and other domains of information retrieval. A simple directed-graph model of a dictionary results in a linear-time algorithm for this problem. Since it is known that many minimum vocabularies can exist for a dictionary, a computationally useful criterion for finding a "desirable minimum vocabulary" is suggested and an O(lV13) algorithm is outlined, where /VI is the number of words in the dictionary, duplicates eliminated. Furthermore, some enrichments to the model and the computational intractability of a variant called the l-lexicon problem are discussed. Directions for further work are indicated.

📜 SIMILAR VOLUMES

On the minimum cut separator problem

✍ Walid Ben-Ameur; Mohamed Didi Biha 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB

On the generalized minimum spanning tree

On the generalized minimum spanning tree problem

✍ Young-Soo Myung; Chang-Ho Lee; Dong-Wan Tcha 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 748 KB

Fly Cheaply: On the Minimum Fuel Consump

Fly Cheaply: On the Minimum Fuel Consumption Problem

✍ Timothy M. Chan; Alon Efrat 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 82 KB

In planning a flight, stops at intermediate airports are sometimes necessary to minimize fuel consumption, even if a direct flight is available. We investigate the problem of finding the cheapest path from one airport to another, given a set of n airports in 2 and a function l 2 × 2 → + representing

On the minimum path problem in Knödel gr

On the minimum path problem in Knödel graphs

✍ Hovhannes A. Harutyunyan; Calin D. Morosan 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

The minimum dummy task problem

✍ Jeremy Spinrad 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 879 KB

The problem of minimizing the number of dummy tasks in a PERT network was shown to be NP-complete by Krishnamoorthy and Deo [9]. Previous methods of dealing with this problem have imposed extra restrictions on the solution [2,4] or have considered "good" exponential algorithms to solve the problem [

Advances in the Minimum Overlap Problem

✍ Jan Kristian Haugland 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 214 KB