Details of Grant 

EPSRC Reference:	EP/F029136/1
Title:	Concatenation State Machines and Simple Functions (algorithms and complexity)
Principal Investigator:	Gasieniec, Professor LA
Other Investigators:	Goldberg, Professor P Potapov, Professor I
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Liverpool
Scheme:	Standard Research
Starts:	01 February 2008	Ends:	31 July 2008	Value (£):	52,005
EPSRC Research Topic Classifications:	Complexity Science Fundamentals of Computing
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.liv.ac.uk