Concatenation State Machines and Simple Functions (algorithms and complexity)

Lead Research Organisation: University of Liverpool
Department Name: Computer Science


Finite-state and pushdown automata were introduced as the accepting devices corresponding to classes of languages of the Chomsky hierarchy. One of the potential applications of finite state automata is string classification. The class of all input strings has to be partitioned into a set of subclasses (i.e. classified) according to some criteria related to the structure (or the content) of the input. A typical example of this type is data packet classification where the input packets sent over a network have to be partitioned into classes according to their information content. A simpler case is data packet filtering that involves partitioning the input into two classes, where each input packet is either rejected , e.g., when containing computer viruses or spam, or accepted otherwise.Another class of interesting questions arise when a sample set of input strings is a priori known to be classified into the same category. The problem now consists in retrieving all strings of this class, or rather finding some simple, generic rule, defining strings of such a class. E.g., such a rule might be given with the aid of an automaton accepting strings of this class or an expression denoting them. Probabilistic methods or approximate solutions are often explored in this context. Such questions are often given in most intelligence quizzes and original, non-standard approaches are sometimes needed here.In order to store potentially large sets of classification policies in memory, it is necessary to reuse their common parts. A natural way to do this consists in decomposing simple languages into prime factors (under concatenation), each of which is stored in memory only once. When a new classification policy is added to memory, we verify if its prime factors are already stored in the data base. Fortunately, each simple language has a canonical representation by means of its (unique) decomposition into prime factors. This representation is reflected in the construction of concatenation state machine (CSM), which has not only transition states (as in a habitual finite state automaton), but also special, binary concatenation states corresponding to concatenation of two languages. The main aim of this project is to study fundamental algorithmic problems and complexity issues arising in the context of efficient design of automata (concatenation state machines) accepting simple languages.


10 25 50
publication icon
Czyzowicz J (2009) Gathering few fat mobile robots in the plane in Theoretical Computer Science