US007027975B1
`
`(12)
`
`United States Patent
`Pazandak et a].
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,027,975 B1
`Apr. 11, 2006
`
`(54) GUIDED NATURAL LANGUAGE
`INTERFACE SYSTEM AND METHOD
`
`('75) Inventors: Paul N_ Pazandak, Bloomingtona MN
`(52); Craig ThOmPSOII, Plano’ TX
`(
`)
`(73) Assignee: Object Services and Consulting, Inc.,
`West Grove, PA (U S)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(1)) by 857 days.
`
`(21) Appl. No.: 09/634,108
`
`(22) Filed:
`
`Aug. 8, 2000
`
`(51) IIlt- Cl-
`(2006-01)
`G10F 17/27
`(52) US. Cl. ........................................................ .. 704/9
`(58) Field of Classi?cation Search .................. .. 704/9,
`704/257, 270,1; 707/3
`See application ?le for complete Search history,
`
`(56)
`
`References Cited
`
`Us‘ PATENT DOCUMENTS
`4,688,l95 A *
`8/1987 Thompson et a1. ......... .. 706/11
`4,829,423 A
`5/1989 Tennant et a1.
`- 364/200
`5,083,268 A
`1/1992 Hemphill et a1~
`395/12
`5,745,550 A *
`4/1998 Eisdorfer et a1. ........... .. 379/52
`6,012,067 A
`1/2000 Sarkar
`6,021,418 A
`2/2000 Brandt et :11.
`6,055,538 A
`4/2000 Kessenich et a1.
`
`5/2000 Park et a1.
`6,064,951 A
`7/2000 Skinner et 31.
`6,085,198 A
`6,321,235 B1* 11/2001 Bird ......................... .. 707/203
`6,615,172 B1* 9/2003 Bennett et a1. ........... .. 704/257
`FOREIGN PATENT DOCUMENTS
`0924628 A2 * 6/1999
`............... .. 707/101
`EP
`-
`* -t d b
`C1 e y exammer
`Primary ExamineriRichemond Dorvil
`Assismnz ExamineriDonald L, Storm
`(74) Azzorney, Agenz, 0r FirmiThe LaW Firm of H. Dale
`Langley, Jr., PC
`
`(57)
`
`ABSTRACT
`
`A method for a guided natural language interface includes
`inputting to a thin client a query, communicating to an
`interface intermediary, communicating to an interface
`descriptor data source, generating an interface descriptor,
`Communicating the interface descriptor to the interface
`intermediary, communicating the interface descriptor to a
`parser farm, requesting an appropriate parser corresponding
`to the interface descriptor, assigning an appropriate parser,
`parsing, communicating a translation from the step of pars
`ing, to the interface intermediary, and communicating the
`translation to the thin client. The thin client can be geo
`graphically remote from any or all of the steps other than the
`step of inputting, such that the method is performed over a
`disparate enterprise, such as a network, for example, the
`Internet
`
`33 Claims, 18 Drawing Sheets
`
`500
`\
`
`END-USER
`
`]_ _________ __ ___ _____ "5,502
`
`1
`
`TH/N CLIENT
`INPUT/OUTPUT DISPLAY
`HOST
`APPLICATION
`
`|
`
`i
`:
`i
`:
`1
`:
`
`304
`
`INTERFACE
`DESCRIPTOR
`DATA SOURCE
`
`_________ __
`
`6 314
`
`k
`
`COMMAND
`INTERMED/ARY
`1
`
`1
`
`RESULT
`TRANSLATION
`TARGET
`APPLICATION
`
`_____ _1
`
`A
`i CLIENT
`i 302
`1
`i
`;
`1
`l________. ___________________ __|
`LL I/F CODE
`,
`NEXT ITEMA/EXPEHTA ——|
`USER 3 SELECT/0N
`6372
`INTERFACE
`B
`\ t INTERMEDIARY
`INTERFACE
`DESCH/PTOH 306
`E
`{
`i
`1
`1
`1
`
`TRANSLATIONI 504
`1
`1
`*1 T370:
`1
`I
`E
`
`1
`
`3
`
`l
`
`|
`I
`
`PARsER FARM
`342125 _____ __SEBEEE __________
`
`|
`
`I
`|
`
`Page 1 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 1 0f 18
`
`US 7,027,975 B1
`
`100 \
`
`106
`
`102\
`
`CLIENT
`
`SERVER
`
`FIG. 1
`
`Page 2 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 2 0f 18
`
`US 7,027,975 B1
`
`202\
`
`204\
`
`206\
`
`I,
`INPUTING TO
`CLIENT
`I
`REOUES TING
`APPROPRIATE
`PARSER
`I,
`ASSlGN/NG
`APPROPRIATE
`PARSER
`
`208\
`
`v
`PARS/N6 QUERY
`210\
`‘L
`RETURNING PARSED
`TRANSLATION
`
`FIG. 2
`
`Page 3 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 3 0f 18
`
`US 7,027,975 B1
`
`Zbmmm
`
`H N (a,
`
`:1
`
`AI.
`
`EQREWEQE
`
`mu EQHES
`
`Kg,
`
`mowmm??
`
`mEmEuwmQ
`
`FEM
`
`
`
`“.5 E52:
`
`QQEEQEQ
`momma, ?g
`
`2M1
`
`mmwmqm
`
`
`
`EmE mmmmqm M ism
`
`m 5E
`
`Page 4 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 4 0f 18
`
`US 7,027,975 B1
`
`400 \
`402\
`
`l
`
`INPUTTING TO
`TH/N CLIENT
`
`40“
`
`l
`
`INTERMEOIARY
`l
`
`406
`\
`
`COMMUNICATING TO
`INTEREA CE OEsCRIPTOR
`OATA SOURCE
`
`408
`
`4 10
`\
`
`l
`GENERATING AN INTERFACE
`OEsCRIPTOR
`l
`COMMUNICATING TO
`INTEREA CE INTERMEOIARY
`47%
`l
`COMMUNICATING T0
`PARsER FARM
`l
`414\
`IDENTIFYING, LOCATING
`OR CREATING PARsER
`
`<,_
`
`L
`426
`i
`;
`OUTPUTTING BY
`:
`=- ---- J-AA-AAA ---- --=
`
`_ _ _ _ _ _ _ _ _ _ _ L _ ._ _ ._ _ _ ._ __
`
`I
`
`l
`_________ "L ______ n 1424
`l
`COMMUNICATING TO
`:
`: COMMANO INTERMEOIARY I
`--------- "E -------- -
`;
`I
`PROCESSING TARGET
`APPLICATION
`420
`T
`F
`DELIVERING TRANsLATION
`TO COMMANO
`INTERMEOIARY
`
`422
`/
`
`COMMUNICATING TO
`INTEREA CE
`INTERMEDIARY
`T
`
`PARS/N6
`
`/' 4 18
`
`/
`416
`
`FIG. 4
`
`Page 5 of 44
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 5 of 18
`
`US 7,027,975 B1
`
`vle
`
`LNAINO/LNANI|INGITONIHL!r420E|INIT)|V
`AYTdSIG
`
`d5SN-GNF
`
`
`
`NOLLOFIAISSAISN
`
`t
`
`__4009ANTi
`
`
`
`VLYFIdXF/VNILILIXINroe
`
`
`LFOYY!LINSId5NOLL908GO01dl49SI7ISNVYL
`
`AUVIGINVYFINIjaviGanaiOno
`
`
`!JOVIYIINI
`
`
`
`ONYAWWODJOVIYIINIJOVIUIMI
`
`
`
`NOVOIdd¥
`
`G‘Old
`
`
`
` roSYAUTSBOEI|||I|{|
`
`Page 6 of 44
`
`Page 6 of 44
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 6 of 18
`
`US 7,027,975 B1
`
`PBRUaAdieona ishaasisomeoeBekah
`
`ete
`
`FIG. 6
`
`Page 7 of 44
`
`Page 7 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 7 0f 18
`
`US 7,027,975 B1
`
`33%|: scape
`
`List the American Davoco Employees next 6320'
`
`FIG. 7
`
`Page 8 of 44
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 11,2006
`Apr. 11, 2006
`
`Sheet 8 0f 18
`Sheet 8 of 18
`
`US 7,027,975 B1
`US 7,027,975 B1
`
`
`
`
`
`
`
`
`
`Page 9 of 44
`
`Page 9 of 44
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 11,2006
`Apr. 11, 2006
`
`Sheet 9 0f 18
`Sheet 9 of 18
`
`US 7,027,975 B1
`US 7,027,975 B1
`
`
`
`st snes ae,
`
`FIG. 9
`
`Page 10 of 44
`
`Page 10 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 10 0f 18
`
`US 7,027,975 B1
`
`List the Kuwait: residents whose mzmel
`
`FIG. 10
`
`Page 11 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 11 0f 18
`
`US 7,027,975 B1
`
`a ,
`
`LL presence on a web page ‘ some manifestations - Ne
`
`r i 1
`
`1
`!
`
`
`
`.be'ach'erg ‘courses’
`
`FIG. 11
`
`Page 12 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 12 0f 18
`
`US 7,027,975 B1
`
`Portable
`Speci?cation
`Editor
`
`Imports
`metadata
`
`:J<1_b__a out a
`datasource
`
`ODBC
`DataSource
`
`Generates /
`Edits
`
`Portable
`Specification
`IF‘iles
`
`FIG. 12
`
`Page 13 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 13 0f 18
`
`US 7,027,975 B1
`
`Q 5 Portable Saeci?calion
`E Relations
`E Joins
`
`FIG. 13
`
`Page 14 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 14 0f 18
`
`US 7,027,975 B1
`
`: é’sPmabl
`
`ifii
`
`d1.
`
`? 12 Example Speti?catio
`@ [m Relations
`
`‘
`
`m name
`
`0
`
`'
`
`-
`
`4:
`
`em
`
`'
`
`m address
`
`E residence
`E type
`0- E aiofczmoni
`Q @ Julns
`@ ENVIRO_CONFEREN - _
`@ KUwNLREslDENT-Lg '
`@ AMERICAN__DAV0C0
`
`v,
`
`\
`
`'
`
`3} longitude
`
`A
`
`I
`
`‘
`
`%
`
`Page 15 of 44
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 11,2006
`Apr. 11, 2006
`
`Sheet 15 0f 18
`Sheet 15 of 18
`
`US 7,027,975 B1
`US 7,027,975 B1
`
`S .
`
`
`
`
`
`FIG. 15
`
`Page 16 of 44
`
`Page 16 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 16 0f 18
`
`US 7,027,975 B1
`
`'.- commands
`
`‘Lisa
`
`éfri
`
`.Davqim. Mia},
`
`$581531" W98 2 iiainé, 1;‘ g
`
`I 'oce-Expe ‘V -
`
`'3
`
`MARKETING
`PUMPING
`REFINING
`
`g
`
`'
`
`‘
`
`.
`
`1315531." the
`“mm fénprek
`
`n
`
`g e. "
`
`I
`
`FIG. 16
`
`Page 17 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 17 0f 18
`
`US 7,027,975 B1
`
`@NLI Query Translation l?
`
`,EW
`..WI 6
`MR NE
`SELECT DISTINCT* FROM AMERICAN 0.00000 Emov
`EN A E L
`EEARTMEN?
`AMERICAN_DAVOCO EMPLOYEED
`.C
`
`
`,E
`
`i f???“
`
`All!“
`
`1
`
`I
`
`191: 000’ Iii?!“
`
`AM
`
`,
`
`by
`
`FIG. 17
`
`Page 18 of 44
`
`

`

`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 18 0f 18
`
`US 7,027,975 B1
`
`Adam
`C
`Pamela
`Daniels
`Darwell Matthew
`Downs Barbara
`H
`Bonnie
`H
`William
`milton
`David
`M
`Alexis
`M
`Peterson James
`Simo Denise
`S
`John
`
`Continental
`Continental
`Continental
`Continental
`Continental
`Continental
`Continental
`Continental
`Continental
`Continental
`Continental
`Continental
`
`25273000
`25273000
`25273000
`25273000
`25273000
`25273000
`25273000
`25273000
`25273000
`25273000
`25273000
`25273000
`
`Bneid at Qar F’.O. 80111083 Safat
`Bneid al Qar P.O. Box1003 Safat
`Bneid al Qar P10. Box1083 Safat
`Bneid al Qar PtO. 90111083 Safat
`Bneicl el Qar FRO‘ 80111083 Safat
`Bneid al Qar P.O. B0x1003 Safat
`Elneid al Qar P.O. 80111083 Safat
`Bneid al Qar P10. 50111083 Safat
`Elneid at Qar P00. Box1083 Safat
`Bneld al Qar P.O. Box1083 Safat
`Etneinl at Qar P00. 801M083 Safal
`Elneicl at Qar P,O. Box1083 Safat
`
`FIG. 18
`
`Page 19 of 44
`
`

`

`US 7,027,975 B1
`
`1
`GUIDED NATURAL LANGUAGE
`INTERFACE SYSTEM AND METHOD
`
`BACKGROUND OF THE INVENTION
`
`The present invention generally relates to computers and
`computing and, more particularly, to natural language inter
`faces (NLI) for user interfacing With computing devices to
`interact With computer applications, for example, database
`programs, on such devices or interconnected devices, by
`inputting stated questions or commands in natural language,
`such as English language and grammar, to Which the devices
`and applications respond.
`Computational linguistics and natural language process
`ing are rather specialiZed computing disciplines that relate to
`the computer user and his ability and mode of communica
`tion With computing devices. In the sub-area of natural
`language processing, more speci?c areas of research and
`development include information retrieval from text (for
`example, using keyWords as in conventional search engines,
`such as GoogleTM); question ansWering from databases,
`knoWledgebases, or text (for example, linguistically moti
`vated techniques using grammars and lexicons but also
`pattem-based techniques); natural language generation;
`natural language translation; text-to-speech; speaker recog
`nition; ontologies (such as, for example, WordnetTM), and
`conversational analysis. A natural language interface (NLI),
`as the name implies, is a particular mode or method of user
`interaction With a computing device or devices in Which the
`user employs natural language, such as the English language
`and grammar, to communicate inputs, for example, queries
`and commands, to the devices and applications of the
`devices. NLIs can often be desired modes for communicat
`ing With computing devices, softWare applications, and
`related hardWare and softWare components, depending on
`the particular application or discipline for the devices and in
`the case of experienced as Well as less-sophisticated users.
`Certain types of natural language interfaces are conven
`tional. In the conventional NLIs, the user types or speaks
`unconstrained commands (including queries) With the
`expectation that the system Will understand the speech acts
`and take the desired action (e.g., return an ansWer). As can
`be understood, there are limitations to the capabilities of the
`conventional NLIs. For example, computing poWer and
`features have not previously been adequate to encompass all
`possible variations and uses of language and grammar.
`Moreover, the tremendously large numbers and variables of
`Words, contexts, and meanings With any natural language are
`nearly impossible to accurately process under all applicable
`language rules and variations.
`Because of the limitations of computing and NLIs in the
`past, computing users Who interface using NLIs have typi
`cally not fully understood the limited scope and capabilities,
`or “coverage”, of the particular NLIs (such as, in terms of
`the subset of natural language a system understands, typi
`cally delimited by lexical, semantic, grammatical, and
`domain coverage boundaries). Consequently, NLI com
`mands and language are often not fully or properly inter
`preted or understood by the NLI or computing system
`having such interface, and the user likely Will not have
`sufficient command of the natural language subset and
`limitations of the NLI and extensive training or learning can
`be required in order to make appropriate and desired use of
`capabilities of the NLI and related system. The NLIs have
`not necessarily made interfacing more inherently under
`standable or easier to the user. In other Words, the typical
`user of natural language commands and NLIs for interfacing
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`With computing devices can risk overshooting or under
`shooting the underlying application system’s capabilities,
`because of the limitations of those capabilities With the
`present states of computing capacity and technologies and
`because of the limits of the user’s knoWledge and under
`standing.
`In addition to the implications to computing users Who
`interface via NLIs, computer and softWare developers of
`NLIs for applications have the overWhelming and virtually
`impossible task of de?ning a large number of all possible
`Words, grammar rules, and domain translations necessary in
`efforts to increase NLI coverage. Because of the magnitude
`of the efforts in such development, NLI creation is an
`expensive process, even to retarget from one database to
`another. All conventional NLIs have limited and mismatch
`of coverage problems. In the past, this has often caused users
`Who experience the coverage problems to groW frustrated,
`and fail to make full use or entirely discontinue use of
`conventional NLIs.
`Previously, NLIs have generally been delivered With a set
`of limited form or “canned” example queries. Users of the
`NLIs have been encouraged to use these examples or only
`slight variations thereof to obtain satisfactory results. None
`theless, these example queries, even if only slightly varied,
`often tend to interfacing failures or unexpected or incorrect
`results. Several conventional NLI products include:
`Microsoft Easy QueryTM, ELFTM, and iPhraseTM. No doubt,
`there are other conventional NLIs and other NLI products.
`All such knoWn NLI technologies have been limited, hoW
`ever, in acceptability to feW useful applications and to very
`narroW and simple applications in any event, and none have
`become pervasively used or available in the industry. This is
`the result of the problems of the conventional NLIs.
`Of particular note in the early l980’s, Texas Instruments
`developed the so-called “NLMenu” system, a natural lan
`guage interface technology that sought to address certain of
`the foregoing problems of NLIs. NLMenu employed sub
`stantially the same grammar, lexicon, and parsing found in
`all other NLI systems at the time and even those conven
`tional to date. One nuance at the time of the NLMenu system
`Was that the typical parser Was modi?ed in the system to
`parse a partial sentence and, then, predictively ?nd all next
`legal completions (i.e., the acceptable next Words or phrases
`under the NLMenu interface lexicon and grammar) and
`display these legal completions in a constellation menu (i.e.,
`a menu displayed to the user that lists all next lexical choices
`organiZed by grammatical category). The user Was then able
`to select from the constellation menu a next Word or phrase
`in the menu, Which Word or phrase Was an appropriate legal
`completion of the particular natural language input sentence,
`query, command or other sequence. The NLMenu system is
`described in Us. Pat. No. 4,829,423, and certain additional
`aspects are described in Us. Pat. Nos. 4,688,195 and
`5,083,268.
`As With the other conventional NLIs, the NLMenu system
`presented many of the problems previously described.
`Moreover, the NLMenu system is quite limited in that it is
`a single-user system in Which constellation menus are dis
`played on the user’s computing device and interact With a
`single, complex full-featured parser. The constellation
`menus shoW a single screen-shot of the user’s display of the
`entire lexicon useable by the user to interface in the natural
`language, but this is a disadvantage because the menus
`occupy considerable screen area of the user’s display and
`often obscure other entities or features displayed on the
`screen that can be the subject of the user’s efforts in lodging
`a natural language query. SWitching among and moving
`
`Page 20 of 44
`
`

`

