forked from reiniscirpons/reiniscirpons.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpublications.html
186 lines (186 loc) · 7.03 KB
/
publications.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
<!doctype html>
<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Reinis Cirpons - Publications</title>
<link href="./favicon.ico" rel="icon" />
<link href="./style.css" rel="stylesheet" type="text/css" />
</head>
<body>
<header>
<h1>Reinis Cirpons's homepage</h1>
<nav>
<menu>
<li>
<a href="./index.html">Home</a>
</li>
<li>
<a href="./cv.pdf">CV</a>
</li>
<li>
<mark><a href="./publications.html">Publications</a></mark>
</li>
<li>
<a href="./software.html">Software</a>
</li>
<li>
<a href="./talks.html">Talks</a>
</li>
<li>
<a href="./teaching.html">Teaching</a>
</li>
</menu>
</nav>
<hr />
</header>
<main>
<h2>Publications</h2>
<p>
See also:
<a href="https://arxiv.org/a/cirpons_r_1.html">a/cirpons_r_1</a> on
arXiv and
<a href="https://orcid.org/0000-0001-7238-1576">0000-0001-7238-1576</a>
on ORCiD.
</p>
<h3>Published</h3>
<dl>
<dt>"Polynomial time multiplication and normal forms in free bands"</dt>
<dd>
<div>With <a href="https://jdbm.me/">J. D. Mitchell</a></div>
<div>
<cite
>Theoretical Computer Science <b>953</b> (2023). doi:
<a href="https://doi.org/10.1016/j.tcs.2023.113783"
>10.1016/j.tcs.2023.113783</a
></cite
>
</div>
<div>
Preprint:
<a href="https://arxiv.org/abs/2209.05334">arXiv:2209.05334</a>
</div>
<div>
<details>
<summary>Abstract</summary>
We present efficient computational solutions to the problems of
checking equality, performing multiplication, and computing
minimal representatives of elements of free bands. A band is any
semigroup satisfying the identity and the free band is the free
object in the variety of k-generated bands. Radoszewski and Rytter
developed a linear time algorithm for checking whether two words
represent the same element of a free band. In this paper we
describe an alternate linear time algorithm for the same problem.
The algorithm we present utilises a representation of words as
synchronous deterministic transducers that lend themselves to
efficient (quadratic in the size of the alphabet) multiplication
in the free band. This representation also provides a means of
finding the short-lex least word representing a given free band
element with quadratic complexity.
</details>
</div>
</dd>
</dl>
<h3>In preparation</h3>
<dl>
<dt>"Transformation representations of diagram monoids"</dt>
<dd>
<div>
With
<a href="https://staff.cdms.westernsydney.edu.au/~james/"
>J. East</a
>
and <a href="https://jdbm.me/">J. D. Mitchell</a>
</div>
<div>
Preprint:
<a href="https://arxiv.org/abs/2411.14693">arXiv:2411.14693</a>
</div>
<div>
<details>
<summary>Abstract</summary>
We obtain formulae for the minimum transformation degrees of the
most well-studied families of finite diagram monoids, including
the partition, Brauer, Temperley–Lieb and Motzkin monoids. For
example, the partition monoid P_n has degree 1 +
(B(n+2)-B(n+1)+B(n))/2 for n > 1, where these are Bell numbers.
The proofs involve constructing explicit faithful representations
of the minimum degree, many of which can be realised as (partial)
actions on projections.
</details>
</div>
</dd>
<dt>
"Computing finite index congruences of finitely presented semigroups
and monoids"
</dt>
<dd>
<div>
With
<a href="https://marinaanagno.github.io/"
>M. Anagnostopoulou-Merkouri</a
>, <a href="https://jdbm.me/">J. D. Mitchell</a> and
<a href="https://mariatsalakou.github.io/">M. Tsalakou</a>
</div>
<div>
Preprint:
<a href="https://arxiv.org/abs/2302.06295">arXiv:2302.06295</a>
</div>
<div>
<details>
<summary>Abstract</summary>
In this paper we describe an algorithm for computing the left,
right, or 2-sided congruences of a finitely presented semigroup or
monoid with finitely many classes, and alternative algorithm when
the finitely presented semigroup or monoid is finite. We compare
the two algorithms presented to existing algorithms and
implementations. The first algorithm is a generalization of Sims'
low index subgroup algorithm for finding the congruences of a
monoid. The second algorithm involves determining the distinct
principal congruences, and then finding all of their possible
joins. Variations of this algorithm have been suggested in
numerous contexts by numerous authors. We show how to utilise the
theory of relative Green's relations, and a version of Schreier's
Lemma for monoids, to reduce the number of principal congruences
that must be generated as the first step of this approach. Both of
the algorithms described in this paper are implemented in the
<a href="https://www.gap-system.org/">GAP</a> package
<a href="https://github.com/semigroups/Semigroups">Semigroups</a>
, and the first algorithm is available in the C++ library
<a href="https://github.com/libsemigroups/libsemigroups"
>libsemigroups</a
>
and in its python bindings
<a href="https://github.com/libsemigroups/libsemigroups_pybind11"
>libsemigroups_pybind</a
>.
</details>
</div>
</dd>
</dl>
<h3>Other</h3>
<dl>
<dt>
"Computing in relatively free bands - An acyclic transducer based
approach"
</dt>
<dd>
<div>Masters project</div>
<div>
<a href="./publications/computing-in-relatively-free-bands.pdf"
>Download document (PDF, 0.3MB)</a
>
</div>
</dd>
</dl>
</main>
<footer>
<hr />
<ul>
<li>
<a href="https://github.com/reiniscirpons">GitHub</a>
</li>
<li>2022-2024 R. Cirpons</li>
</ul>
</footer>
</body>
</html>