Aspasia Togia

Eleftheria Koseoglou

Sofia Zapounidou

INDEX Nikolaos Tsigilis

Open access infrastructure in Greece : current status, challenges and perspectives

Keywords: Open Access Infrastructure in Greece: Current Status, Challenges and Perspectives Open Access, Open Access Policy, Scholarly communication, Institutional Repositories, Open Access Journals, Greece

HAL is

Introduction 1

Advances in information technology and the globalisation of science have brought significant changes in the ways research is created, disseminated and consumed. Open Access (OA) has become an important component in scholarly communication and is growing fast [START_REF] Laakso | The Development of Open Access Journal Publishing from 1993 to 2009[END_REF][START_REF] Morrison | The dramatic growth of Open Access[END_REF], mainly due to the benefits it provides to individuals, universities and the research in general, as well as to the support it has received from governments, organisations, institutions, and libraries. OA seeks to remove price and permission barriers [START_REF] Suber | Ensuring open access for publicly funded research : right way to mix green and gold approaches[END_REF] so that scientific literature is freely available on the public internet permitting users to use it for any "lawful purpose, without financial, legal, or technical barriers other than those inseparable from gaining access to the internet itself" [START_REF] Chan | Budapest Open Access Initiative[END_REF]. The movement of OA is associated with the notion of open science, which basically concerns the sharing of knowledge. Rather than a standard form of open access being adopted, a range of different OA types have been developed, with varied approaches to issues such as reader rights, reuse rights, copyrights, and cost of publishing. Different models include :

• Libre OA [START_REF] Suber | Gratis and libre open access[END_REF] : free of charge, it extends user's rights to reuse beyond fair use.

• Gratis OA [START_REF] Suber | Gratis and libre open access[END_REF] : free of charge, it allows no uses beyond fair use.

• Delayed OA : paid access initially, becoming free to read after a delay period or embargo [START_REF] Willinsky | The access principle : the case for open access to research and scholarship[END_REF][START_REF] Laakso | Delayed open access : an overlooked high-impact category of openly available scientific literature[END_REF].

• Gold OA : unrestricted online access to articles published in scholarly journals, sometimes with a publication fee [START_REF] Archambault | Proportion of open access papers published in peer-reviewed journals at the European and world levels-1996-2013[END_REF][START_REF] Chan | Budapest Open Access Initiative[END_REF].

Open access infrastructure in Greece : current status, challenges and perspec... ELPUB 2018

• Green OA : articles are published in toll-access journals, but self-archived in an OA archive, usually an institutional or a disciplinary repository. [START_REF] Björk | Open access to the scientific journal literature : situation 2009[END_REF][START_REF] Harnad | The access/impact problem and the green and gold roads to open access : an update[END_REF].

Most Green OA does not extend reuse rights.

• Hybrid OA : articles are published in subscription journals but are free to read against an article processing charge (APC) [START_REF] Laakso | Delayed open access : an overlooked high-impact category of openly available scientific literature[END_REF].

• Bronze OA : articles are free to read on the publisher website, without an explicit Open license [START_REF] Piwowar | The state of OA : a large-scale analysis of the prevalence and impact of Open Access articles[END_REF].

The most common distinction is between Gold and the Green OA, and it is unclear which approach will predominate. [START_REF] Harnad | The access/impact problem and the green and gold roads to open access : an update[END_REF] suggest that the faster and more secure way to achieve 100 % OA is providing a mandate for the green road. [START_REF] Suber | Ensuring open access for publicly funded research : right way to mix green and gold approaches[END_REF] suggests that the green and the gold routes have complementary advantages and the balance between them will ensure unrestricted access to publicly funded research.

There is evidence that OA is associated with higher impact of research products as a result of availability and reuse [START_REF] Tennant | The academic, economic and societal impacts of Open Access : an evidence-based review[END_REF], contributing at the same time to the enhancement of the quality of research through the transparency and the democratisation it offers [START_REF] Elsabry | Claims About Benefits of Open Access to Society (Beyond Academia)[END_REF]. It enables readers outside of academia to use scientific literature for personal problem solving, increase their understanding of science and see how public money is being invested [START_REF] Zuccala | Open Access and Civic Scientific Information Literacy[END_REF]. OA gives universities the opportunity to increase their ranking position [START_REF] Baldock | Citations, open access and university rankings[END_REF] and offers a viable solution to escalating costs of academic journals [START_REF] Houghton | Economic implications of alternative scholarly publishing models : Exploring the costs and benefits[END_REF].

