T 1473/05 () of 4.3.2010

Summary of Facts and Submissions

I. This is an appeal against the decision by the examining division refusing European patent application No. 03 010 491.3.

II. In examination proceedings the applicant filed claims according to inter alia a main request, claim 1 of this request reading as follows:

"A method, comprising: generating a directed acyclic word graph with words included in program guide data; receiving (410) a request to display program information; determining whether the program information is included in the program guide data by searching (412) the directed acyclic word graph generated from the program guide data; and returning (416, 418) an indication as to whether the program information is included in the program guide data."

III. The reasons for the appealed decision relating to claim 1 of the main request may be summarized as follows.

D1: WO 01/78382 A2

represented the closest prior art, disclosing a program guide having a text search function (see figures 16 and 18) in which a display image allowed the user to enter a string of characters and to see the results of the search. The indication in figure 16 consisted of displaying only those titles in the EPG (Electronic Programming Guide) data which matched the entered character, i.e. which started with the letter "A". The method of claim 1 differed from D1 by generating a directed acyclic word graph with words included in the EPG data and searching the directed acyclic word graph. The objective technical problem was seen as providing a suitable electronic search facility for searching for programming information. To solve this problem a skilled person would consider standard string search algorithms and would also consider the use of "multiway tries" as described in

D2: Sedgewick, Robert, "Algorithms in C++", September 2001, Addison-Wesley, Boston, USA, pages 646 to 663, XP-002260888.

The term "multiway tries" was synonymous with the "directed acyclic word graph" mentioned in claim 1. Hence the subject-matter of claim 1 lacked inventive step, Article 56 EPC 1973, in view of the combination of D1 and D2.

IV. With a statement of grounds of appeal the appellant (applicant) filed a set of claims according to a main request. The appellant also requested that the decision be set aside and that the board decide that the claims of said main request and the description and figures on file are allowable.

V. In the statement of grounds of appeal the appellant argued regarding the main request essentially as follows. D1 did not explicitly state how the program information was searched. Hence the subject-matter of claim 1 differed from the disclosure of D1 in generating a directed acyclic word graph with words included in program guide data and determining whether the program information was included in the program guide data by searching the directed acyclic word graph generated from the program guide data. The objective technical problem was to provide an appropriate search of the program database. Faced with the objective technical problem, a person skilled in the art would have tried to find out what kind of results should be provided by searching the program database, and based on the knowledge about the desired results he/she would have considered an appropriate search method. Studying D1 in this regard, the skilled person would have found several text passages related to searching program listings provided by the program guide with respect to certain categories, for example: page 22, lines 9 to 16, (listings organized by time, channel or genre), page 29, lines 3 to 10, (searching detailed program descriptions for a keyword) and page 29, lines 22 to 29, (searching for a keyword in program names (figure 16), actor names (figure 17) or program titles (figure 18)). Hence the skilled person would have considered using the organization of program information in different categories and thus have been guided in the direction of sorting within those predetermined different categories, rather than in the direction of using directed acyclic word graphs, since this would have led to abandoning the information gained by the organization of the program information in different categories. There was also no hint in D1 for the skilled person to search for a solution to the above problem in the remote technical field to which D2 belonged, namely the field of algorithms for programming languages. Hence the subject-matter of claim 1 involved an inventive step.

VI. The board set out its preliminary opinion on the appeal in an annex to a summons to oral proceedings, Article 15(1) RPBA (OJ EPO 2007, 536). The board expressed doubts as to the clarity of claim 19 and the conciseness of the claims, Article 84 EPC 1973. In addition, the board commented as follows, the board's comments being reproduced here verbatim.

"5. Document D1

D1 concerns an interactive television program guide able to generate listings according to time, genre, theme, channel etc. of, for instance, video-on-demand programs and regular television programs. Alternatively, a text search may be used to find programs. Figure 16 and page 28, lines 1 to 8, concern a search for a title using a user-defined term, "A[A]" in figure 16. Figure 17 and page 28, lines 24 to 27, concern a search for an actor's name using a user-defined term, "JULI[A]" in figure 17. Four titles are indicated in figure 17 which match this search criterion (i.e. the additional information searched seems to contain an actor's name showing this search criterion which is not contained in the title shown). Figure 18 and page 29, lines 3 to 12, concern a search in program descriptions for a user-defined keyword, "LO[V]" in figure 18. These searches allow direct selection of a program meeting the search criteria.

6. Document D2

Page 648, section 15.3, defines a "multiway trie", figure 15.15 showing a 26-way trie, a trie being a tree-based data structure for representing sets of character strings. As explained on page 647, lines 8 to 13, in connection with the "existence-table problem", a multiway trie can be used to determine whether a word is present in the words stored in the trie.

7. The common general knowledge

It seems to have been common general knowledge at the priority date that a multiway trie could be used to store a dictionary (for instance as a spelling checker), searching the trie revealing whether a search term belonged to the dictionary. It was also apparently known that a directed acyclic word graph (DAWG) differed from a multiway trie in that in the latter there was no elimination of suffix redundancy, i.e. no merging of identical subtrees, meaning that a DAWG required less storage space than a multiway trie.

8. Novelty, Article 54(1),(2) EPC 1973

In the statement of grounds of appeal the appellant seems to essentially agree with the finding in the appealed decision that the subject-matter of claim 1 differed from the disclosure of D1 in:

1. generating a directed acyclic word graph with words included in program guide data and

2. determining whether the program information is included in the program guide data by searching the directed acyclic word graph generated from the program guide data.

