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

**SCOPE**

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

**SCOPE**

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

**AIMS**

·
to promote research in all aspects of descriptional complexity
through conferences, publications, and more in-formal means of scientific
interaction;

·
to promote interaction and the exchange of information across
traditional disciplinary boundaries;

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

**SCOPE**

All aspects of descriptional complexity, both theory and
application. These aspects include:

·
generalized descriptional complexity measures and their
properties, including resource-bounded com-plexity, structural complexity,
hierarchical complexity, trade-offs in succinctness, and the complexity of
sets, languages, grammars, automata, etc.;

·
algorithmic and other descriptional theories of randomness;

·
the use of descriptional randomness and associated descriptional
complexity measures in computational complexity, economy of description,
cryptography, information theory, probability, and statistics;

·
descriptional complexity measures for
inductive inference and prediction, and the use of these measures in machine
learning, computational learning theory, computer vision, pattern recognition,
statistical inference, and neural networks.

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

**SCOPE**

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

**AIMS**

To promote the
field of computational learning theory and to establish close cooperation
between existing groups working in geographically separated areas. To support
steps helping to bridge theory and applications.** **

**SCOPE**

·
Computational and complexity-theoretic aspects of learning

·
Investigation of formal models of learning

·
The teacher/learner and other learning paradigms

·
Neural networks and learning

·
Kolomogorov complexity approach to learning

·
Application of the computational and complexity approach to
learning to the design of learning systems

**WG
1.5 - Cellular Automata and Discrete Complex Systems**

est.
1994, dissolved 2004, re-established 2008

**AIMS**

To support the
development of cellular automata theory and their applications (especially in parallel
computing, in the study of complex systems, in physics, biology, artificial life, ...). To pursue the design and
utilization of cellular automata machines.

**SCOPE**

Cellular automata as models of parallelism, complex systems,
dynamic systems, interactive behavior, physical systems and models of
biological systems. Cellular automata machines.

**WG
1.6 - Term 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.

**SCOPE**

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

**SCOPE**

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.

**SCOPE**

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.

**SCOPE**

Theories, tools and experiments for verified software.