TC 1 - Foundations of Computer Science - Aims and Scopes

est. 1989 as SG14 / approved in 9/96 as TC 1


       to support the development of theoretical computer science as a fundamental science that has similar scientific goals in understanding the information processing world as physics has in understanding the energy processing world and similar goals in developing methodology for science and technology as mathematics does;

       to support the development and exploration of fundamental concepts, models, theories, systems, and other basic tools and the understanding of laws, limits, and possibilities of information processing as well as to de-velop bridges with other sciences and their applications. 


To encourage, organise, support, and unify the development of the following areas:

       frontiers, laws, and limits of information processing;

       fundamental formal systems;

       efficiency and complexity of information processing;

       formal systems to specify, design, verify, analyse, and manipulate

       complex information processing systems;

       theoretical foundations of various other parts of computer science and its main application areas;

       scientific paradigms of informatics and their relations to other disciplines;

       information processing fundamental concepts, models and theories to support the development of other sciences. With the goal to develop foundations and to make use of them.

WG1.1 - Continous Algorithms and Complexity
est. 1992


To provide a forum for international collaboration and for the dissemination of research and applications of continuous algorithms and complexity. 


Many problems in natural science, engineering, social science and business have continuous models. Hence the scope of WG 1.1 is algorithms and especially computational complexity of algorithms for solving continuous models. By computational complexity is meant the intrinsic difficulty of solving such problems. Examples of the problems that are being studied include: ordinary and partial differential equations, continuous optimization, multivariate integration and approximation, matrix multiplication, and systems of polynomial equations.

Of special interest is the solution of continuous problems on parallel and distributed computer systems. 

WG1.2 - Descriptional Complexity
est. 1992, revised 2017


Descriptional complexity has historically been a multidisciplinary area of study, with contributions from automata theory, computational complexity, cryptography, information theory, probability, statistics, pattern recognition, machine learning, computational learning theory, computer vision, neural networks, formal languages and other fields. The aims of the working group are therefore:

       To promote research in all aspects of descriptional complexity through conferences, publications, and more informal means of scientific interaction such as electronic news groups;

       To promote interaction and the exchange of information across traditional discipline boundaries;

       To provide a point of contact for all researchers in all disciplines interested in descriptional complexity and its applications.


The scope of the working group encompasses all aspects of descriptional complexity, both theory and application. These aspects include but are not limited to:

       Algorithmic and other descriptional theories of randomness;

       The use of descriptional randomness and associated descriptional complexity measures in computational complexity, cryptography, information theory, probability, and statistics;

       The minimum description-length principle, stochastic complexity, algorithmic probability, and other descriptional complexity measures related to inductive inference and prediction;

       The use of such descriptional complexity measures in statistical inference, pattern recognition, machine learning, computational learning theory, computer vision and neural networks;

       Generalized descriptional complexity measures and their properties, including resource-bounded complexity, structural complexity, hierarchical complexity, and the complexity of sets, languages, grammars, automata, etc.;

       Program complexity and reliability of software.


WG1.3 - Foundations of Systems Specifications
est. 1992


       To support and promote the systematic development of the mathematical theory and the foundations of systems specifications;

       To investigate the theory of formal models for systems specifications, development, transformation and verification; 


The theoretical aspects of the specification and development of computing systems that are based on algebraic and logic concepts and can be studied systematically within a theory of systems specifications. 

WG 1.4 - Computational Learning Theory
est.1995, dissolved 2015

WG 1.5 - Cellular Automata and Discrete Complex Systems
est. 1994, dissolved 2004, re-established 2008, revised 2009


The Working Group 1.5, on Cellular Automata and Discrete Complex Systems, has the following attributions:

       To establish and maintain a permanent, international, multidisciplinary forum for the collaboration of researchers in the field of Cellular Automata (CA) and Discrete Complex Systems (DCS).

       To provide a platform for presenting and discussing new ideas and results.

       To support the development of theory and applications of CA and DCS (e.g. parallel computing, physics, biology, social sciences, and others) as long as fundamental aspects and their relations are concerned.

       To identify and study within an inter- and multidisciplinary context, the important fundamental aspects, concepts, notions and problems concerning CA and DCS.


The scope of the working group encompasses all fundamental aspects of cellular automata and discrete complex systems, including:


       Algebraic aspects

       Complexity issues

       Emergent properties

       Formal language processing

       Models of parallelism and distributed systems

       Phenomenological descriptions

       Scientific modeling

       Practical applications



