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

**AIMS**

· 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.** **

**SCOPES**

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

**AIMS**

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

**SCOPES**

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

**AIMS**

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.

**SCOPES**

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

**AIMS**

· 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;** **

**SCOPES**

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

**AIMS**

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

·
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.

**SCOPES**

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

· Dynamics

· 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

**AIMS**

· 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.

**SCOPES**

· 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

**AIMS**

· 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.

**SCOPES**

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

**AIMS**

· 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.

**SCOPES**

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

**AIMS**

· 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 the VSI’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.

**SCOPES**

Theories, tools and experiments for
verified software.

**WG 1.10 – String ****Algorithmics**** & Applications**

est. 2015

**AIMS** **and SCOPES**

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.