Complexity in Algebra and Algebra in Complexity: the role of finite semigroups and general algebra. Algebra and logic form the mathematical framework for expressing and analysing algorithms and their difficulty. We can then scientifically analyse what makes some tasks more difficult than others. This project unifies parallel areas of algebra to focus on two key topics at this interface between algebra and computational complexity. As a flow on, our work can uncover new algorithms for solving ....Complexity in Algebra and Algebra in Complexity: the role of finite semigroups and general algebra. Algebra and logic form the mathematical framework for expressing and analysing algorithms and their difficulty. We can then scientifically analyse what makes some tasks more difficult than others. This project unifies parallel areas of algebra to focus on two key topics at this interface between algebra and computational complexity. As a flow on, our work can uncover new algorithms for solving constraint problems and for the study of formal languages.
With a team of top international researchers developing new interactions between mathematics and the study of algorithms, the project will foster a culture of innovation and bring Australia into the play in this internationally competitive area.Read moreRead less
Practical and theoretical aspects of structure enumeration. Many areas of study involve processing of large numbers of
objects in some class. These are countless examples in
chemistry, physics, mathematics, and other disciplines.
Structure Enumeration is the study of methods for efficient
generation and analysis of such objects. The project will
involve exploitation and extension of recent advances, many
due to the CI, which have added orders of magnitude to what
was possible only a few ....Practical and theoretical aspects of structure enumeration. Many areas of study involve processing of large numbers of
objects in some class. These are countless examples in
chemistry, physics, mathematics, and other disciplines.
Structure Enumeration is the study of methods for efficient
generation and analysis of such objects. The project will
involve exploitation and extension of recent advances, many
due to the CI, which have added orders of magnitude to what
was possible only a few years ago. The outcome will be a
combination of theoretical results and practical achievements,
whose usefulness will be demonstrated with some serious
applications in physics and mathematics.
Read moreRead less
Structure enumeration, applications and analysis. Structure enumeration and analysis is at the heart of finite mathematics and its many fields of application in diverse scientific disciplines. Australia has a substantial status in this field both in mathematics and physics. This project will enhance that status and develop greater ties with the centres of structure research in other parts of the world.
Efficient Computational Methods for Constrained Path Problems. We consider a class of path design problems which arise when an object needs to traverse between two points through a specified region. The region may be a continuous space or the path may be restricted to the edges of a network. The path must optimise a prescribed criterion such
as risk, reliability or cost and satisfy a number of constraints.
Problems of this type readily arise in the defence, transport and
communication i ....Efficient Computational Methods for Constrained Path Problems. We consider a class of path design problems which arise when an object needs to traverse between two points through a specified region. The region may be a continuous space or the path may be restricted to the edges of a network. The path must optimise a prescribed criterion such
as risk, reliability or cost and satisfy a number of constraints.
Problems of this type readily arise in the defence, transport and
communication industries. In addition to efficient solution methods
for these problems the project will produce computational tools for
a wide range of related network routing problems.Read moreRead less
Proof Theoretical Methods for Reasoning about Process Equivalence. The emergence of internet commerce has made the issue of secure computing more urgent than ever. A substantial part of the security issues with today's computer applications are due to design problems.
The principles of secure computation have not been fully understood and adequate tools for the construction of secure applications are still lacking. The understanding of the foundations of secure computation is essential in bu ....Proof Theoretical Methods for Reasoning about Process Equivalence. The emergence of internet commerce has made the issue of secure computing more urgent than ever. A substantial part of the security issues with today's computer applications are due to design problems.
The principles of secure computation have not been fully understood and adequate tools for the construction of secure applications are still lacking. The understanding of the foundations of secure computation is essential in building trusted computer applications. Process calculi and logic represent two promising disciplines in which the principles of analysis and design of secure systems can be studied systematically, out of which formal verification tools can be constructed.Read moreRead less
Generic complexity in computational topology: breaking through the bottlenecks. The project will focus on key computational problems in three-dimensional topology, with the aims of illuminating the theoretical limitations of such problems, developing new computational tools for solving them, and applying these tools to a variety of applications. The project will generate theoretical research, practical software, and rich experimental data.
Expressive power and complexity of temporal logics for model-checking. Hardware verification based upon mathematical logic is now routinely
used in industry to verify the correctness of large digital circuits
using a technique called model-checking. Such discrete systems move
from one state to another according to the regular ticks of a clock.
The challenge now is to find tractable methods for reasoning about
real-time systems and hybrid systems that move in a continuous manner
with respec ....Expressive power and complexity of temporal logics for model-checking. Hardware verification based upon mathematical logic is now routinely
used in industry to verify the correctness of large digital circuits
using a technique called model-checking. Such discrete systems move
from one state to another according to the regular ticks of a clock.
The challenge now is to find tractable methods for reasoning about
real-time systems and hybrid systems that move in a continuous manner
with respect to time: examples include aeroplanes flying according to
the laws of physics and a moving robot arm. We shall invent new logics
which are specifically tailored for tractable reasoning about
real-time and hybrid systems.Read moreRead less
Knowledge Based Model Updating for the Correctness of Security Protocols. This project will fundamentally provide a new paradigm of the security protocol verification and modification. As such, it will significantly enhance Australia's already leading role in the cutting edge research on information security. By applying the new methodology and technology, Australian IT industry will be able to develop more secure communication systems in real world domains. With a very strong research team acro ....Knowledge Based Model Updating for the Correctness of Security Protocols. This project will fundamentally provide a new paradigm of the security protocol verification and modification. As such, it will significantly enhance Australia's already leading role in the cutting edge research on information security. By applying the new methodology and technology, Australian IT industry will be able to develop more secure communication systems in real world domains. With a very strong research team across different areas such as knowledge reasoning, temporal logics and information security, and a collaborative research training environment, this project will further enhance Australia's international reputation as a leader in computing and IT research.Read moreRead less
Economical and practical design and analysis of probabilistic distributed systems. Complex computing systems composed of communicating processes are
distributed over networks, and interact with embedded hardware
components. They routinely operate in probabilistic environments:
hardware components fail randomly, but at known rates; and tactical
randomisation resolves competition for resources. Effective
specification, development and analysis methods for these systems
is crucial, and probab ....Economical and practical design and analysis of probabilistic distributed systems. Complex computing systems composed of communicating processes are
distributed over networks, and interact with embedded hardware
components. They routinely operate in probabilistic environments:
hardware components fail randomly, but at known rates; and tactical
randomisation resolves competition for resources. Effective
specification, development and analysis methods for these systems
is crucial, and probability makes that particularly difficult.
The focus of this project is to develop new formal methods that are
economical and practical in use. Exploiting our recent advances in
probabilistic program semantics, we will add probability in a new
way to proven techniques in concurrency theory, including
refinement and hierarchical design.Read moreRead less
Algebraic reasoning for serialisability in probabilistic transaction systems. The ability to analyse complex systems is a vital part of the development of large-scale computer applications; a method that improves the quality of the analysis task would increase the competitiveness of the software industry, would attract future development work (in complex and intelligent systems) to Australia, and could contribute to national security.
The results of this project will have a direct influence ....Algebraic reasoning for serialisability in probabilistic transaction systems. The ability to analyse complex systems is a vital part of the development of large-scale computer applications; a method that improves the quality of the analysis task would increase the competitiveness of the software industry, would attract future development work (in complex and intelligent systems) to Australia, and could contribute to national security.
The results of this project will have a direct influence on currently available design tools; the fact that Australian institutions will be responsible for key theoretical results in this growing field will strengthen Australia's position worldwide as an international centre for computer science.Read moreRead less