Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Let A be a finite alphabet, and H be a finite dictionary of words formed from the letters of this alphabet. In a conventional keyboard typically each key of the keyboard is assigned a unique symbol chosen from the alphabet. We consider the problem of assigning more than one symbol of the alphabet A to the same key on the keyboard. Let Ci be a subset of A. Every time a character in Ci is to be represented, the keyboard represents it using the digit (i.e. the index) 'i'. In a keyboard of this form, since multiple symbols of the alphabet A have the same representation, the representations of all the (distinct) words in the dictionary H need not be unique. A useful measure of the effectiveness of a particular keyboard is the number of words of H which are mapped to the same encoded form (i.e. they collide). This metric will be termed the ambiguity associated with the keyboard. The problem we study is one of optimally assigning the symbols of the alphabet to the keys of a given keyboard with a view to minimize the resulting ambiguity. The problem as stated above is proven to be NP-hard. This naturally leads us to seek fast and approximate solutions to the optimization problem on hand. After presenting the only reported solution to the problem, we report a fast learning automaton-based solution to this problem. Experimental results demonstrating the power of this solution have also been presented.

REFERENCES

• 1: Brucker, P, "On the Complexity Of Clustering Problems", in R.Henn, B.Korte and W. Olettii (eds.), Optimierung und Operations Research, Lecture Notes in Economics and Mathematical Systems, Berlin, 1978.
• 2: De Jong, K., "Adaptive System Design: A Genetic Approach", IEEE Transactions on Systems, Man, and Cybernetics~ 1980, pp. 566-574.
• 3: Dewey, G., Relative Frequency of English Speech Sounds, Cambridge, MA, Harvard Univ. Press, 1923.
• 4: Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980 [doi>10.1145/356827.356830]
• 5: S. Lakshmivarahan, Learning Algorithms Theory and Applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1981
• 6: Levine, S. H., "An Adaptive Approach to Optimal Keyboard Design for Nonvocal Communication", Proc. of the International Conference of Cybernetics and Society, 1985, pp. 334-337.
• 7: Levine, S. H., Minneman, S.L., Getschow, C.O., and Goodenough- Trepagnier, C., "Computer Disambiguation of Multi-Character Text Entry ' An Adaptive Design Approach", Proc. of the IEEE International Conference on Systems, Man and Cybernetics, 1986, pp. 298-301.
• 8: Kumpati S. Narendra , Mandayam A. L. Thathachar, Learning automata: an introduction, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 9: B. J. Oommen , D. C. Y. Ma, Deterministic Learning Automata Solutions to the Equipartitioning Problem, IEEE Transactions on Computers, v.37 n.1, p.2-13, January 1988 [doi>10.1109/12.75146]
• 10: Oommen, B.J., R.S. Valiveti, and Zgierski, J., "An Adaptive Learning Solution to the KeyBoard Optimization Problem".Submitted for Publication.
• 11: Sankoff, D., and Kruskal, J.B., Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, Addison Wesley, 1983.
• 12: Sargur N. Srihari, Computer Text Recognition and Error Correction, IEEE Computer Society Press, Los Alamitos, CA, 1985
• 13: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 14: C. K. Wong , Ashok K. Chandra, Bounds for the String Editing Problem, Journal of the ACM (JACM), v.23 n.1, p.13-16, Jan. 1976 [doi>10.1145/321921.321923]
• 15: Zgierski, J., Application of Learning Automata to Various Optimization Problems, Honours Project, School of Computer Science, Carleton University, Ottawa.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)
  I.7 DOCUMENT AND TEXT PROCESSING

General Terms:
Algorithms, Design, Experimentation