`US 7,027,975 B1
`
`3
`features around on the screen of the display can be incon-
`venient for the user. Furthermore, the parser of the NLMenu
`system is full-featured and so useful for various situations,
`but in many instances the parser is excessive in features and
`cumbersome(i.e., overkill) where alternative and simpler
`kinds of parsers are more useful andpractical. In general, the
`NLMenu system has been useable for certain applications,
`but not others. Particularly, the system is not particularly
`effective for use in present computing environments,
`in
`which scalability, multi-user capability, wide area and
`remote geographic networking, and reducedor “thin client”
`hardware and software is desired.
`
`The present invention overcomes these and other prob-
`lems ofthe prior technology.
`
`SUMMARY OF THE INVENTION
`
`Embodiments of the present invention include systems
`and methods for light-weight guided NLI client interfaces
`and supporting parser farms on servers, available concur-
`rently and in real time to a plurality of users, over disperse
`and geographically disparate networks, such as the Internet.
`An embodiment is a system for a natural languageinter-
`face. The system includes a client device, a server device,
`and a communications network interconnecting the client
`device and the server device.
`
`Another embodiment is a system for a natural language
`interface. The system includes a thin client, a parser farm, a
`parser, a first communications network for communicatively
`connecting the thin client and the parser farm, and a second
`communications network for communicatively connecting
`another element selected from the group consisting of the
`parser farm andthe parser.
`Yet another embodiment is a system for a natural lan-
`guage interface. The system includesa thin client, an inter-
`face intermediary, a first communications network connect-
`ing the thin client and the interface intermediary, an interface
`descriptor data source, a second communications network
`connecting the interface descriptor data source and the
`interface intermediary, a command intermediary, a third
`communications network connecting the commandinterme-
`diary and the interface intermediary, a parser farm, a fourth
`communications network connecting the parser farm and the
`interface intermediary, a parser, a fifth communications
`network communicatively connecting the parser to the
`parser farm, and a sixth communications network for com-
`municatively connecting the parser and the interface inter-
`mediary.
`Another embodiment of the system is a method of a
`natural language interface. The methodincludes inputting to
`a thin client a query, requesting an appropriate parser for the
`query, assigning an appropriate parser, parsing the query,
`and returning a parsed translation.
`Yet another embodiment is a method of parsing. The
`method includes inputting a query at a first location and
`parsing the query at a secondlocation.
`Another embodimentis a method of a natural language
`interface. The method includes inputting to a thin client a
`query, communicating to an interface intermediary, commu-
`nicating to an interface descriptor data source, generating an
`interface descriptor, communicating the interface descriptor
`to the interface intermediary, communicating the interface
`descriptor to a parser farm, requesting an appropriate parser
`corresponding to the interface descriptor, assigning an
`appropriate parser, parsing, communicating a translation
`from the step of parsing, to the interface intermediary, and
`communicating the translation to the thin client.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention may be better understood, andits
`numerous objects, features, and advantages made apparent
`to those skilled in the art by referencing the accompanying
`drawings.
`FIG.1 illustrates embodiments of a client-server system,
`including a client device and a server device, communica-
`tively connected by a network, such as the Internet, for
`serving as a natural language interface system.
`FIG.2 illustrates embodiments of a method of operation
`of the client-server system of FIG. 1, providing a multi-user,
`multi-device, geographically disparate communications sys-
`tem having a natural language interface.
`FIG.3 illustrates embodiments of a system for a natural
`language interface over a network of multiple and geo-
`graphically disparate users and devices, such as the Internet.
`FIG.4 illustrates embodiments of a method of a natural
`
`language interface over a network of multiple and geo-
`graphically disparate users and devices, such as the Internet.
`FIG. 5 illustrates embodiments of a natural
`language
`interface system, as found in one such exemplary system
`referred to as the LingoLogic (LL) system.
`FIG. 6 illustrates embodiments of a distinctive avatar
`employed to initiate a query or command of the natural
`language interface system of FIG.5.
`FIG.7 illustrates embodiments of a sequence of web-links
`and a popup menu usedto specify a query or command of
`the natural language interface system of FIG.5.
`FIG.8 illustrates embodiments of a cascading menu used
`to specify a query or command of the natural
`language
`interface system of FIG.5.
`FIG.9 illustrates embodiments of phrase buttons used to
`specify a query or commandof the natural languageinter-
`face system of FIG.5.
`FIG.10 illustrates embodiments of a type-in display used
`to specify a query or command of the natural
`language
`interface system of FIG.5.
`FIG. 11 illustrates embodiments of a drop down menu
`used to specify a query or commandofthe natural language
`interface system of FIG.5.
`FIG.12 illustrates embodiments of inputs and outputs of
`a Portable Specification Editor.
`FIG.13 illustrates embodiments of methods of importing
`an ODBCdatabase schema into the Portable Specification
`Editor.
`FIG. 14 illustrates embodiments of a screen-shot of the
`
`Portable Specification Editor, illustrating how an interface
`designer can create a portable specification from a database
`schema that can then be used to auto-generate a guided
`natural language interface.
`FIG. 15 illustrates embodiments of a simple expert used
`to specify a value in a query or command of a natural
`language interface system.
`FIG. 16 illustrates embodiments of a data source expert
`used to specify a value in a query or commandof a natural
`language interface system, wherein the value is shown
`during and after invocation of the expert.
`FIG. 17 illustrates embodiments of a translation of a
`sample query into SQL, in accordance with a natural lan-
`guage interface system, such as the LingoLogic system.
`FIG. 18 illustrates embodiments of execution results of a
`
`sample query in a tabular format for a natural language
`interface system, such as the LingoLogic system.
`The use of the same reference symbols in different draw-
`ings indicates similar or identical items.
`
`Page 21 of 44
`
`Page 21 of 44
`
`

