Text mining applies the same analytical functions of data mining to the domain of textual information, relying on sophisticated text analysis techniques that distill information from free-text documents.IBM's Intelligent Miner for Text provides the necessary tools to unlock the business information that is "trapped" in email, insurance claims, news feeds, or other document repositories.It has been successfully applied in analyzing patent portfolios, customer complaint letters, and even competitors' Web pages.After defining our notion of "text mining", we focus on the differences between text and data mining and describe in some more detail the unique technologies that are key to successful text mining.

We investigate the problem of determining a compact underspecified semantical representation for sentences that may be highly ambiguous. Due to combinatorial explosion, the naive method of building semantics for the different syntactic readings independently is prohibitive. We present a method that takes as input a syntactic parse forest with associated constraint-based semantic construction rules and directly builds a packed semantic structure. The algorithm is fully implemented and runs in O(n4log(n)) in sentence length, if the grammar meets some reasonable 'normality' restrictions.

We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call semidirectional. In semidirectional Lambek calculus SDL there is an additional nondirectional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequent's left-hand side, thus permitting non-peripheral extraction. SDL grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidirectional Lambek Grammar is NP-complete by a reduction of the 3-Partition problem.

Some linguistic constraints cannot be effectively resolved during parsing at the location in which they are most naturally introduced.This paper shows how constraints can be propagated in a memoizing parser (such as a chart parser) in much the same way that variable bindings are, providing a general treatment of constraint coroutining in memoization.Prolog code for a simple application of our technique to Bouma and van Noord's (1994) categorial grammar analysis of Dutch is provided.

In the general framework of a constraint-based grammar formalism often some sort of feature logic serves as the constraint language to describe linguistic objects.We investigate the extension of basic feature logic with subsumption (or matching) constraints, based on a weak notion of subsumption.This mechanism of oneway information flow is generally deemed to be necessary to give linguistically satisfactory descriptions of coordination phenomena in such formalisms.We show that the problem whether a set of constraints is satisfiable in this logic is decidable in polynomial time and give a solution algorithm.

A generalization of term subsumption, or matching, to a class of mathematical structures called feature algebras is discussed. It is shown how these generalize both first-order terms and the feature structures used in computational linguistics. The notion of subsumption generalizes to a natural notion of homomorphism between elements of these algebras, and the authors characterize the notion, showing how it corresponds to a mapping which preserves partial information. In the setting of feature algebras, unification corresponds naturally to solving constraints involving equalities between strings of unary functions symbols, and semiunification also allows inequalities representing subsumption constraints. Their generalization allows the authors to show that the semiunification problem for finite feature algebras is undecidable. This implies that the corresponding problem for rational trees (cyclic terms) is also undecidable. Thus a partial solution to the decidability of this problem, which has been open for several years, is produced.>

The paper describes a new implementation of feature structures containing disjunctive values, which can be characterized by the following main points: Local representation of embedded disjunctions, avoidance of expansion to disjunctive normal form and of repeated test-unifications for checking consistence. The method is based on a modification of Kasper and Rounds' calculus of feature descriptions and its correctness therefore is easy to see. It can handle cyclic structures and has been incorporated successfully into an environment for grammar development.