Assessing the expressiveness of OTDS: is it a Turing complete language?

This topic can be worked on in a bachelor’s thesis as well (in an extended form) in a master’s thesis.

In the German tourism market, many players are active that collaborate and exchange information to realize their business. One type of players are tour operators that organize travel packages that are often composed of transportation (usually flights) and accommodation. While these players may sell their packages on their own, they may also rely on another type of players specialized in selling packages to consumers. These so-called travel agents can be local businesses or website’s that sell the products online. For this collaboration to work, the travel agents need to be able to search and book packages offered by tour operators. Due to the plurality of players on the market, information can only be exchanged cost-efficiently between all players by using a standard interface. The Open Travel Data Standard (OTDS) is the most recent standard in the German market and gains increasing popularity among its players.

The OTDS standard allows tour operators to describe their offered packages in a detailed way. Instead of describing concrete travel packages, such as for example a hotel plus a flight for a certain date and a certain combination of travelers, tour operators can describe individual components and rules. Individual components can be flights and accommodations. Rules then define how components may be combined to packages that can be offered to consumers and what price is associated with each offer. The rules and the data are then bundled to an OTDS delivery, a zipped archive of XML files that can then be processed by other players on the market.

The expressiveness of the OTDS standard is a feature important to many players on the market, but it entails a certain complexity when processing OTDS deliveries. It can become a challenge to process the OTDS delivery such that the components are correctly combined using the given rules to offered packages. At the same time the efficiency is of high importance, as the data is updated on a regular basis up to multiple times a day.

When one studies the OTDS standard and its manifold features, one may get the impression that OTDS has expressiveness like a regular programming language. This gives reason for the following research hypothesis we want to study:

OTDS is a Turing complete language.

The motivation for investigating this hypothesis is that the answer would allow us to better assess limitations of processing OTDS deliveries. Further we might be able to make recommendations on how to further develop the standard in order to reduce the complexity of processing OTDS deliveries and increase the efficiency and scalability of the processing.

Thesis meta data

  • Type: Bachelor Thesis, Master Thesis
  • Status: Open