`

`US 7,027,975 B1
`
`5
`DETAILED DESCRIPTION
`
`In computing, communications and processing devices,
`embodiments provide guided interfaces to such devices and
`their applications, which guided interfaces are operable as
`distributed parts of a guided language processor to client
`devices and server devices, such as in a computer or
`communications network. Particularly, completion-based
`interfaces, such as grammar-driven menu-based restricted
`language interfaces (or so-called “natural language inter-
`faces” (NLI)), and also other interfaces such as guided
`navigation of categories, path expressions, and languages
`other than natural languages, as well as speech interfaces to
`such guided interfaces, are operable distributed amongclient
`and server elements. This distribution enables predictive
`parsing, as well as translation and execution, concurrently
`and in real time, supporting pluralities of users to simulta-
`neously specify pluralities of queries or commandsinter-
`faced to pluralities of devices and applications, including
`over a networkorother distributed computing environment.
`The embodiments are operable, for example, on the Internet
`and World Wide Web network. Additionally, embodiments
`are operable in local area networks and even on a single
`computer or device.
`Referring to FIG. 1, a system 100 for a communicative
`network includes a server element 102 and a client element
`
`104. The client element 104 is communicatively connected
`to the server element 102 by a communicative connector
`106. The server element 102 is any of a wide variety of
`processing or communications devices,
`such as,
`for
`example, a computer, a processor, a circuit, memory or other
`element within a processor or processing device, or any
`device including any such matter, which server element 102
`is capable of functioning to receive a communicated request
`and appropriately respond. The client element 104 is also
`any of a wide variety of processing or communications
`devices, such as, for example, those previously mentioned,
`which client element 104 is capable of sending or causing
`the sending of a request and receiving a communicated
`response. The communicative connector 106 is any of a
`wide variety of communication channels and elements there-
`for, including, for example, a wire, a circuit, a bus, a cable,
`a wired or wireless communications network, or any other
`device or componentthat allows for communications, elec-
`trical or otherwise, between elements functioning to com-
`municate in a client-server manner. For purposes hereof, a
`client-server system or functionis to be broadly construed to
`include any and all communicative arrangements in which
`elements,
`devices,
`or
`components
`intercommunicate,
`directly or through intermediary systems, by generation of a
`request, receipt of the request, generation of a response, and
`occurrence of the response. The client-server system and
`function, as so construed, includes client-server operations
`over a network, such as the Internet or World Wide Web,
`another wide area network, a local area network, and even
`within a device among elements, components, or peripherals
`of the device, such as within a single computer or other
`processing device.
`In operation, the system 100 operates, at least in part, in
`a client-server manner, such that the client element 104
`delivers a request over the communicative connector 106 to
`the server element 102. The server element 102 receives the
`
`request and directly or indirectly processes it. The server
`element 102 then appropriately responds to the request, for
`example, by communicating a response signal back to the
`client element 104 over the communicative connector 106.
`
`6
`Although the communicative connector 106 is illustrated in
`FIG. 1 as a simple line connection between the client
`element 104 and the server element 102, it is to be under-
`stood that the communicative connector 106 can be any of
`a wide variety of communicating intermediate devices,
`connections, and elements of a network or system that are
`communicatively connected to enable inter-communications
`in the client-server mannerjust described. For example, the
`communicative connector 104 in certain embodimentsis the
`Internet and each of the client element 104 and the server
`
`element 102 is a separate, disparate processing device con-
`nected to the Internet. Of course, as has been more fully
`described,all other network or interconnection of devices or
`components is possible and included within the scope of the
`embodiments.
`Referring to FIG. 2, a method 200 operable on the system
`100 of FIG. 1 includes a step 202 of inputting a query or
`commandto a client. In the step 202, for example, a human
`user inputs, via input components such as a keyboard to a
`computing device as the client, a database or other applica-
`tion query in a natural language, such as English grammar
`and lexicon, through a natural language interface (NLI). In
`a step 204, a request is made, such asvia the client to another
`device, for example, a server, for an appropriate parser for
`parsing the particular NLI input of the step 202.
`for
`if,
`Referring to FIGS. 1 and 2,
`in conjunction,
`example, the method 200 operates on a system 100 that
`includes the Internet as the communicative connector 106
`between a client element 104 and the server element 102, the
`step 202 of inputting is performedat the client element 104
`and the step 204 of requesting an appropriate parser is
`communicated over the communicative connector 106 to the
`server element 102. The server element 102 can maintain or
`
`make accessible a selection of parser from among one or
`moreparsers of a so-called “parser farm’. In this manner, an
`appropriate parser for the particular input from the client
`element 104 is useable, and the parser need not (although it
`maybe) available in or at the client element 104itself. In the
`trade, the term “thin client” is sometimes used to refer to a
`client in a client-server system which does not itself have
`substantial processing or operative capability within the
`client, and such thin client relies on other units, such as a
`server, for processing and operative capabilities available on
`the client’s request. The method 200 is particularly appli-
`cable to such thin client environments, as those skilled in the
`art will understand and appreciate.
`Continuing to refer to FIG. 2, a step 206 of the method
`200 assigns the appropriate parser for parsing the input of
`the step 202. The appropriate parser, in any instance, will
`depend on several variables,
`including, for example, the
`numbers and types of parsers available for the application
`and the particular system 100 and method 200 capabilities
`and operations. Selection of parsers among several choices
`is subject to many possibilities. On selection of the parser in
`the step 206, the parser in a step 208 performsa parse of the
`query or command input in the step 202. The step 208 is
`repeated until a well formed grammar constituent is speci-
`fied. Once the parse in the step 208 is completed, a step 210
`returns a translation from the parser of the parsed query or
`command.
`Referring to FIGS. 1 and 2, in conjunction, in a possible
`example in which the method 200 operates on a system 100
`that includes the Internet as the communicative connector
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`the appropriate parser
`106 as previously mentioned,
`requested and chosen in the step 204 is resident on or
`available via the server element 102. The client element 104
`
`in such example is, therefore, a thin client in that significant
`Page 22 of 44
`
`Page 22 of 44
`
`

`

`US 7,027,975 B1
`
`7
`processing operations, at least with respect to the guided
`language query operations of the method 200, occur on or
`through the server element 102, not the client element 104.
`Architecture
`
`Referring to FIG. 3, an implementation 300 of the system
`100 of FIG. 1 includes a thin client 302, for input by and
`output display to a user, such as a human computeroperator.
`The thin client 302 can be, for example, a personal desktop
`computer, a notebook computer, a network computer, a
`personal digital assistant, a network-enabled telephone, a
`dumb terminal, a smart phone, a set top box, a Palm™
`device, a toy controller, a remote control and any other
`device having functions of input and request communica-
`tion. The user of the thin client 302 is most likely a human
`user, however, it can alternatively be a software or hardware
`agent which interacts with the thin client 302 to input and
`receive responses.
`Maintainedon the thin client 302 can be a host application
`(not shown), such as a software program, embedded pro-
`gram, or hardware functional unit, which initiates a com-
`municative interaction by the thin client 302 with other
`elements of the implementation 300. Examples of host
`applications are a web browser, Microsoft Word™, or a
`specialized or other stand-alone application.
`In addition,
`the thin client 302 can include a target
`application (not shown) that receives a translation (as here-
`after described) of a query or command correspondingto the
`input to the thin client 302 and returns results (as hereafter
`described),
`including status messages,
`for example,
`for
`display on the thin client 302. The target application can be
`includedin or the sameas, or different or distinct from, the
`host application of the thin client 302. Several exemplary
`types of target applications include database management
`system (DBMS) systems, word processors, game programs,
`robots with sensors and feedback,
`toys, video cassette
`recorders (VCRs), military equipment, and other machines
`and devices with software interfaces.
`
`The thin client 302 can include various elements, includ-
`ing, for example, an input/output display that the user can
`use to construct queries and commandsand viewresults.
`The thin client 302 can be any of a variety of presently
`availabl