In the light of the description, the feature set out in claim 1 "returning an indication as to whether the program information is included in the program guide data" and the analogous features set out in claims 19, 34 and 47 seem to have a broad meaning including the display of matches (as an indication that the requested information is included) and the display of no matches, this being an indication that the requested information is not included. The above feature interpreted in the light of the description thus seems to be disclosed in D1. This was not contested by the appellant.

9. The objective technical problem

The appellant also stated in the grounds of appeal that the objective technical problem was to provide an appropriate search of the program database.

The board presently has doubts whether this problem can properly be regarded as the objective technical problem. Firstly, the board is reluctant to regard the objective technical problem solved by the invention as relating to the searching of the program guide data itself, since the application does not disclose in detail how the program guide data is searched, Secondly, paragraph [0041] of the published application makes clear that, once an indication has been returned of whether the requested information is available in the program guide data (by searching the one or more directed acyclic word graphs), it is optional whether the requested information is searched for in the program guide data and returned. Indeed claims 1, 19, 34 and 47 are not restricted to a subsequent search of the program guide data. Moreover, according to column 12, lines 52 to 57, a search of the program guide data is only carried out if the requested information is found in the directed acyclic word graphs. This passage also indicates that the program guide data may be searched "instead of returning the notification". Hence the problem of providing an appropriate search of the program database and the problem given in the appealed decision, namely "to provide a suitable electronic search facility for searching for programming information", do not appear to be always solved by the invention as claimed.

Furthermore, on the basis of this interpretation, the objective technical problem of providing a search result sooner, which is derivable from paragraph [0004], lines 40 to 51, of the published application would also not always be solved. For instance, in the case mentioned in column 12, lines 52 to 57, searching the directed acyclic word graphs and then the program guide data would presumably take longer than simply searching the program guide data.

However the problem of determining sooner whether matches of the requested information can be found in a subsequent search (but not necessarily immediately indicated) does seem to be solved. Hence the board tends to regard this problem as the objective technical problem in assessing inventive step.

10. Inventive step, Article 56 EPC 1973

The above problem is solved by the following features essentially set out in all four independent claims:

1. generating a directed acyclic word graph with words included in program guide data, and

2. determining whether the program information is included in the program guide data by searching the directed acyclic word graph generated from the program guide data.

The objective technical problem would have arisen in the context of a searching system such as that known from D1. The skilled person considering this problem would have looked for solutions in the field of searching and thus found D2. The board does not agree with the appellant's argument that D2 concerns a remote technical field, since there was a general trend towards convergence of electronic program guides and computers, and a computer seems to constitute one of the client devices envisaged in the present application (see paragraph [0014]). Although D2 teaches using a multiway trie, the skilled person would have modified the multiway trie to give a directed acyclic word graph to save memory space, this being a usual design consideration in the design of domestic electronic equipment.

The appellant has argued (in particular on page 6 of the statement of grounds of appeal) that organization of the program guide in different categories and sorting within those categories would be the direction indicated to a person skilled in the art in D1. The board notes that a method as specified in claim 1 (see e.g. paragraph [0017]) does not seem to exclude an organization of the program guide data into categories. Moreover the searching in D1 cannot be considered as a mere sorting of program listings; this impression might be obtained from the example in figure 16, but not in the examples of figures 17 and 18, where the titles are not sorted according to the search string.

Hence the inventive step of the claimed subject-matter will be discussed at the oral proceedings."

VII. No reply was received from the appellant.

VIII. Oral proceedings were held by the board on 4 March 2010 in the absence of the appellant. During a break in the oral proceedings, in reply to a telephone call by the registrar, a request was received by fax from the appellant that a decision according to the state of the file be issued.

IX. At the end of the oral proceedings the board announced its decision.

Reasons for the Decision

1. The admissibility of the appeal

The appeal is admissible.

2. Amendments

Claim 1 of the present main request has the same text as claim 1 of the main request forming the basis of the appealed decision.

3. The prior art and novelty

The appellant has not commented on the board's preliminary opinion on D1, D2, the common general knowledge and novelty, set out in points 5, 6, 7 and 8, respectively, of the annex to the summons to oral proceedings (see point VI above). The board sees no reason to deviate from its preliminary opinion and thus adopts said preliminary opinion as its final position.

Consequently the board finds that the subject-matter of claim 1 differs from the disclosure of D1 in:

1. generating a directed acyclic word graph with words included in program guide data and

2. determining whether the program information is included in the program guide data by searching the directed acyclic word graph generated from the program guide data.

4. Inventive step

4.1 Again, the appellant has not commented on the board's preliminary opinion regarding the objective technical problem and inventive step, set out in points 9 and 10, respectively, of the annex to the summons to oral proceedings (see point VI above). The board, having reconsidered the appellant's case in the oral proceedings, adopts said preliminary opinion as its final position.

4.2 Hence the board regards the objective technical problem as being to determine sooner whether matches of the requested information can be found in a subsequent search (but not necessarily immediately indicated). This problem would have arisen in the context of a searching system such as that known from D1. The skilled person considering this problem would have looked for solutions in the field of searching and thus found D2. The board does not agree with the appellant's argument that D2 concerns a remote technical field, since there was a general trend towards convergence of electronic program guides and computers, and a computer constitutes one of the client devices envisaged in the present application (see paragraph [0014]). Although D2 teaches using a multiway trie, the skilled person would have modified the multiway trie to give a directed acyclic word graph to save memory space, this being a usual design consideration in the design of domestic electronic equipment.

4.3 Hence the board comes to the same conclusion as the examining division, albeit for somewhat different reasons, that the subject-matter of claim 1 does not involve an inventive step, Article 56 EPC 1973. Consequently the appealed decision cannot be set aside.

ORDER

For these reasons it is decided that:

The appeal is dismissed.