WG 1.6 - Rewriting
est. 1998, revised 1999


       To promote research efforts in rewriting and its applications.

       To establish close cooperation between existing groups and to facilitate the emergence of new ones.

       To increase awareness of rewriting techniques in the computer science community at large.

       To foster development of applications of theoretical advances.


       Rewriting for computing and reasoning

       Theoretical studies of the rewriting relation of different orders.

       Complexity issues of rewriting.

       Compilation techniques and applications.

       Theory and applications of rewriting logic and calculus

       Application of rewriting to constraint solving, theorem proving and algebraic specifications

       The design, promotion and teaching of rewrite based techniques and applications.

WG 1.7 - Theoretical Foundations of Security Analysis and Design
est. 1999


       To investigate the theoretical foundations of security as an independent discipline with firm grounds in logic, semantics and complexity.

       To discover and promote new areas of application of theoretical techniques in computer security.

       To provide a platform for presenting and discussing emerging ideas and trends.

       To strengthen research efforts in current and emerging applications of formal methods and related approaches to the design and analysis of secure systems and applications.

       To make formal methods amenable to the security practicioners, hence increasing awareness of formal verification techniques for security in the computer science community at large.

       To support and promote the systematic use of formal techniques in the development of security related applications.

       To encourage researchers, especially younger ones, to enter this field.

       To promote or support the organization of meetings in this and related areas.

       To provide a clearinghouse for dissemination of information and publications, also with industry.


The main research topics relevant for the Working Group include:

       formal definition and verification of the various aspects of security: confidentiality, integrity, authentication and availability;

       new theoretically-based techniques for the formal analysis and design of cryptographic protocols and their manifold applications (e.g., electronic commerce);

       information flow modelling and its application to the theory of confidentiality policies, composition of systems, and covert channel analysis;

       formal techniques for the analysis and verification of mobile code;

       formal analysis and design for prevention of denial of service.  

WG 1.8 - Concurrency Theory
est. 2005


       To develop theoretical foundations of concurrency, exploring frontiers of existing theoretical models like process algebra and various process calculi, so as to obtain a deeper theoretical understanding of concurrent and parallel systems.

       To promote and coordinate the exchange of information on concurrency theory, exchanging ideas, discussing open problems, and identifying future directions of research in the area.


The activities of this WG will encompass all aspects of concurrency theory and its applications. The themes of the WG include:

       process algebras and calculi,

       expressiveness of formalisms for concurrency,

       modal and temporal logics for concurrency and their extensions,

       resource sensitive approaches to concurrency and their developments,

       tools for verification and validation of concurrent systems,

       reactive models for real-time and hybrid systems,

       calculi and typing systems for mobile processes and global computing,

       stochastic and probabilistic models of concurrent processes,

       behavioral relations for processes,

       decidability and complexity issues in concurrency theory,

       semantic frameworks for concurrency such as structural operational semantics,

       integration of concepts from concurrency theory into specification, modeling and programming languages, and (global) concurrent systems, and

       exploration of the frontiers of concurrency theory in connections to various branches of computer science, including theories of operating systems, internet languages, Petri nets and their applications, communication protocols, security issues on the internet, global ubiquitous computing, distributed algorithms, embedded systems, software architectures and engineering, automata theory; information theory, various formal methods, control theory and robotics, bio-computing, quantum computing, and other emerging areas.

WG1.9/2.15 Verified Software
est. 2010


       To contribute to a comprehensive theory of programming that covers the features needed to build practical and reliable programs.

       To contribute to a coherent toolset that automates the theory and scales up to the analysis of industrial-strength software.

       To collect realistic, verified programs as part of the Verified Software Initiative (VSI) Repository.  It will do this using the following means:
* By encouraging members to solve agreed theoretical problems, adapt tools to advance the state of the art, and to populate the VSIís Repository by conducting experiments using theVSIís open problem collection.
* By having a sharply focused common sense of purpose.
* By being committed to making progress on the VSI roadmap.
* By producing deliverables determined by the membership.
* By further developing the research agenda, collecting open problems, recording progress with appropriate milestones, etc.


Theories, tools and experiments for verified software.

WG 1.10 Ė String Algorithmics & Applications
est. 2015


We will focus in String Algorithmics (combinatorics on words, string algorithms) and

applications. We propose a unique forum for the best available research that will provide

sustained inspiration within the stringological community for still better research. There
is no other group that specializes in the area that the SA would cover.