Several governments and national research bodies, in the European context particularly, have set their goals of publishing between 50 % and 80 % -if not all -of their national research output as open access within the next years. Towards this end, policies, budget provisions and administrative structures are being developed accordingly (Schimmer, Geschuhn, & Vogle, 2015). OA is a core strategy in European Union, and since 2006 the European Commission has been developing policies on OA and open science through many reports, guidelines, recommendation, projects and initiatives initiatives (European Commission, 2017), while OpenAIRE/OpenAIRE-Advance project (https:// www.openaire.eu/) is the implementation of open access via successful infrastructure comprised of a human network and robust technical services. European Union identifies three main tenets to ensure that everyone will have access to scientific papers published in Europe : "Sharing knowledge freely", "open access", and "reusing research data" (United Nations University, 2016).

OA infrastructure is necessary for implementing open access and open science in any country. Open access infrastructures in Greece have been steadily improving over the past years, as more and more stakeholders follow international trends and participate in European networks and projects. The aim of the present paper is to give a description of the Greek OA infrastructure with emphasis on academic repositories and OA journals. Building upon previous literature [START_REF] Banou | Managing Expectations for Open Access in Greece : Perceptions from the Publishers and Academic Libraries[END_REF][START_REF] Chantavaridou | Open access and institutional repositories in Greece : progress so far[END_REF][START_REF] Georgiou | Open access in Greece[END_REF] and relying of data collected from directories and aggregators, such as OpenDoar, ROAR and OpenDoaj, as well as from systematic research by the authors, the article presents information relating to the state-of-the-art of OA in order to identify current trends and future challenges. In addition, to in an effort to examine the level of OA availability of the Greek scholarly output, we used the Unpaywall database (https://unpaywall.org) to find OA information for publications authored by researchers affiliated with Greek HEIs.

Research landscape and scholarly communication in Greece 6

The three main funding sources of Research and Development (R&D) activities in Greece are the public funding, the business enterprise sector, and the European Union. In Higher Educator Sector specifically, public funding is the main source, providing 66,3 % of the total funds in 2016, while the European Union and the enterprise sector provided 18 % and 7. 3 % respectively (National Documentation Centre, 2018). In 2016 R&D constituted 1.01 % of GPD placing Greece below the average expenditure in EU countries (Figure 1). Research is carried out by three main institutions : HEIs, Research Centres supervised by the General Secretariat for Research and Technology, and Public Hospitals. In 2014, Greek publications accounted for 2.10 % of the total publications produced in EU, and 1.06 % of the publications produced in OECD member countries. Since 2007, and after a period of continuous growth, the share of Greek publications and the position of Greece, both in EU and OECD, have been declining. However, considering the number of publications in relation to the national expenditure on R&D, Greece is in the first positions within EU, a fact indicating the high productivity of the research system in the country (Figure 2). The publishing industry in Greece is characterised by traditional, small to medium sized, family-owned enterprises. Scientific publications are being produced by three kinds of publishers : exclusively STM publishers, general publishers, which publish scientific books, and organisations, such as scientific institutions, museums, etc. [START_REF] Banou | Managing Expectations for Open Access in Greece : Perceptions from the Publishers and Academic Libraries[END_REF]. The STM publishing production represents a very small proportion of annual book production, which is oriented to Humanities and Literature (Table 1). Nearly half of the STM books are translations of foreign titles [START_REF] Georgiou | Open access in Greece[END_REF]. 2). However, these represent only a small proportion of the total research output of the country, as, especially in the area of STM, researchers largely publish in international journals. 10 In 1998, and as a response to the shrinking journal collections in Greek academic libraries due to stagnant budgets and high price increases, a national consortium, the Hellenic Academic Libraries Link (Heal-Link), was established. Members of Heal-Link are 54 libraries -all Greek academic institutions, the National Library of Greece, many research centres, and some special libraries. Its main purpose is to provide the entire academic and research community access to electronic journals of various disciplines and publishers. In addition, Heal-Link negotiates license agreements for groups of members interested in specific electronic resources [START_REF] Hormia-Poutanen | Consortia in Europe : describing the various solutions through four country examples[END_REF]. All Heal-Link members have access to the full-text of approximately 11,000 international journals and 67,000 e-books. The cost of Heal-Link license agreements is covered by the Ministry of Education. In addition to the content provided through Heal-link, academic libraries also acquire print and electronic resources through their own budgets. The largest part of academic libraries funding comes from their parent institutions, which in turn are almost exclusively dependent by state funding.

Open access in Greece

11 Progress in Greece in the OA issues is mainly the result of the rapid evolution in the content management approach, which has been taken place since 2000, driven mainly by academic libraries, and materialised due to EC funding [START_REF] Georgiou | Open access in Greece[END_REF].

Open access to scientific content, despite the gaps in the regulatory framework on research, has been supported through the enhancement of e-infrastructures, mainly towards the development of institutional repositories, but also through the participation of the relevant stakeholders in EU programmes. Greek organisations that play an EKT has developed the National Archive of PhD Theses, which currently contains bibliographic records with metadata for 38446 and the full-text of 35787 PhD theses from all HEIs in Greece as well as PhD theses awarded to Greek scholars by foreign universities.

The full-text is available for browsing and printing one-page-at-a-time. The PDF is made available for download to registered users that have accepted the pertinent terms and conditions.

Institutional repositories

The EU funded national projects enabled almost every academic institution in Greece to develop its own repository. As a result, 28 out of 36 HEIs run an institutional repository (Table 3). Of those, 15 are listed in DOAR and 13 are registered in ROAR. Overall, DSpace is the software more frequently used, and Dublin Core the prevalent metadata format. However, only three repositories are aggregated by the OpenAIRE portal, wihle OAI-PMH compliance tests using the OAI PMH Validator & Data Extraction Tool (Banos, c2011-2018 revealed that 18 repositories have validated OAI-PMH services. All repositories host multiple types of collections, ranging from grey literature and journal archives to administrative documents and educational resources. A closer look at the contents reveals that they mostly include EDTs. This is related to the fact that HEIs regulations require students to submit an electronic copy of their theses to the IR.

In nine cases there is free and unrestricted access to the contents of the repository. In sixteen repositories the full text of some items is not available, while in 3 institutions access is limited to registered users or affiliated members. Half of the repositories contain publications of faculty members, though the numbers are extremely small compared to the institutions' overall research output, and access to the full-text is limited. For instance, in the case of the Aristotle University of Thessaloniki, the largest university in Greece that runs one of the richest repositories in the country, only 30 % of the publications contributed by faculty are available in full text. 4). Thirty-one of these journals are listed in DOAJ and 26 in ROAD.

OA publications in international venues

20 As it has already been mentioned, most of Greece's research output is channeled to international journals. In order to get a rough picture of the percentage of this content that is OA we used Unpaywall (https://unpaywall.org/) to find out open access versions of articles authored by Greek researchers. "Unpaywall is powered by a database of 100 million scholarly papers. Of these, about 16 million have links to fulltext open access, making it the largest open database of legal Open Access" (Unpaywall, n.d.). Unpaywall harvests OA content from a wide range of sources including repositories, pre-print servers, gold OA journals, hybrid journals, and services like DOAJ and Crossref. We selected the top ten Greek universities in the Scimago Institutions Rankings (http:// www.scimagoir.com/index.php). These include seven general, multidisciplinary universities and three specialised institutions in Engineering, Agriculture, and Economics respectively (Table 5). 21 We used Scopus to collect the publications of authors affiliated to the above institutions. Publications without DOI were excluded from the Unpaywall check. Lists of DOIs in sets of 10000 were uploaded to Unpaywall and the check results were emailed to us as spreadsheets. When multiple versions of OA are available, Unpaywall includes the "best" OA evidence, prioritizing publisher-hosted content over content found in repositories [START_REF] Bosman | Open access levels : a quantitative exploration using Web of Science and oaDOI data[END_REF].

22 Of the 146461 publications found in Scopus 126486 (86.4 %) had a DOI. 109358 DOIs were located in the Unpaywall database and of them only 31905 (29.2 %) corresponded to publications available in OA form. Open access publications accounted for the 21.8 % of all publications authored by researchers affiliated to the institutions included in the sample. OA levels were similar for all institutions, ranging between 20 % and 30 %, except for the University of Crete and the University of Athens, which had rates of 41.5 % and 38 % respectively (Figure 3). 23 Types of publications are presented in Table 6. The overwhelming majority were journal articles, 32.5 % of which were available in some kind of OA form. 24 Data showed that 75 % of the OA versions of articles were hosted by publishers, thus representing gold, bronze or hybrid articles, while the rest 25 % were green papers, hosted by repositories. However, the opposite is the case with respect to papers in conference proceedings, the majority of which are available in repositories (Table 7).

Discussion and conclusions

This study includes a brief of the Greek OA landscape, with emphasis on academic Institutional Repositories and open access journals. In addition, it provides an analysis of the OA availability of research outputs produced by Greek researchers and published in international venues.

In the past ten years Greek OA scholarly journals have been significantly increased : from 84 reported in 2009 by [START_REF] Georgiou | Open access in Greece[END_REF] to 116 today. Academic institutions have emerged as key players in OA publishing, alongside the various scientific and professional societies that prevailed a few years ago. Indicative of this trend are the recent initiatives of some academic libraries to provide electronic publishing platforms and host OA journals published by university faculties, departments etc. These services, together with EKT's epublishing, seem to have been particularly well received by scholars in Humanities and Social Sciences, and they have contributed to the escalation in the number of OA titles in these areas. However, many aspects of OA journal publishing have to be considered, such as compliance with open standards and technologies, adequate search and retrieval functions, standardised preservation solutions, viable business models and sustainability [START_REF] Georgiou | Open access in Greece[END_REF][START_REF] Hodgson | Open access infrastructure : where we are and where we need to go[END_REF].

Repositories are now established in the majority (72 %) of HEIs in Greece, and openarchives.gr functions as a national aggregator for OA content. All repositories host various kinds of collections and very often the same type of material is labeled by different collection names across the repositories, making the categorisation of material rather difficult. Moreover, multiple types of contents present a challenge for end user searching and retrieval [START_REF] Georgiou | Open access in Greece[END_REF]. IRs do not have an explicit copyright policy neither do they include guidelines about copyright issues. Despite their numerical increase, they do not reflect the extent of the research output of their academic communities. Their focus is on collecting postgraduate and doctoral theses, and these dominate the content of the collections. The extremely low numbers of articles and conference papers -not to mention research data -suggest that Greek scholars have not been convinced to deposit their research outputs, despite the heavy investment of financial and human resources needed to establish and maintain an IR. The development of institutional OA policies is critical for OA implementation and there is evidence that institutional mandates play an important role in the uptake of OA at HEIs [START_REF] Pinfield | Making open access work : The 'state-of-the-art' in providing open access to scholarly literature[END_REF]. Of equal importance is the need to promote the benefits of open access to researchers and highlight its advantages in terms of greater impact, more citations and increased visibility. Well-funded implementation, regular policy review, improved repository service, and consistent advocacy of the advantages of OA, all have been recognised as important elements required to achieve a successful OA model [START_REF] Armbruster | Implementing Open Access : policy case studies[END_REF].

In an effort to estimate what proportion of the literature produced by Greek researchers is available OA, we used Unpaywall service to examine a sample of scholarly publications of authors affiliated to Greek universities. We found 29 % of all DOI-assigned publications are OA, a score similar to those found in other studies and falls within the range that has been reported for European countries [START_REF] Bosman | Open access levels : a quantitative exploration using Web of Science and oaDOI data[END_REF][START_REF] Piwowar | The state of OA : a large-scale analysis of the prevalence and impact of Open Access articles[END_REF]. Levels of green OA were rather low, accounting for nearly 30 % of all OA publications. However, this figure is not representative of the total level of green OA, as publications also available in some form of gold OA are excluded by Unpaywall. Low levels of green OA have been also attributed to the incomplete harvesting of institutional repositories [START_REF] Bosman | Open access levels : a quantitative exploration using Web of Science and oaDOI data[END_REF]. In fact, IRs of Greek HEIs are not included in the Unpaywall sources of OA content.

So far, Greek academic institutions do not generally support their staff in taking full advantage of the benefits of OA. University of Patras is the first university in Greece to actively encourage OA by participating in the Open Library for Humanities and the institutional OA programme of MDPI. Furthermore, subscription to BioMed Central enables faculty members to publish their research results in OA journals and have a discount on publication costs.

Looking ahead, the implementation of national open policies and funders mandates is the main challenge for the development of open access in Greece. Towards this goal, the active and systematic engagement of all stakeholders (policy makers, funders, librarians, researchers and the wider academic community) is required. Funding bodies and research organisations must adopt OA policies for both publications and research data.

According to the national roadmap towards the implementation of the European Research Area (ERA), until 2025, all publicly funded research will be freely accessible. In addition, Greece will investigate ways to support the transition from the existing subscription-based system to a model of OA, examining the financial aspects of such models and determining the process of the transition (General Secretariat for Research and Technology, 2016).

32 There are also several requirements to be met at the infrastructural level, including :

• Using ORCIDs for Greek faculty and researchers to enable disambiguation and discoverability of their work BIBLIOGRAPHY

Figure 1 .

 1 Figure 1. GERD as a percentage of GPD in 2016

Figure 2 .

 2 Figure 2. Number of publications per millions spent on R&D in 2014

  research at the time of writing this paper revealed 116 active OA scholarly journals. The majority of them (70 %) are published in the fields of Arts/ Humanities and Social Sciences. Medical Sciences are third in the row, with 29 % of journals, followed by Science and Engineering. Academic institutions and societies are more active in journal publishing. Sixteen journals are being published by research centres, 7 by other institutions, such as museums and hospitals, and 5 by commercial publishers (Table

Figure 3 .

 3 Figure 3. Publications of Greek Universities

Figure 4 .

 4 Figure 4. OA over time

Table 1 . Book production by subject 2007-2011 Subject 2007 2008 2009 2010 2011

 1

	Humanities & SS	26.0 % 25.4 % 25.3 % 28.1 % 26.7 %
	Pure & Applied Sciences	6.6 % 7.4 % 7.7 % 7.5 % 6.0 %
	Literature	21.5 % 21.0 % 23.7 % 24.3 % 27.9 %
	Children's books	17.6 % 20.5 % 19.6 % 17.7 % 18.0 %
	Auxiliary school books & ELT	8.6 % 8.1 % 6.0 % 5.7 % 5.9 %
	Art books	7.5 % 6.9 % 7.4 % 6.9 % 6.8 %
	General, practical & self-help books 12.2 % 10.5 % 10.2 % 9.8 % 8.5 %
	(Source : National Book Centre)

Table 2 .

 2 Peer-review journals and their publishers

Subject Peer-review titles Academic Research Society Commercial Other

	Humanities & Arts 19	2	8	6	3
	Medical Sciences 61	2	1	53	4	1
	Science	17	5	4	5	3
	Social Sciences	58	13	4	15	21	5
	Technology	8	4		4
	Total	163	26	17	83	31	6

(Source :

[START_REF] Georgiou | Open access in Greece[END_REF]

  Open access infrastructure in Greece : current status, challenges and perspec... ELPUB 2018 important role in the area of open access/open science, both within the country and at European level are the following : i. The Greek Research and Academic network (GRNET S.A.), that provides research organisations with network technologies and cloud infrastructures ; ii. The "Athena" Research and Innovation Centre, which provides management services for research and Linked Open Data services to support open access initiatives of the public sector ; iii. The National Documentation Centre (EKT), which aggregates and provides access to the Greek scientific output ; iv. The HEAL-Link, which provides services related to HEIs' open access repositories (General Secretariat for Research and Technology, 2016). Although many academic libraries make extensive reference to OA, and the Rectors' Conference approved, in 2012, open access for the dissemination of scientific results, and signed the Berlin Declaration, neither HEIs nor research centres have adopted the relevant policies. There are only four institutional OA mandates registered in ROARMAP, three by universities and one by a research centre : the International Hellenic University, the Technical University of Crete, the Panteion University, and the Archimedes Centre for Modeling, Analysis & Computation. However, the latter two have not specific policy terms. Policies of the Archimedes research centre are mainly content, submission and preservation policies rather than deposit mandates, and Panteion University states that its policy is in line with Berlin Declaration, without specifying specific terms. harvests the metadata of collections that are OAI-PMH compatible and provides a single-point-of-access to digitised contents of academic and research institutions, archives, libraries and scientific societies. The platform includes a harvester, which collects metadata from individual sites and repositories. After harvesting, the content is semantically enriched by a bilingual vocabulary and semantic enrichment system, which offers semantic cohesion and improve its searchability, presentation and multilinguismby the Semantics.gr. The import process takes place through the Aggregator accumulation management environment and the content is finally published on the OpenArchives.gr portal. The portal layout has been recently redesigned to provide improved search and browsing facilities. Openarchives.gr hosts 72 different collections, such as journals, institutional repositories, archives, scientific publications, books and collections of grey literature. It offers access to approximately 650.000 items, including more than 200,000 scientific articles, 170,000 theses or dissertations, 47,000 conference items and many more.

International Hellenic University's policy, adopted in 2015, is mandatory for peerreviewed manuscripts, books, book chapters, working papers, technical reports and EDTs, while encourages its members to deposit research datasets as well. Technical University's of Crete policy, in effect since 2014, encourages the deposit of peer-reviewed articles, books, technical reports, and research datasets.

Public research funding agencies, on the other hand, have not been very active in implementing OA policies. A first step towards this direction is the requirement placed upon the researchers participating in the "Diversity, inequalities and social inclusion" Programme to submit publications to an open access repository, or, alternative, publish in OA journals.

Developments at policy level may be slow, but OA infrastructure has been steadily expanding and improving in recent years, mainly thanks to the funding through Structural Funds. The National Documentation Centre (EKT) maintains a scientific aggregator (https://openarchives.gr), which

Table 3 .

 3 Institutional repositories in Greek HEIs

Table 4 .

 4 OA journalsOpen access infrastructure in Greece : current status, challenges and perspec... An important initiative in OA publishing has been the development of EKT's ePublishing services, which aim at providing open access to digital scholarly content, as well as a range of integrated publishing services to the academic community. ePublishing has been developed with open access interoperable technology and it currently hosts 33 academic journals, 26 eBooks and 18 eProceedings, by 36 accredited Greek publishers, mainly societies and academic institutions. Besides the organisation, documentation and dissemination of metadata and content of scholarly journals, ePublishing services also include training and consulting on OA publishing, including intellectual property issues, the standardisation of the editorial process, and the interoperability of systems.

	Subject	Academic Research Society Commercial Other Total
	Humanities/Arts 19	7	9	1	1	37
	Medical Sciences 5	2	17	3	2	29
	Science	5	2	3	1	1	12
	Social Sciences	15	4	12		2	33
	Technology	4			1		5
							ELPUB 2018

Table 5 .

 5 Top rating Greek universities

	University		Faculties Departments	Teaching staff	Scopus Publications (2008-2017)
	1.National University of Athens (UoA)	8	33	1764	37550
	2.Aristotle Thessaloniki (AUTH) University	of	11	41	1944	30213
	3.University of Patras (UPatras) 5	24	705	16432
	4.University of Crete (UoC)		5	16	485	11585
	5.National Technical University (NTUA)	9	9	514	17619

Table 6 .

 6 Publication types

		OA	Non OA	Total
	Publication Type
		N	% N		% N
	Book	46	8.2 524	91.8 570
	Book chapter	668	10.7 5559 89.3 6227
	Journal article	30026 32.5 62371 67.5 92397
	Monograph	6	6.7 84	93.3 90
	Proceedings	1123 11.3 8822 88.7 9945
	Other	36	28.1 92	71.9 128
	Total	31905 29.2 77452 70.8 109358

Table 7 .

 7 OA host

		Publisher Repository Total
	Publication Type
		N	% N	%	N
	Book	32	69.6 14	30.4 46
	Book chapter	79	11.8 589 88.2 668
	Journal article	22348 74.4 7678 26.6 30026
	Monograph	0	0	6	100 6
	Proceedings	114	10.2 1009 89.8 31905
	Other	30	83.3 6	16.7 128
	Total	22603 70.8 9302 29.2 31905

  • Establishing user-friendly self-archiving workflows in Greek IRs. Use of DOIs and the CrossRef API could facilitate the processes and be considered. Archiving Greek publications in IRs is a challenge due to lack of DOIs. Therefore, publications in Greek conferences and journals could be archived by librarians and though a self-archiving process • Integrating tools that may support sharing (e.g. share buttons) or may give an idea regarding impact (e.g. citations from Scopus or PubMed, alternative metrics such as number of views/downloads, or tweets from the Altmetric.com API)• Depositing of citation data by Greek OA journals as open structured separable data in open citations projects (e.g., https://i4oc.org/, or http://opencitations.net/)• Promoting the interoperability of IRs with other OA infrastructure at national and international level.

ABSTRACTS

Open access (OA) is a global movement to make research results widely available by removing price and permission barriers. OA infrastructure is necessary for implementing open access and open science in any country. The aim of the present paper is twofold : (i) to give a description of the Greek OA infrastructure with emphasis on academic repositories and OA journals, and (ii) to examined the OA availability of publications authored by Greek researchers and published in international journals. Results indicated that Open access infrastructures in Greece have been steadily improving over the past years, with 28 out of 36 HEIs running their own IR and 116 OA journals being published. The OA availability of the literature produced by Greek researchers is similar to that found in other studies and falls within the range that has been reported for European countries. Although numbers seem rather satisfactory, there are a number of challenges that have to be addressed at both the infrastructural and the policy level, the most important being the implementation of national open policies and funders mandates.

ELEFTHERIA KOSEOGLOU

Aristotle University of Thessaloniki, Greece

SOFIA ZAPOUNIDOU

Aristotle University of Thessaloniki, Greece

NIKOLAOS TSIGILIS

Aristotle University of Thessaloniki, Greece

Open access infrastructure in Greece : current status, challenges and perspec... ELPUB 2018


Patrick A Dehornoy
email: patrick.dehornoy@unicaen.fr

Cancellativity Criterion

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

Keywords: 1991 Mathematics Subject Classification. 20M05, 20M12, 20F36 semigroup presentation, van Kampen diagram, rewrite system, cancellativity, word problem, Garside monoid, group of fractions, monoid embeddability, Artin-Tits groups

We establish a new, fairly general cancellativity criterion for a presented monoid that properly extends the previously known related criteria. It is based on a new version of the word transformation called factor reversing, and its specificity is to avoid any restriction on the number of relations in the presentation. As an application, we deduce the cancellativity of some natural extension of Artin's braid monoid in which crossings are colored.

Establishing that a presented monoid (or semigroup) is cancellative is in general a nontrivial task, for which not so many methods are known [12, sec. 5.3]. If a distinguished expression ("normal form") has been identified for each element of the monoid, and if, for each element a of the considered monoid M and every generator s of the considered presentation, the normal form of a can be retrieved from that of sa and s, then one can indeed conclude that sa = sb implies a = b. But, when no normal form is known, no generic method is available. Adjan's criterion based on the left graph [1, 14] is useful, but, by definition, it applies only to presentations with (very) few defining relations. Ultimately relying on Garside's analysis of the braid monoids B + + + n [11], the so-called reversing method [5, 8] provides a simple criterion, which proved to be useful for many concrete presentations, typically those of all Artin-Tits monoids. However, an intrinsic limitation of the method is that it only applies to monoid presentations (S, R) that contain a limited number of relations, namely those such that, for all s, t in S, there exists at most one relation of the form s... = t... in R ("right-complemented" presentations). The aim of this paper is to extend the previous criterion by developing a new approach that requires no limitation on the number of defining relations. The result we prove takes the following form:

Proposition. Assume that (S, R) is a monoid presentation such that (i) there exists an ≡ R -invariant map λ from S * to ordinals satisfying λ(sw) > λ(w) for all s in S and w in S * , and

(ii) for every s in S, for every relation w = w ′ in R, and for every (S, R)-grid from (s, w), there exists an equivalent grid from (s, w ′ ), and vice versa, and

(iii) there is no relation sw = sw ′ in R with w, w ′ distinct. Then the monoid associated with (S, R) admits left cancellation.

In the above statement, ≡ R refers to the congruence on the free monoid S * generated by the relations of R, and an (S, R)-grid is a certain type of rectangular van Kampen diagram specified in Definition 1.1 below. Note that Condition (i) in the above statement is trivial when each relation in R consists of two words with the same length ("homogeneous presentation"), since, in that case, λ(w) can be taken to be the length of w.

As an application, we deduce:

Proposition. For every n and every nonempty set C, the monoid The monoid B + + + n,C is an extension of Artin's monoid B + + + n of positive n-strand braids, and it is a typical example of a monoid that is inaccessible to all previously known methods. We shall see that the elements of B + + + n,C admit a natural interpretation in terms of braids with C-colored crossings, and both B + + + n,C and its universal group might be structures of independent interest. They are in particular directly reminiscent of (but not identical to) the monoids investigated in [START_REF] Berenstein | Monomial braidings[END_REF].

B + + + n,C := σ

Using reversing grids

As in [START_REF] Dehornoy | The subword reversing method[END_REF], our cancellativity criterion is based on some word transformation called factor (or subword) reversing, and on a criterion for establishing that the latter is complete, meaning that it detects every word equivalence with respect to the presentation. The specificity of the current paper is to extend the framework so as to avoid any restriction on the number of relations in the presentation. This is done by introducing the new notion of a reversing grid (Section 1.1), then establishing a convenient completeness criterion (Section 1.2), and finally deducing the expected cancellativity criterion and various other consequences (Section 1.3).

1.1. The notion of a reversing grid. If S is a nonempty set, we denote by S * the free monoid of all words in S, and use ε for the empty word. A monoid presentation is a pair (S, R), where R is a list of (unordered) pairs of words of S * ; as usual, we write relations with an equality sign, thus writing w = w ′ for {w, w ′ }. We then denote by S | R + the monoid presented by (S, R), that is, the monoid S * /≡ R , where ≡ R is the congruence on S * generated by R. To avoid any confusion due to using = in relations of the presentation, we shall use ≡ for word equality.

A relation of the form w = ε with w nonempty will be called an ε-relation. In the sequel, we shall only address monoid presentations (S, R) that contain no εrelation. In this case, the only invertible element of the monoid S | R + is the unit 1, represented by the empty word. Note that every such presentation also defines a semigroup and, in fact, most statements of this paper can be adapted to a semigroup context. However, the overall philosophy here is really that of monoids, and it seems more natural to stick to a monoid context.

Our main subject of investigation is a certain binary relation (or rewrite system) on S × S associated with (S, R) as follows.

Definition 1.1. If (S, R) is a monoid presentation, an (S, R)-grid is a rectangular diagram consisting of finitely many matching S ∪ {ε}-labeled pieces of the types t s t 1 t q s 1 s p with s, t, s 1 , ..., s p , t 1 , ..., t q in S and

st 1 ••• t q = ts 1 ••• s p a relation of R, s s ε ε , ε s ε s , t ε t ε , ε ε ε ε with s, t in S.
For u, v, u 1 , v 1 in S * , we say that an (S, R)-grid Γ goes from (u, v) to (u 1 , v 1 ) or, equivalently, that (u, v) is the source of Γ and that (u 1 , v 1 ) is its target, if the labels of the left and top edges of Γ form the words u and v, respectively, whereas the labels of the right and bottom edges form the words u 1 and v 1 . If there exists an

(S, R)-grid from (u, v) to (u 1 , v 1 ), we say that (u, v) is right R-reversible to (u 1 , v 1 ), written (u, v) R (u 1 , v 1 ) or, in a diagrammatic way, v v 1 u u 1 R
; we then often skip R if there is no ambiguity.

In the above definition, a grid consists of (finitely many) rectangular pieces (or tiles) whose edges are labeled by one or several letters of the current alphabet S or by ε, and two adjacent pieces are called matching if the letters occurring on the common part of their edges coincide (but we do not assume that all edges involve the same number of letters: by definition, there is only one letter on the top and the left edges, whereas there can be more on the bottom and right edges, depending on the length of the words involved in the relations of the presentation). Let us immediately observe that, by definition, a grid that contains more than one elementary piece can be split into the union of several grids, see for instance Lemma 1.5 below.

B + + + n := σ 1 , ..., σ n-1 σ i σ j = σ j σ i for |i -j| 2 σ i σ j σ i = σ j σ i σ j for |i -j| = 1 + .
For n 4, a typical grid for (1.1) is

(1.2) σ 2 σ 3 σ 2 σ 3 σ 2 σ 1 ε σ 1 σ 2 σ 1 σ 3 σ 2 ε σ 1 σ 1 σ 1 σ 2 σ 1 σ 2 σ 3 ε σ 3 σ 1 σ 2 ε σ 3
It contains eight squares, of which five correspond to relations of (1.1), and it goes from (σ 1 , σ 2 σ 3 σ 2 ) to (σ 1 σ 2 σ 3 , σ 2 σ 1 σ 3 σ 2 σ 1 ), witnessing the right reversing relation

(σ 1 , σ 2 σ 3 σ 2 ) (σ 1 σ 2 σ 3 , σ 2 σ 1 σ 3 σ 2 σ 1 ), alias σ 2 σ 3 σ 2 σ 2 σ 1 σ 3 σ 2 σ 1 σ 1 σ 1 σ 2 σ 3 .
In all five types of elementary pieces considered in Definition 1.1, the labels of the two possible paths from the top-left vertex to the bottom-right vertex form words that are ≡ R -equivalent, i.e., represent the same element in the monoid S | R + . An easy induction on the number of elementary pieces implies: Lemma 1.3. For every monoid presentation (S, R), and for all words u, v, u 1 , v 1 in S * , the relation (u, v) R (u 1 , v 1 ) implies uv 1 ≡ R vu 1 . In particular,

(1.3) (u, v) R (ε, ε) implies u ≡ R v.
In other words, a reversing grid from (u, v) to (u 1 , v 1 ) is a special type of van Kampen diagram witnessing the ≡ R -equivalence of the words uv 1 and vu 1 .

Remark 1.4. In the articles [START_REF] Dehornoy | Groups with a complemented presentation[END_REF][START_REF] Dehornoy | On completeness of word reversing[END_REF][START_REF] Dehornoy | Complete positive group presentations[END_REF][START_REF] Dehornoy | On word reversing in braid groups[END_REF], reversing was described in terms of signed S-words, defined to be words in a symmetrized alphabet S ∪ S with S consisting of one copy s for each letter s of S. If w, w ′ are signed S-words, one declares that w R w ′ holds if one can go from w to w ′ by a finite sequence of transformations, each of which consists either in deleting some length two factor ss, or in replacing some length two factor st with

t 1 ••• t q s p ••• s 1 , where st 1 ••• t q = ts 1 ••• s p is a relation of R.
The connection with our current approach is easy: writing w for the word obtained from w by exchanging s and s everywhere and reversing the order of letters, the relation (u, v) R (u 1 , v 1 ) of Definition 1.1 is equivalent to uv R v 1 u 1 in the sense of signed word reversing. The advantage of the current description is to make it more visible that reversing only involves positive words and the presented monoid, without connection with inverting the elements and moving to a group context. In any case, the reversing grid is the fundamental object, and it seems more natural to begin with it.

One of the advantages of the current grid-based approach is to make the following technical result almost straightforward: Lemma 1.5. For every monoid presentation (S, R), and for all u, v ′ , v ′′ , u 1 , v 1 in S * , the following are equivalent:

(i) The relation (u, v ′ v ′′ ) R (u 1 , v 1 ) holds; (ii) There exist u ′ , v ′ 1 , v ′′ 1 in S * satisfying (u, v ′ ) R (u ′ , v ′ 1 ), (u ′ , v ′′ ) R (u 1 , v ′′ 1 ), and v 1 ≡ v ′ 1 v ′′ 1 . Proof. Assume that Γ is an (S, R)-grid from (u, v ′ v ′′ ) to (u 1 , v 1 )
. By definition, Γ is a juxtaposition of elementary diagrams as in Definition 1.1. Grouping the diagrams that lie below v ′ on the one hand, and below v ′′ on the other hand, splits Γ into two grids Γ ′ and Γ ′′ . By construction, the input of Γ ′ is (u, v ′ ); call its output (u ′ , v ′ 1 ). Then, by construction, the input of Γ ′ is (u ′ , v ′′ ), and its output has the form (u 1 , v ′′ 1 ), with

v 1 ≡ v ′ 1 v ′′ 1 . So (i) implies (ii). v ′ v ′′ v ′ 1 v ′′ 1 u u ′ u 1 v 1
Conversely, concatenating a grid from (u, v ′ ) to (u ′ , v ′ 1 ) and a grid from (u

′ , v ′′ ) to (u 1 , v ′′ 1 ) provides a grid from (u, v ′ v ′′ ) to (v ′ 1 v ′′ 1 , u 1 )
, so (ii) implies (i). 1.2. Completeness of reversing. A reversing grid is a van Kampen diagram of a special type, namely one in which at most two edges (one horizontal, one vertical) start from each node. If there exists an (S, R)-grid from (u, v) to (ε, ε), then, by Lemma 1.3, the words u and v must be ≡ R -equivalent. Conversely, if u and v are ≡ R -equivalent words, there must exist a van Kampen diagram connecting u and v but, in general, there is no reason why the latter could be chosen with the special form of a reversing grid: for instance, Fact 2.10 below will provide an example of an equivalence that cannot be recognised by a reversing grid. We now consider the case when using reversing grids is always possible. Definition 1.6. We say that right reversing is complete for a monoid presentation (S, R) if the converse of (1.3) also holds, that is, if, for all u, v in S * ,

(1.4) (u, v) R (ε, ε) is equivalent to u ≡ R v.
This definition is theoretical, and our aim will be to establish a practical criterion characterizing completeness of reversing. Two such criteria have already appeared. A first criterion is described in [START_REF] Dehornoy | Complete positive group presentations[END_REF], in terms of what is called the cube condition: in principle, this criterion works for arbitrary presentations but, in practice, it can be used only for complemented presentations, namely presentations with at most one relation s... = t... for each pair of generators (s, t). Another criterion is described in [START_REF] Dehornoy | On completeness of word reversing[END_REF], but, even in theory, it does not apply to presentations that are not complemented. What we do below is establish a new completeness criterion that extends the one of [START_REF] Dehornoy | On completeness of word reversing[END_REF] and works for every presentation, complemented or not. The main point is that this new criterion, contrary to the cube condition, remains tractable in the non-complemented case, i.e., without any restriction on the number of relations in the considered presentation.

It follows from the definition of a reversing grid that reversing can be complete only for monoid presentations with no ε-relation: indeed, by definition, (w, ε) (ε, ε) is impossible for w nonempty. So we shall hereafter restrict to monoid presentations with no ε-relation. The crucial notion is then the notion of equivalent grids. Definition 1.7. If (S, R) is a monoid presentation with no ε-relation, two (S, R)grids Γ, Γ ′ are said to be equivalent if the labels of the four edges of Γ form words that are ≡ R -equivalent to their counterparts in Γ ′ . We shall start from the following observation.

Lemma 1.8. If (S, R) is a monoid presentation with no ε-relation, a sufficient condition for right reversing to be complete for (S, R) is that, for all u, v in S * , (♦ * )

For every grid from (u, v), and for all u ′ , v ′ satisfying u ′ ≡ R u and v ′ ≡ R v, there is an equivalent grid from (u ′ , v ′ ).

Proof. Assume that (♦ * ) holds for all u, v in S * , and let u, u ′ be ≡ R -equivalent words. A trivial induction on the length of u shows that there exists a grid Γ from (u, u) to (ε, ε), as shown on the right. Applying (♦ * ) to Γ and to the equivalences u ≡ R u and u ≡ R u ′ , we conclude that there exists a grid

Γ ′ from (u, u ′ ) that is equivalent to Γ. Let (u ′ 1 , v ′ 1 ) be the output of Γ ′ . Then, by assumption, we have u ′ 1 ≡ R ε and v ′ 1 ≡ R ε. Because R contains no ε-relation, u ′ 1 ≡ R ε implies that u ′ 1 is empty, and v ′ 1 ≡ R ε implies that v ′ 1 is empty. s 1 s ℓ ε s ℓ ε s ℓ ε ε s 1 s ℓ ε s ℓ ε s ℓ ε ε u u
So Γ ′ witnesses that (u, u ′ ) right-reverses to (ε, ε) and, therefore, right reversing is complete for (S, R).

As it stands, Lemma 1.8 does not provide a tractable criterion, because it involves arbitrary pairs of ≡ R -equivalent words in S * . We show now that, under convenient finiteness assumptions ("noetherianity"), the most elementary instances of the condition are sufficient to deduce the full condition.

If M is a monoid and g, h belong to M , one says that g properly right-divides h, written g ≺ R h or h ≻ R g, if h = h ′ g holds for some non-invertible element h ′ of M (proper left-division ≺ L would be defined symmetrically with g on the left). Definition 1.9. A monoid M is called right noetherian if there is no infinite descending sequence with respect to proper right-divisibility relation in M , that is, every sequence

g 0 ≻ R g 1 ≻ R ... in M is finite 1 .
In a general monoid, the notions of left invertible, right invertible, and invertible elements need not coincide. That difficulty vanishes in a right noetherian monoid.

Lemma 1.10. Assume that M is a right noetherian monoid.

(i) An element of M is left invertible if, and only if, it is right invertible if, and only if, it is invertible.

(ii) The product of two non-invertible elements of M is non-invertible.

Proof. (i) First, we recall that, if an element admits a left and a right inverse, then the latter are equal, for

f g = gf ′ = 1 implies f = f (gf ′ ) = (f g)f ′ = f ′ .
Now, assume that g admits a left inverse, say f g = 1. Two cases are possible. If f is invertible, then so is g, since hf = 1 implies h = hf g = g, whence gf = 1. Otherwise, g k = f gg k gives g k ≻ R g k+1 for every k 0, leading to the infinite descending sequence 1 ≻ R g ≻ R g 2 ≻ R ..., which contradicts right noetherianity. Hence left invertibility implies invertibility in M .

Next, assume that g admits a right inverse, say gh = 1. Then h admits a left inverse and, by the above result, h must be invertible. This in turn implies that h is also a left inverse of g, so g is invertible, and right invertibility implies invertibility.

(ii) Assume that g and h are non-invertible elements of M , and gh is invertible. Then g is right invertible and h is left invertible, so, by (i), both are invertible, which implies that their product is invertible, a contradiction.

Recognizing whether a monoid is noetherian is in general difficult. In practice, we can use the following criterion.

Lemma 1.11. For every monoid M , the following are equivalent:

(i) The monoid M is right noetherian.

(ii) There exists a map λ from M to ordinals such that, for all g, g ′ in M ,

(1.5) g ≻ R g ′ implies λ(g) > λ(g ′ ).
(iii) There exists a map λ from M to ordinals satisfying, for all g, h in M ,

(1.6) λ(gh) λ(h) + λ(g), and λ(g) > 0 whenever g is non-invertible.

Proof. The equivalence of (i) and (ii) is standard: for ≻ R to admit no infinite descending sequence means that the relation ≻ R is well-founded, and it is well known that this amounts to the existence of a map to the ordinals that decreases along ≻ R . Next, (iii) implies (ii): indeed, assuming g = hg ′ with h non-invertible and applying (1.6), we obtain λ(g) λ(g

′ ) + λ(h) > λ(g ′ ).
Finally, assume (i), whence (ii). As above, the relation ≻ R is well founded, so, by standard arguments, there exists a map λ : M → Ord inductively defined by

(1.7) λ(g) := 0 if g is invertible, sup{λ(f ) + 1 | f ≺ R g} otherwise.
1 This notion of noetherianity, which is reminiscent of that of rings and algebras, is not the only one used for semigroups: right noetherianity may also refer to a monoid in which every right congruence is finitely generated, or to a monoid in which every right ideal is finitely generated.

We claim that this particular function λ, which satisfies (1.5) by construction, also satisfies (1.6). First, we observe that, if g is not invertible, then g ≻ R 1 is true, so we must have λ(g) > λ(1) = 0. So the second assertion in (1.6) is true. Next, we observe that, if g is invertible, then λ(gh) λ(h) holds. Indeed, the inequality is trivial for λ(h) = 0, and, otherwise, the sets {f | f ≺ R h} and {f | f ≺ R gh} coincide, and we deduce

λ(gh) = sup{λ(f ) + 1 | f ≺ R gh} = sup{λ(f ) + 1 | f ≺ R h} = λ(h).
We prove now using induction on λ(g) that λ(gh) λ(h) + λ(g) holds for every h in M . Assume first λ(g) = 0. Then g must be invertible, and we established above the equality λ(gh) = λ(h) = λ(h) + λ(g), as expected. Assume now λ(g) > 0. Then g is not invertible and, by definition, we have λ(g) = sup{λ(f ) + 1 | f ≺ R g}. Let h be an arbitrary element of M . By Lemma 1.11, gh is not invertible, and we obtain

λ(gh) = sup{λ(f ) + 1 | f ≺ R gh} by definition sup{λ(f h) + 1 | f ≺ R g} because f ≺ R g implies f h ≺ R gh sup{λ(h) + λ(f ) + 1 | f ≺ R g} by induction hypothesis = λ(h) + sup{λ(f ) + 1 | f ≺ R g} by monotonicity of ordinal addition = λ(h) + λ(g) by definition.
Thus the first inequality in (1.6) is established, and (i) implies (iii).

Translating the previous result at the level of presentations, we can state:

Lemma 1.12. If (S, R) is a monoid presentation, the monoid S | R + is right noetherian whenever the following equivalent conditions hold:

there exists an ≡ R -invariant map λ from S * to the ordinals satisfying λ(sw) > λ(w) for all s in S and w in S * ; (1.8) there exists an ≡ R -invariant map λ from S * to the ordinals satisfying λ(uv) λ(v) + λ(u) for all u, v in S * , and λ(s) > 0 for s in S.

(1.9) Thus, (1.8) provides a sufficient condition for right noetherianity-which is also necessary if no element of S is invertible in S | R + -and, when it is satisfied, one is assured that the stronger condition (1.9) is satisfied (possibly by another map λ ′ ). As already noted, in the case of a homogeneous presentation, i.e., when all relations have the form w = w ′ with w, w ′ of the same length, defining λ(w) to be the length of w provides a map λ witnessing (1.9). Note that (1.8) can hold only if there is no ε-relation so, when considering below monoid presentations that satisfy (1.8), there is no need to explicitly require that they contain no ε-relation.

The main technical result we shall establish is the following criterion for the completeness of reversing: Lemma 1.13. A monoid presentation (S, R) satisfying (1.8) satisfies (♦ * ) if, and only if, for every element s in S and every relation w = w ′ in R, (♦) for every grid from (s, w), there is an equivalent grid from (s, w ′ ), and vice versa.

The proof will use an induction on an ordinal parameter called the diagonal of a grid: Definition 1.14. If (S, R) is a monoid presentation and λ is a map witnessing (1.9), then, if Γ is an (S, R)-grid from (u, v) to (u 1 , v 1 ), the diagonal of Γ is the value of λ(uv 1 ).

Note that, with the above notation and by Lemma 1.3, the diagonal of Γ is also equal to λ(vu 1 ).

On the other hand, for w, w ′ in S * , we write dist R (w, w ′ ) for the combinatorial distance between w and w ′ with respect to R, namely the minimal length of an R-derivation from w to w ′ if w and w ′ are ≡ R -equivalent, and ∞ otherwise.

Proof of Lemma 1.13. One implication is trivial: (♦) for s and w = w ′ follows from applying (♦ * ) to the words s and w with the equivalences s ≡ R s and w ′ ≡ R w.

The point is to establish the converse implication. This will be done using two nested inductions. First, we fix a map λ from S * to ordinals satisfying (1.9), which is possible by Lemma 1.12. By the properties of ordinal addition, we always have (1.10) λ(u) λ(uv), λ(v) λ(uv), and λ(v) < λ(uv) for u nonempty.

Then, for α an ordinal, we introduce the special case of Condition (♦ * ) corresponding to grids whose diagonal is at most α:

(♦ * α )
For every grid with diagonal α from (u, v), and for all u ′ , v ′ satisfying u ′ ≡ R u and v ′ ≡ R v, there is an equivalent grid from (u ′ , v ′ ).

Finally, for d a natural number, we consider the special case of Condition (♦ * α ) corresponding to combinatorial distances between the sources of the old and new grids bounded by d:

(♦ * α,d )
For every grid with diagonal α from (u, v), and for all u ′ , v ′ satisfying dist R (u, u ′ ) + dist R (v, v ′ ) d, there is an equivalent grid from (u ′ , v ′ ).

It should be clear that (♦ * ) for two words u, v is equivalent to the conjunction of all (♦ * α,d ) for u, v. Using an induction on α and, for a given α, on d, we shall establish that, if (♦) is true for every s and every relation w = w ′ of R, then (♦ * α,d ) is true for all u, v.

Assume first α = 0. Assume that Γ is a grid with zero diagonal from (u, v) to (u 1 , v 1 ), and u ′ ≡ R u and v ′ ≡ R v hold. By construction, λ(w) = 0 implies that w is empty, so λ(uv 1 ) = λ(vu 1 ) = 0 requires that u, v, u 1 , and v 1 all are empty. Next, the assumption u ′ ≡ R ε implies that u ′ is empty, and v ′ ≡ R v implies that v ′ is empty as well. Then choosing Γ ′ := Γ provides the expected condition. So (♦ * 0 ) is true for all u, v.

Assume now α > 0 and d = 0. Assume that Γ is a grid with diagonal α from (u, v) to (u 1 , v 1 ), and dist R (u, u ′ ) + dist R (v, v ′ ) = 0 holds. By definition, we have u ′ ≡ u and v ′ ≡ v. Then choosing Γ ′ := Γ provides the expected condition. So (♦ * α,0 ) is true for all u, v and for every α. Assume now α > 0 and d = 1. Assume that Γ is a grid with diagonal α from (u, v) to (u 1 , v 1 ), and dist R (u, u ′ ) + dist R (v, v ′ ) = 1 holds. Up to a symmetry, we may assume u ′ ≡ u and dist R (v ′ , v) = 1. By definition, the latter relation means that there exists a relation w = w ′ in R and two words v 0 , v 2 satisfying v ≡ v 0 wv 2 and v ′ ≡ v 0 w ′ v 2 . As v is the product v 0 wv 2 , repeated applications of Lemma 1.5 show that the assumption (u, v) R (u 1 , v 1 ) implies the existence of u 0 , u 2 and v 3 , v 4 , and

v 5 satisfying v 1 ≡ v 3 v 4 v 5 and (u, v 0 ) R (u 0 , v 3 ), (u 0 , w) R (u 2 , v 4 ), and (u 2 , v 2 ) R (u 1 , v 5 ),
corresponding to a decomposition of the grid Γ into the union of three grids

v 0 w v 2 v 3 v 4 v 5 v 1 v u u 0 u 2 u 1
Assume first that the word u 0 is empty. Then, necessarily, u 1 and u 2 are empty, and we have v 4 ≡ w and v 5 ≡ v 2 . Then the situation is as the left diagram below

v 0 w v 2 v 3 w v 2 v 1 v u ε ε ε v 0 w ′ v 2 v 3 w ′ v 2 v ′ 1 v ′ u ε ε ε
and the right diagram shows that (♦ * α,1 ) is satisfied with u ′ 1 empty and v ′ 1 ≡ v 3 w ′ v 2 . Assume now that u 0 is not empty. Then we write u 0 ≡ su 3 with s in S. Splitting the grid again, we obtain the existence of words u 4 , ..., u 7 and v 6 , v 7 such that the situation is as in the left diagram below

v 0 w v 2 v 6 v 7 v 3 v 4 v 5 v 1 v u s u 3 u 4 u 5 u 6 u 7 u 1 v 0 w ′ v 2 v ′ 6 v ′ 7 v 3 v ′ 4 v ′ 5 v ′ 1 v ′ u s u 3 u ′ 4 u ′ 5 u ′ 6 u ′ 7 u ′ 1
We shall now establish the existence of words u ′ 3 , ..., u ′ 7 and v ′ 4 , ..., v ′ 7 such that the right diagram above is a legitimate (S, R)-grid, with u ′ i ≡ R u i and v ′ j ≡ R v j for all i and j.

We begin with the top median square. By assumption, we have (s, w)

R (u 4 , v 6 ) and w = w ′ ∈ R. By (♦), there exist u ′ 4 and v ′ 6 satisfying u ′ 4 ≡ R u 4 , v ′ 6 ≡ R v 6 and (s, w ′ ) R (u ′ 4 , v ′ 6 )
. Consider now the bottom median square. Then u 3 ≡ R u 3 is trivial, whereas v ′ 6 ≡ R v 6 and (u 3 , v 6 ) R (u 5 , v 4 ) hold by construction. Moreover, (1.10) implies

λ(u 3 v 4 ) < λ(su 3 v 4 ) λ(v 0 su 3 v 4 ) λ(v 0 su 3 v 4 v 5 ) = λ(uv 1 ) α,
whence β := λ(u 3 v 4 ) < α. By induction hypothesis, (♦ * β ) is true for u 3 and v 6 , and we deduce the existence of u ′ 5 and v ′ 4 satisfying

u ′ 5 ≡ R u 5 , v ′ 4 ≡ R v 4 and (u 3 , v ′ 6 ) R (u ′ 5 , v ′ 4 ).
(ii) By Lemma 1.8, (i), that is, (♦ * ) for all u, v, implies that reversing is complete for (S, R), which, by definition, implies the equivalence of (ii).

Let us turn to left cancellativity. Then completeness of right reversing is useful, as it shows that, if there is no obvious counter-example to left cancellativity, then there is no hidden counter-example either: Lemma 1.16. If right reversing is complete for the presentation (S, R) and R contains no relation of the form su = sv with s in S and u, v distinct, then the monoid S | R + admits left cancellation.

Proof. It is enough to prove that, for all words u, v in S * , every relation of the form su ≡ R sv with s in S implies u ≡ R v. So assume su ≡ R sv. By completeness of right reversing, we deduce (su, sv) R (ε, ε). By Lemma 1.5, a grid witnessing (su, sv) R (ε, ε) decomposes into four grids, as shown on the right. The assumption about the presentation requires that u 1 and v 1 are empty, which in turn implies u 2 ≡ u and v 2 ≡ v.

s v v 1 v 2 ε ε s u u 1 u 2 ε ε
Then the bottom right square witnesses (u, v) R (ε, ε), which, by Lemma 1.3, implies u ≡ R v.

Putting things together, we deduce the practical cancellativity criterion that is the main result of this paper, as stated in the preamble of the paper: Proposition 1.17. Assume that a monoid presentation (S, R) satisfies (1.8) and (♦) for every s in S and every relation w = w ′ in R. Then a sufficient condition for the monoid S | R + to be left cancellative is that there is no relation sw = sw ′ in R with w, w ′ distinct.

We recall once again that Condition (1.8) automatically holds when the considered presentation (S, R) is homogeneous.

Of course, a symmetric criterion exists for right cancellativity: right noetherianity is to be replaced with left noetherianity, meaning the non-existence of an infinite descending sequence with respect to proper left divisibility, and right reversing grids are to be replaced with their left counterparts, in which one starts from the bottom and right edges and uses the relations to build a rectangular diagram in which the output corresponds to the left and top edges. Note that a right reversing grid is not a left reversing grid, in particular because "cancellation squares" are not the same: Remark 1.18. Contrary to Adjan's cancellativity criterion of [START_REF] Adyan | On the embeddability of monoids[END_REF][START_REF] Remmers | On the geometry of semigroup presentations[END_REF], the criterion of Proposition 1.17 does not guarantee that the considered monoid S | R + embeds in its universal group, that is, in the group defined, as a group, by the presentation (S, R), sometimes also called the enveloping group of S | R + . For instance, consider the monoid M with presentation

(1.11) a, b, c, d, a ′ , b ′ , c ′ , d ′ | ac = bd, ac ′ = bd ′ , a ′ c = b ′ d + .
The monoid M fails to satisfy the first Malcev condition [4, Chapter 12, page 310] and, therefore, it does not embed in its universal group. However, the presentation of (1.11) is eligible for the cancellativity criterion of Proposition 1.17-but not for Adjan's criterion, since (a, b) is a cycle in the left graph.

We conclude with one more application of completeness of right reversing, now in terms of common (right) multiples.

1 , v 1 satisfying (u, v) R (u 1 , v 1 ).
Proof. Assume that there exists a grid from (u, v), say (u, v) R (u 1 , v 1 ). By Lemma 1.3, this implies uv 1 ≡ R vu 1 , which shows that the element of S | R + represented by uv 1 and vu 1 is a common right multiple of a and b. Conversely, assume that c is a common right multiple of a and b: this means that there exist words u ′ , v ′ such that c is represented by uv ′ and vu ′ , which therefore satisfy uv ′ ≡ R vu ′ . Under the assumptions, right reversing is complete for (S, R), so (uv ′ , vu ′ ) R (ε, ε) holds. Splitting a reversing grid in four pieces as shown on the right, we see that there exists a grid

v u ′ v 1 v 2 ε ε u v ′ u 1 u 2 ε ε from (u, v)
, and that the equivalences Proof. The assumption that (S, R) is right complemented implies that an (S, R)grid from (u, v) is unique when it exists. Thus, Proposition 1.19 says that every common right multiple of a and b is a right multiple of the element represented by uv 1 . So the latter element, when it exists, is a right lcm of a and b.

u ′ ≡ R u 1 v 2 , v 2 ≡ R u 2 ,
Specializing even more, we finally obtain:

Corollary 1.21. Assume that a monoid presentation (S, R) satisfies the assumptions of Proposition 1.19 and, moreover, for all s, t in S, there exist s ′ , t ′ in S such that st ′ = ts ′ is a relation of R. Then any two elements of the monoid S | R + admit a right lcm.

Proof. The presentation is eligible for Corollary 1.20, so we know that any two elements with a common right multiple admit a right lcm. The additional assumption about (S, R) guarantees that, for all words u, v in S * , there exists one (S, R)-grid from (u, v): indeed, obstructions arise when a relation s... = t... is missing, and when the process never terminates because smaller and smaller arrows appear without end. The assumption that there always exist a relation s... = t... discards the first obstruction; the assumption that the relations involve words of length 2 discards the second one. Thus, any two elements of the monoid S | R + admit a common right multiple, hence a right lcm.

Remark 1.22. The cancellativity criterion of Proposition 1.17 subsumes the one established in [START_REF] Dehornoy | On completeness of word reversing[END_REF] in the case of a right complemented presentation. In such a case, there exists at most one (S, R)-grid admitting a given source (u, v), and, therefore, the output words can be seen as functions of u and v. Then, the cancellativity criterion can be stated as a compatibility of the functions in question, called "complement", with the equivalence relation ≡ R . In our general case, the scheme of the proof remains the same, but one needs to find a different formalism, which makes the extension nontrivial: indeed, whenever the considered presentation contains at least two relations with the same initial letters, there may exist more than one grid with a given source, and complement functions just make no sense. In [START_REF] Dehornoy | On completeness of word reversing[END_REF], in addition to qualitative aspects, some quantitative results are established, and they can be extended to our current framework. Say that a monoid presentation (S, R) has defect d if, for every s in S, every relation w = w ′ in R, and every (S, R)-grid Γ from (s, w), there exists an equivalent (S, R)-grid Γ ′ from (s, w ′ ) such that the sum of the distances between the output words of Γ and Γ ′ is bounded above by d, and d is minimal with that property. Then the inductive proof of Proposition 1.13 can be adapted to show that, if (S, R) has finite defect d and Γ is a grid from (u, v), then, for all u ′ ≡ R u and v ′ ≡ R v, there exists an equivalent grid Γ ′ from (u ′ , v ′ ) such that the distance between the outputs of Γ and Γ ′ is bounded by an explicit function of the distance between their inputs, actually a double exponential of base d. The reader is referred to [START_REF] Dehornoy | On completeness of word reversing[END_REF] to fill in the details.

Applications to variants of braid monoids

As an application of the results of Section 1, we now establish that the monoids of colored braids, which are extensions of the classical Artin braid monoids, admit cancellation.

2.1. Braids with colored crossings. We mentioned in Example 1.2 that, for n 1, the standard n-strand monoid B + + + n is the monoid presented by (1.1). We recall, for instance from [START_REF] Birman | Braids, Links, and Mapping Class Groups[END_REF], that, under interpreting σ i as the elementary crossing that exchanges the strands at positions i and i + 1 as in

σ i : 1 2 • • • i-1 i i+1 i+2 • • • n the monoid B + + +
n is the monoid of isotopy classes of positive n-strand braid diagrams. We now consider an extension of the monoid B + + + n : Definition 2.1. For n 1 and C a nonempty set, the monoid of positive C-colored braids is the monoid with presentation (2.1)

B + + + n,C := σ (a) i (i n, a ∈ C) σ (a) i σ (b) j = σ (b) j σ (a) i for |i -j| 2 σ (a) i σ (b) j σ (c) i = σ (c) j σ (b) i σ (a) j for |i -j| = 1 + .
The idea is that the generator σ (a) i corresponds (as usual) to a crossing at positions i and i+1 with, in addition, an attached "color" a in C. The relations of (2.1) are then natural if we imagine that the colors are connected with the names, or initial positions, of the strands (as opposed to the current positions). Typically, we may think of taking for C the set of all (unordered) pairs in {1, ..., n}, the meaning of the crossing σ (p,q) i being "the strands starting at positions p and q cross at position i", see Figure 1. (p,q) i the meaning "the strands starting at positions p and q cross at position i", that is, if we take into account the names (origins) of the strand that cross, then the relations of (2.1) appear naturally.

p q r σ (p,q) i σ (p,r) i+1 σ (q,r) i σ (q,r) i ∼ p q r σ (q,r) i+1 σ (p,r) i σ (p,q) i+1
Of course, when the colour set C is a singleton, we can forget about colours, and the monoid B + + + n,C is simply the n-strand monoid-which is known to be cancellative since Garside [START_REF] Garside | The braid group and other groups[END_REF]. By contrast, for #C 2 and n 3, the presentation of (2.1) is not complemented (for some generators s, t, there is more than one relation of the type s... = t... in the presentation), and no simple criterion seems to apply. Here we shall prove: Proposition 2.2. The monoid B + + + n,C admits left and right cancellation. The proof consists of applying the criterion of Proposition 1.17, namely considering all generators σ (a) i and all relations w = w ′ of (2.1), and checking that, for every reversing grid built from σ (a) i and w, there exists an equivalent reversing grid built from σ (a) i and w ′ , and vice versa. We shall see that there are only two critical cases, with all other cases either reducing to them or being trivial. Proof. We look at all possible grids from (σ

(a) 1 , σ (b) 2 σ (c) 3 σ (d)
2 ), and exhibit for each of them an equivalent grid from (σ

(a) 1 , σ (d) 3 σ (c) 2 σ (b)
3 ), and conversely. First, exhaustively inspecting the presentation shows that the valid grids from (σ

(a) 1 , σ (b) 2 σ (c) 3 σ (d)
2 ) are the following grids, where e and f are arbitrary elements of the color set C: A priori, one might use different colors f, f ′ in the squares marked * , but f = f ′ leads to a grid that cannot be completed, since there is no relation

(2.2) σ (b) 2 σ (c) 3 σ (d) 2 σ (c) 3 σ (f) 2 σ (d) 1 ε σ (d) 1 σ (e) 2 σ (b) 1 σ (f) 3 σ (c) 2 ε σ (d) 1 σ (a) 1 σ (e) 1 σ (
σ (f) 2 ... = σ (f ′ ) 2 .
.. in (2.1). Now, consider the following valid grid:

(2.3) σ (d) 3 σ (c) 2 σ (b) 3 σ (b) 3 σ (d) 3 σ (f) 2 σ (c) 1 σ (e) 3 σ (b) 2 σ (a) 1 σ (a) 1 σ (f) 1 σ (a) 2 σ (f) 1 σ (e) 2 σ (a) 3
The right edges of (2.2) and (2.3) both yield the word σ

(f) 1 σ (e) 2 σ (a)
3 . For the bottom edges, using ≡ R for the congruence generated by the relations of (2.1), we find

σ (d) 3 σ (f) 2 σ (c) 1 σ (e) 3 σ (b) 2 ≡ R σ (d) 3 σ (f) 2 σ (e) 3 σ (c) 1 σ (b) 2 ≡ R σ (e) 2 σ (f) 3 σ (d) 2 σ (c) 1 σ (b) 2 ≡ R σ (e) 2 σ (f) 3 σ (b) 1 σ (c) 2 σ (d) 1 ≡ R σ (e) 2 σ (b) 1 σ (f) 3 σ (c) 2 σ (d)
1 , which shows that (2.2) and (2.3) are equivalent grids.

Conversely, starting from σ

3 , the only possible reversing grids have the form of (2.3) for some e and f in C, and then (2.2) provides the expected equivalent grid. Proof. As in Lemma 2.3, we look at all reversing grids from (σ (2.4)

σ (b) 1 σ (c) 3 σ (e) 3 σ (c) 2 σ (d) 1 σ (b) 2 σ (e) 3 σ (f) 2 σ (c) 1 σ (a) 2 σ (d) 2 σ (a) 1 σ (a) 1 σ (e) 2 σ (d) 3 σ (f) 1 σ (a) 2
On the other hand, the following grid is also valid:

(2.5) σ (c) 3 σ (b) 1 σ (e) 1 σ (b) 2 σ (f) 3 σ (c) 2 σ (e) 1 σ (d) 2 σ (b) 3 σ (a) 2 σ (f) 2 σ (a) 3 σ (a) 3 σ (e) 2 σ (f) 1 σ (d) 3 σ (a) 2
The right edges of (2.4) and (2.5) correspond to equivalent words, since we have

σ (e) 2 σ (f) 1 σ (d) 3 σ (a) 2 ≡ R σ (e) 2 σ (d) 3 σ (f) 1 σ (a) 2 .
Similarly, we find for the bottom edges

σ (f) 3 σ (c) 2 σ (e) 1 σ (d) 2 σ (b) 3 ≡ R σ (f) 3 σ (d) 1 σ (e) 2 σ (c) 1 σ (b) 3 ≡ R σ (d) 1 σ (f) 3 σ (e) 2 σ (b) 3 σ (c) 1 ≡ R σ (d) 1 σ (b) 2 σ (e) 3 σ (f) 2 σ (c) 1 .
Hence (2.4) and (2.5) are equivalent grids.

Conversely, the possible reversing grids from (σ

(a) 2 , σ (c) 3 σ (b)
1 ) have the form of (2.5) for some f , e, and d in C, and then (2.4) provides the expected equivalent grid.

Lemma 2.5. Property (♦) holds for all σ (a) i and all relations of (2.1).

Proof. First consider the case of σ (a) i and a relation σ

(b) j σ (c) k σ (d) j = σ (d) k σ (c) j σ (b)
k with, say, k = j + 1. For i j -2, every grid from (σ

(a) i , σ (b) j σ (c) k σ (d) j
) is a commutation grid, namely a grid in which every tile corresponds to a commutation relation st = ts, and then there exists an equivalent grid from (σ

(a) i , σ (d) k σ (c) j σ (b) k ) as shown below: (2.6) σ (b) j σ (c) k σ (d) j σ (b) j σ (c) k σ (d) j σ (a) i σ (a) i σ (a) i σ (a) i σ (d) k σ (c) j σ (b) k σ (d) k σ (c) j σ (b) k σ (a) i σ (a) i σ (a) i σ (a) i
The case when we start with a grid from (σ

(a) i , σ (d) k σ (c) j σ (b) k ) is similar.
The case i = j -1 corresponds to Lemma 2.3 for i = 1, and the general case is similar, since the relations of (2.1) are invariant under shifting the indices.

Next, assume i = j. Then a grid from (σ

) exists only for a = b, and then it is as in the left hand diagram below, in which case the right hand diagram provides an equivalent grid for e = c: The case i = j + 1 = k is symmetric to i = j. Similarly, the case i = j + 2 = k + 1 is symmetric to i = j -1. Finally, the cases i k + 2 are symmetric to i j -2.

(2.7) σ (b) j σ (c) k σ (d) j ε σ (c) k σ (d) j σ (a) i ε ε ε σ (d) k σ (c) j σ (b) k ε σ (b) k σ (e) k σ (d) j ε ε σ (a) i σ (e) j σ (
We now consider the case of σ (a)

i and a relation σ

(b) j σ (c) k = σ (c) k σ (b)
j with, say, k j+2. The case i j -2 is similar to that of (2.6), with commutation grids.

Assume i = j -1. Then the grids from (σ (2.8)

σ (b) j σ (c) k σ (c) k σ (d) j σ (b) i σ (c) k σ (a) i σ (d) i σ (a) j σ (d) i σ (a) j σ (c) k σ (b) j σ (c) k σ (d) j σ (b) i σ (a) i σ (a) i σ (d) i σ (a) j
In the other direction, the only grids from (σ The case i = j is almost trivial: grids may exist only for a = b, and then they take the form (2.9)

σ (b) j σ (c) k ε σ (c) k σ (a) i ε ε σ (c) k σ (b) j σ (c) k ε σ (a) i σ (a) i ε Next, assume j + 1 i k -1. If k = j + 2 holds, typically i = 2, j = 1, k = 3,
we are, up to a shifting of the indices, in the situation of Lemma 2.4, and so (♦) is guaranteed. Otherwise, either i is adjacent to exactly one of j or k, and the situation is that of (2.8), or i is at distance at least 2 from both j and k, and the situation is that of (2.7). Finally, the cases of i = k, i = k + 1, and i k + 2 are symmetric to those of (2.9), (2.8), and (2.7), respectively. Thus, all cases have been successfully treated.

We can now easily complete the proof of Proposition 2.2:

Proof of Proposition 2.2. The presentation (2.1) is eligible for the criterion of Proposition 1.17. Indeed, all relations are of the form w = w ′ with w, w ′ of the same length. Hence the monoid B + + + n,C is right noetherian. By Proposition 1.17 and Lemma 2.5, right reversing is complete for (2.1). Hence, as the presentation contains no relation contradicting left cancellation, the monoid admits left cancellation. Finally, the symmetry of the relations guarantees the identity map on the generators induces an anti-automorphism of the monoid, and, therefore, right cancellativity automatically follows from left cancellativity.

Inspecting the proofs above shows that, in the worst cases, the combinatorial distance between the outputs of the old and the new grids is at most 5, so, according to the terminology sketched in Remark 1.22, the defect of the presentation (2.1) is 5, which could be used to obtain explicit upper bounds on the number or reversing steps needed to possibly establish the equivalence of words.

As mentioned in Remark 1.18, our current approach says nothing about the embeddability of the involved monoid in a group. So the obvious question after Proposition 2.2 is Question 2.6. Does the monoid B + + + n,C embed in its universal group? A classical sufficient condition is provided by Ore's theorem [START_REF] Ore | Linear equations in non-commutative fields[END_REF] stating in the current context that a cancellative monoid M in which any two elements admit a common right multiple embeds in its universal group, which, in addition, is then a group of right fractions for M . This applies for instance to the monoid B + + + n . However, for #C 2, the monoid B + + + n,C admits no common multiple: for a = b, the elements σ ). In [START_REF] Dehornoy | Multifraction reduction I: The 3-Ore case and Artin-Tits groups of type FC[END_REF], the embeddability criterion of Ore's theorem is extended to cancellative monoids with no nontrivial invertible elements that satisfy the following "3-Ore condition":

(2.10) any three elements of M which pairwise admit a common right multiple admit a common right multiple, and similarly for left multiples, provided any two elements of M admit a left and a right gcd, i.e., greatest lower bounds with respect to left and right division. For #C 2, the monoid B + + + n,C

does not admit gcds: for instance, for a = b, the elements σ Question 2.8. Is the 3-Ore condition (2.10) sufficient for implying the embeddability of a monoid in its universal group in the case of a cancellative monoid that need not admit gcds?

2.2. A variant. In [START_REF] Berenstein | Monomial braidings[END_REF], the authors consider a variant of the monoid B + + + n,C with the same generators but with a restricted list of relations: Definition 2.9. For n 1 and C a nonempty set, the monoid of restricted positive C-colored braids is the monoid with presentation All relations of (2.11) are relations of (2.1), but, in the "Yang-Baxter" relations, the median color must be equal to one of the extremal colors. Thus the monoid B + + + n,C is a quotient of the monoid B + + + n,C . The authors of [START_REF] Berenstein | Monomial braidings[END_REF] ask whether the monoid B + + + n,C is cancellative. Frustratingly, the criterion of Proposition 1.17 cannot be applied:

= 1 +

 1 is left and right cancellative.

Example 1 . 2 .

 12 Consider the Artin presentation of the n-strand braid monoid(1.1)

Proposition 1 .

 1 19. Assume that a monoid presentation (S, R) satisfies (1.8) and (♦) for every s in S and every relation w = w ′ in R. Then two elements a, b of S | R + respectively represented by words u and v in S * admit a common right multiple if, and only if, there exists at least one (S, R)-grid from (u, v); in this case, every common right multiple of a and b is a right multiple of an element represented by uv 1 and by vu 1 with u

  and v ′ ≡ R v 1 u 2 are satisfied. The latter show that c is a right multiple of the element represented by uv 1 and vu 1 .Corollary 1.20. Assume that a monoid presentation (S, R) satisfies the assumptions of Proposition 1.19 and, moreover, it is right complemented, i.e., if, for all s, t in S, there is at most one relation s... = t... in R. Then two elements a, b of S | R + respectively represented by u and v in S * admit a common right multiple if, and only if, (u, v) R (u 1 , v 1 ) holds for some u 1 , v 1 ; in this case, the element represented by uv 1 and vu 1 is a right lcm of a and b.

Figure 1 .

 1 Figure 1. Colored braid relation: if we give σ

Lemma 2 . 3 .

 23 Property (♦) holds for σ

Lemma 2 . 4 .

 24 Property (♦) holds for σ

3 )

 3 are the following grids, with d, e, f arbitrary in C:

  In the other direction, the only possible grids from (σ to the right hand diagram in (2.7) with e = c and a = b, in which case the left diagram provides the required equivalent grid.

k

  ) are as on the left diagram below, with d arbitrary in C, and the right diagram then provides the expected equivalent grid from (σ

j

  ) are those shown in the right diagram of (2.8) with d arbitrary in C, and the left diagram then provides the expected equivalent grid.

  common right (or left) multiple, since there is no valid reversing grid from (σ

Question 2 . 7 .

 27 the above elements. This leads to two new questions: Does the monoid B + + + n,C satisfy the 3-Ore condition (2.10)?

( 2 .

 2 11) B + + + n,C := σ

Fact 2 . 10 .

 210 If C has at least two elements, right reversing is not complete for the presentation (2.11).Proof. Let a, b, c be elements of C satisfying a = b and a = c. Then Property (♦) fails for σ there may exist no equivalent grid from (σ Indeed, according to what was seen in the proof of Lemma 2.3, the only possible form for such a grid

We move to the top right square. Then v 2 ≡ R v 2 is trivial, whereas u ′ 4 ≡ R u 4 and (u 4 , v 2 ) R (u 6 , v 7 ) hold by construction. Moreover, because w cannot be empty, since R contains no ε-relation, (1.10) implies λ(u 4 v 7 ) < λ(wu 4 v 7 ) λ(v 0 wu 4 v 7 ) λ(v 0 wu 4 v 7 u 7 ) = λ(uv 1 ) α, whence γ := λ(u 4 v 7 ) < α. By induction hypothesis, (♦ * γ ) is true for u 4 and v 2 , and we deduce the existence of u ′ 6 and v ′ 7 satisfying

. Finally, we consider the bottom right square. By construction, we have

whence δ := λ(u 5 v 5 ) < α. By induction hypothesis, (♦ * δ ) is true for u 5 and v 7 , and we deduce the existence of u ′ 7 and v ′ 5 satisfying

) is satisfied for u and v, which completes the case d = 1 in the induction for (♦ * α ). Assume finally α > 0 and d 2. Assume that Γ is a grid with diagonal α from (u, v) to (u 1 , v 1 ), and dist

By assumption, we have λ(uv 1 ) α. By induction hypothesis, (♦ * α,d-1 ) is true for u and v, so we deduce the existence of

) is true for u ′′ and v ′′ , so we deduce the existence of

, and we conclude that (♦ * α,d ) is true for u and v. This completes the induction. 1.3. Main results. We are now ready to state the main results of the paper and, in particular, to establish the cancellativity criterion announced in the title.

First, summarizing the results established so far directly gives the following:

Proposition 1.15. Assume that a monoid presentation (S, R) satisfies (1.8) and (♦) for every s in S and every relation

(ii) For all u, v in S * , the words u and v represent the same element of the monoid S | R + if, and only if, (u, v) R (ε, ε) holds.

Proof. Point (i) is Condition (♦ * ) for u, v, and Lemma 1.13 states that the latter holds whenever (1.8) holds and so does (♦) for every s in S and every relation w = w ′ in R. would be (2.13)

2 on the bottom edge of (2.12) with respect to the congruence generated by the relations of (2.11) consists of two words only, namely σ 2 )-grid may be equivalent to (2.12).

The above negative result does not say that the monoid B + + + n,C is not cancellative, it just says that the criterion of Proposition 1.17 fails to apply. The proof of Fact 2.10 provides an explicit example of a valid relation that cannot be checked using reversing, namely n,C admit cancellation? Does it embed in its universal group?