Thomas G Ball

US Patent:

6529863, Mar 4, 2003

Filed:

Aug 30, 1999

Appl. No.:

09/386094

Inventors:

Thomas J. Ball - Mercer Island WA
Peter John Danielsen - Naperville IL
Lalita Jategaonkar Jagadeesan - Naperville IL
Konstantin Laufer - Chicago IL
Peter Andrew Mataga - Naperville IL
Kenneth G. Rehor - Berwyn IL

Assignee:

Lucent Technologies Inc. - Murray Hill NJ

International Classification:

G06F 1720

US Classification:

704 1, 704 9, 704270, 379 88

Abstract:

Interactive services are provided by employing a modular approach to implementing interactive services with multiple interfaces. Such an approach facilitates supporting natural language understanding interaction with users through use of interfaces that allow at least different ordering of inputs, and/or incomplete information, and/or correction of information, and/or the return of control to prior points in the service. This is realized, in an embodiment of the invention, by employing a single interactive service logic that uses âreactive constraint graphsâ, i. e. , a form of event-driven graph, in which nodes contain a set of constraints on events. Specifically, control progresses from a node to a derivative node, i. e. , âchildâ, only when all the constraints in the set on the node have been satisfied. A single set of constraints implicitly supports a significant number of the possible different orderings of inputs.

US Patent:

6609089, Aug 19, 2003

Filed:

Aug 30, 1999

Appl. No.:

09/386093

Inventors:

Thomas J. Ball - Mercer Island WA
Peter John Danielsen - Naperville IL
Lalita Jategaonkar Jagadeesan - Naperville IL
Konstantin Laufer - Chicago IL
Peter Andrew Mataga - Naperville IL
Kenneth G. Rehor - Berwyn IL

Assignee:

Lucent Technologies Inc. - Murray Hill NJ

International Classification:

G06F 1727

US Classification:

704 9, 379 67

Abstract:

Interactive services with multiple interfaces are realized by employing a modular approach to their implementation. Such an approach facilitates supporting natural language understanding interaction with users through use of interfaces that at least allow the user to provide information beyond what is currently being requested by the service, and/or different ordering of inputs, and/or incomplete information, and/or correction of information, and/or the return of control to prior points in the service. This is realized, in an embodiment of the invention, by employing an interactive service logic that uses âreactive constraint graphsâ, i. e. , a form of event-driven graph in which nodes contain constraints on events, in conjunction with a service monitor. The service monitor manages the communication between the service logic and the multiple user interfaces. As such it provides a communication mechanism in the form of a so-called âlook aheadâ in which the user can input information beyond what is currently required by the interactive service.

US Patent:

6701294, Mar 2, 2004

Filed:

Jan 19, 2000

Appl. No.:

09/487684

Inventors:

Thomas J. Ball - Mercer Island WA
Kenneth Charles Cox - Naperville IL
Rebecca Elizabeth Grinter - Naperville IL
Stacie Lynn Hibino - Naperville IL
Lalita Jategaonkar Jagadeesan - Naperville IL
David Alejandro Mantilla - New York NY

Assignee:

Lucent Technologies, Inc. - Murray Hill NJ

International Classification:

G06F 1728

US Classification:

704257, 704 9, 704270

Abstract:

A natural language-based interface data presentation system interfaces, for example, information visualization system interfaces, is realized by employing so-called open-ended natural language inquiries to the interface that translates them into database queries and a set of information to be provided to a user. More specifically, a natural language inquiry is translated to database queries by determining if any complete database queries can be formulated based on the natural language inquiry and, if so, specifying which complete database queries are to be made. In accordance with one aspect of the invention, knowledge of the information visualization presentation is advantageously employed in the interface to guide a user in response to the users natural language inquiries. In accordance with another aspect of the invention, knowledge of the database and knowledge of the information visualization presentation are advantageously employed in the interface to guide a user in response to the users natural language inquiries. In accordance with still another aspect of the invention, knowledge of the database, knowledge of the information visualization presentation and context information about the query dialogue are advantageously employed in the interface to guide a user in response to the users natural language inquiries.

US Patent:

6904590, Jun 7, 2005

Filed:

May 25, 2001

Appl. No.:

09/866090

Inventors:

Thomas J. Ball - Mercer Island WA, US
Sriram K. Rajamani - Bellevue WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F009/44

