Powered by OpenAIRE graph
Found an issue? Give us feedback

University of Novi Sad

University of Novi Sad

3 Projects, page 1 of 1
  • Funder: UK Research and Innovation Project Code: EP/V032003/1
    Funder Contribution: 1,199,940 GBP

    One of the most amazing results of twentieth century mathematics was the discovery by Alonzo Church and Alan Turing that there are problems in mathematics which cannot be solved, in the sense that there is no algorithm to solve them. This means that no matter how powerful a computer you use to help you, there are some mathematical problems that you will still not be able to solve. If the problem that cannot be solved is in the form of a "yes" or "no" question, then we call it an undecidable problem. On the other hand, if it can be solved, then we say that it is a decidable problem. There are many decision problems that arise naturally in algebra. Important examples include the word problem, which asks us to decide whether two different algebraic expressions are equal to each other, and the membership problem, which asks us to decide whether one element in an algebraic structure can be expressed in terms of another collection of elements. Being able to solve problems like these is important when studying infinite algebraic structures. The main topic of this project is to investigate a range of decision problems like these for three classes of algebraic objects called groups, monoids and inverse semigroups. These three classes arise naturally in the study of symmetry and partial symmetry in mathematics. An important tool for defining infinite groups, monoids and inverse semigroups, is given by the theory of presentations in generators and relations. The idea is that the elements of the group or monoid are represented by strings of letters, called words. We are also given a set of defining relations, which are rules telling us that certain pairs of words are equal to each other. Two words are then equal if one can be transformed into the other by applying the relations. For example, if we use the letters x and y, and we have a single defining relation xy=yx, then the words xyx and yxx are equal since xyx = (xy)x = (yx)x = yxx. On the other hand, the words xy and yy are not equal. The problem of determining whether or not two words are equal to each other is the word problem mentioned above. When we define a monoid or group using a presentation, by increasing the number of relations we can increase the complexity of the monoid or group that we define. If there are no relations these are called free monoids and groups, and because of their simple structure several natural decision problems, like the word problem, can be seen to be decidable in these cases. In contrast, it is known that there are monoids, groups, and inverse semigroups which are defined by finitely many generators and relations, but have undecidable word problem. The situation is the similar for the many other decision problems arising in algebra. It is natural to ask whether groups or monoids which are close to being free, in some sense, will have good algorithmic properties. An important positive result of this kind for groups is Magnus's theorem which shows that groups defined by a single defining relation all have decidable word problem. On the other hand, it was recently discovered that there are inverse monoids defined by a single defining relation that have undecidable word problem. However, it remains an important longstanding open problem whether the word problem is decidable for one-relator monoids. There are many fascinating open problems like this one which ask fundamental questions about where the boundary between decidability and undecidability lies for finitely presented groups, monoids and inverse semigroups. In this project we will explore a range of interrelated problems of this kind. This will be done by developing geometric and topological methods, which use the "shape" of these algebraic objects, or the way they interact with spaces, to shed light on their algorithmic properties.

    more_vert
  • Funder: UK Research and Innovation Project Code: EP/N033353/1
    Funder Contribution: 100,576 GBP

    This project is concerned with the study of certain fundamental objects in algebra called groups, monoids and inverse monoids. These objects arise naturally in the mathematical study of symmetry and partial symmetry. Given any mathematical structure on a set, the collection of structure-preserving mappings from the set to itself form a monoid, the collection of all symmetries form a group, while the partial symmetries give rise to an inverse monoid. In this way these algebraic objects pervade mathematics. One way to represent a group, monoid of inverse monoid is via a presentation. The elements are represented by strings of letters, called words. We are also given a set of pairs of words, called defining relations, which are rules telling us that certain pairs of words are equal to each other. Then two words are defined to be equal if one can be turned into the other by a sequence of applications of the defining relations. For example, using the alphabet with the letters a and b, and just with a single defining relation ab=ba, the words aba and aab are equal since aba = a(ba) = a(ab) = aab. On the other hand, the words bb and ab are not equal since one cannot be transformed into the other using the relation ab=ba. A famous result in twentieth century mathematics shows that there does not exist, in general, an algorithm to decide whether two words are equal in a monoid defined by a finite presentation. This is known as the word problem, and is also undecidable in general both for finitely presented groups and inverse monoids. These results are important since they were some of the first concrete natural decision problems proven to be undecidable in general. The importance of the word problem is clear: decidability of the word problem for a class of algebras indicates that we have some hope of studying the structural properties of algebras in the class, while undecidability of the word problem would suggest there would likely to be major difficulties in investigating the class as a whole. Given that the word problem is undecidable in general, a lot of research has been done to identify classes of monoids for which the word problem is decidable. One fundamental idea is that by restricting the number of defining relations in the presentation, this should limit the complexity of the object that it defines. An important result of this kind for groups is Magnus's theorem which shows that groups defined by a single defining relation all have decidable word problem. In contrast to this, the following problem remains open: Open problem. Is the word problem decidable for monoids with a single defining relation? This important problem has been open for more than half a century, and is one of the main motivations for our research project. Rather than attacking this problem directly, the project instead aims to develop various aspects of the theory of certain inverse monoids, called special inverse monoids. Specifically the project will develop certain important tools from theoretical computer science, from the area of rewriting systems, to investigate the subgroups, structure, and geometry of these inverse monoids. We will then apply this theory to investigate the word problem for these inverse monoids which will then lead to important results about decidability of the word problem, in general, for monoids defined by a single defining relation. The project will involve extensive collaboration with researchers both from the UK and from universities in Portugal, Serbia and the USA. We will organise a workshop midway through the project, centred around its main themes, which will bring together leading experts from a diverse range of topics in algebra, logic and theoretical computer science.

    more_vert
  • Funder: UK Research and Innovation Project Code: AH/K006002/1
    Funder Contribution: 79,349 GBP

    It is widely recognized that the historic environment provides a source of cultural enrichment, and enhances people's quality of life and well-being. However, it also undergoes cycles of material transformation, of decay and renewal, which inform the meanings and values associated with it. Indeed, these changes contribute to the experience of authenticity. Decay acts as a tangible mark of age, and the patina produced by everyday weathering and wear provides a sense of connection across generations. At the same time processes of decay and degradation are assessed and arrested by organisations charged with conserving the historic environment for future generations. Much of this work relies on scientific methods and techniques, which have been developed for use in conserving the historic environment. However, by intervening to modify processes of transformation and decay, these techniques can have a powerful impact on the fabric of historic buildings. They can alter their appearance and introduce new materials, as well as affect the cultural meanings and values attached to them by various groups of people. In this project we use methods from the arts and humanities, including interviews and forms of participant observation, to examine the kinds of value attached to deterioration and decay in historic buildings. We investigate how decisions about the conservation of materials are informed by these values and related ideas of authenticity. We also explore how science-based interventions alter these meanings and values, and impact on perceptions of 'the real' and the 'authentic'. Our partners include the National Trust for Scotland and Historic Scotland, organisations that are involved in conserving and managing some of Scotland's most important historic sites. They provide case studies involving particular historic buildings or monuments that are currently the subject of active conservation. This provides us with the opportunity to study how the science-based techniques they use both inform, and are informed by, cultural values and ideas of authenticity. Our project brings together researchers from the humanities and the sciences in a cross-disciplinary collaboration. We are also in partnership with the leaders of a European research project (HEROMAT), which allows us to study the values attached to the latest developments in scientific conservation methods. The research will be of benefit to a wide range of academic researchers and professionals involved in conserving the historic environment. The results are intended to inform future conservation policy and practice, ensuring that science-based techniques are used in a culturally sensitive way in conserving the historic environment.

    more_vert

Do the share buttons not appear? Please make sure, any blocking addon is disabled, and then reload the page.

Content report
No reports available
Funder report
No option selected
arrow_drop_down

Do you wish to download a CSV file? Note that this process may take a while.

There was an error in csv downloading. Please try again later.