US Classification:

717132, 717128, 717133, 717144, 717156

Abstract:

Methods are discussed that enhance program analysis. One aspect of the invention includes a method for checking a model of a program. The method includes a control-flow graph having vertices from the model, applying a transfer function to each vertex to form a set of path edges, and analyzing the set of path edges of a vertex. The set of path edges includes valuations that are implicitly represented so as to inhibit an undesired explosion in the valuations that would hinder the act of analyzing.

US Patent:

7058925, Jun 6, 2006

Filed:

Apr 30, 2002

Appl. No.:

10/136881

Inventors:

Thomas J. Ball - Mercer Island WA, US
Sriram K. Rajamani - Bellevue WA, US
Todd D. Millstein - Seattle WA, US
Rupak Majumdar - Albany CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 9/44

US Classification:

717106, 717104, 717131, 717136

Abstract:

Described is a method that enables the automatic generation of a boolean program that is a predicate abstraction of a program written using a general programming language. The method is capable of abstracting code statements within the program that include procedure calls, assignments, goto statements, conditionals, and pointers. In accordance with the invention, predicates of interest are identified for each code statement in the program. For each particular code statement, the process generates predicate statements that describe an effect that the statement has on the predicates of interest. If the effect of a particular code statement is indeterminable, non-deterministic predicate statements are included in the boolean program to model the indeterminable nature of the code statement. In addition, if a particular code statement includes a procedure call, the arguments and return value of the procedure call are translated to associated predicates in the calling context.

US Patent:

7584455, Sep 1, 2009

Filed:

May 12, 2004

Appl. No.:

10/844710

Inventors:

Thomas J. Ball - Mercer Island WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 9/44

US Classification:

717124, 717126, 717127, 717131, 717134

Abstract:

Techniques and tools for achieving improved test coverage in a finite program state space are described, such as a technique for selecting a set of predicates, calculating a set of possible predicate values, calculating a subset of the set of possible predicate values, and generating a test for the computer program based at least in part on the subset. The subset comprises an approximation (e. g. , an under-approximation) of reachable states in the program. A superset of the set of possible predicate values also can be calculated; the superset comprises an over-approximation of the reachable states in the program. In another aspect, a Boolean abstraction of a program is generated, reachability analysis is performed based at least in part on the Boolean abstraction, and symbolic execution is performed to generate test data. The reachability analysis can include computing lower and/or upper bounds of reachable observable states.

US Patent:

7587707, Sep 8, 2009

Filed:

Jul 1, 2005

Appl. No.:

11/172760

Inventors:

Thomas J. Ball - Mercer Island WA, US
Shuvendu K. Lahiri - Redmond WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 9/44

US Classification:

717117, 717106, 717114

Abstract:

Predicate abstraction techniques and tools. Using symbolic decision procedures, predicate abstractions for computer programs are generated based on a set of predicates representing observations of expected behavior of the program. The set of predicates may be generated by an automatic program analysis tool or may be provided a user based on the user's observations. The predicate abstraction process may employ binary decision diagrams. Two or more symbolic decision procedures (e. g. , for different kinds of program logic) can be combined to form a combined symbolic decision procedure to be used for predicate abstraction. A data structure can be used to track derived predicates during predicate abstraction.

US Patent:

7657867, Feb 2, 2010

Filed:

Jun 17, 2005

Appl. No.:

11/155458

Inventors:

Thomas J. Ball - Mercer Island WA, US
Sriram K. Rajamani - Bellevue WA, US
Todd D. Millstein - Seattle WA, US
Rupak Majumdar - Albany CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 9/44

US Classification:

717106

Abstract:

Described is a method that enables the automatic generation of a boolean program that is a predicate abstraction of a program written using a general programming language. The method is capable of abstracting code statements within the program that include procedure calls, assignments, goto statements, conditionals, and pointers. In accordance with the invention, predicates of interest are identified for each code statement in the program. For each particular code statement, the process generates predicate statements that describe an effect that the statement has on the predicates of interest. If the effect of a particular code statement is indeterminable, non-deterministic predicate statements are included in the boolean program to model the indeterminable nature of the code statement. In addition, if a particular code statement includes a procedure call, the arguments and return value of the procedure call are translated to associated predicates in the calling context.