Group, Ring, Language and Related Areasin Computer ScienceRIMS, 2023
February 15-17 , 2023
The Kyoto University Research Institute for Mathematical Science
Kyoto University

Invited Speakers

Collin Bleak
University of St Andrews, School of Mathematics and Statistics,
UK

Title: Embeddings into Finitely Presented Simple Groups
Abstract: In this talk, we describe a process whereby we can embed any hyperbolic
group into a ﬁnitely presented inﬁnite simple group. This gives a proof of what is, insome sense, the ”typical” case of the Boone-Higman Conjecture of 1973 (that a ﬁnitely
generated group G has a solvable word problem if and only if G can be embedded into aﬁnitely presented simple group).
The talk will proceed in three roughly independent parts: A short history of the BooneHigman Conjecture, a discussion of Hyperbolic groups and an embedding of these into theRational group of Grigorchuk, Nekrashevych, and Suschanskii, and ﬁnally, a discussionof why the topological full group over this rational group is ﬁnitely presented and simple,
or, at least provides a route to a further embedding in a group that is ﬁnitely presentedand simple.
Joint with James Belk, Francesco Matucci, and Matthew Zaremsky.

Alexander Meduna
Brno University of Technology, Department of Information Systems,
Czech Republic

Title: Grammars with Context Conditions and Their Applications
Abstract: In the classical formal language theory, we can divide grammatical productions into context-dependent and context-independent productions, and based on thisdivision, we can naturally distinct context-dependent grammars, such as phrase-structuregrammars, from context-independent grammars, such as context-free grammars. Making
a derivation step according to context-dependent productions depends on rather strict
conditions satisﬁed by the context surrounding the rewritten symbol while making a
step according to context-independent productions does not, so from this point of view,
we obviously always prefer using context-independent grammars to the others. Unfortunately, compared to context-dependent grammars, context-independent grammars are
signiﬁcantly less powerful; in fact, most of them are incapable to grasp some aspectsof quite common programming languages. On the other hand, most context-dependent
grammars are equivalent to the Turing machines, and this remarkable power represents
their indisputable advantage. These pros and cons inspired the modern language theory
to introducing some new grammars that simultaneously satisfy these properties-(1) they
are based on context-independent productions, (2) their context conditions are signiﬁcantly simpler than the strict conditions of classical context-dependent productions, and(3) they are as powerful as classical context-dependent grammars.
In the present talk, we overview the most essential types of these grammars, whosealternative context conditions can be classical into these three categories-(A) context
conditions placed on derivation domains, (B) context conditions placed on the use of productions, (C) context conditions placed on the neighborhood of the rewritten symbols.
As already pointed out, we want the context conditions as small as possible. Therefore,
we concentrate the investigation on the reduction of context conditions. Speciﬁcally, it
reduces the number of some of their components, such as nonterminals or productions.
It studies how to achieve this reduction without any decrease in this generative power,
which coincides with the power of the Turing machines. By achieving this reduction,
it actually makes the partially parallel rewriting more succinct and economical, and thiseconomization is obviously highly appreciated both from a practical and theoretical standpoint. Regarding each of the discussed grammars, we introduce and study their paralleland sequential versions, which represent two basic approaches to grammatical rewriting intoday s formal language theory. That is, during a sequential derivation step, a grammar
rewrites a single symbol in the current sentential form while during a parallel derivation
step, a grammar rewrites all symbols. As context-free and E0L grammars represent perhaps the most fundamental sequential and parallel grammars, respectively, we usuallybase the discussion of sequential and parallel rewriting upon them.

In the conclusion of this talk, we illustrate the applications of grammars with context
conditions by several biologically oriented examples.
The talk is based upon the author’s latest book Handbook of Mathematical Models
for Languages and Computation (written along with his PhD students Petr Horáček andMartin Tomko), The Institution of Engineering and Technology, 2020.
Keywords: formal grammars; context conditions; basic properties; language families; reduction; simpliﬁcation; descriptional complexity; applications; perspectives.
Author: Prof. Alexander Meduna (born 1957 in Olomouc, Czech Republic ) is a theoretical computer scientist and expert on compiler design, formal languages and automata. Heis a full professor of Computer Science at the Brno University of Technology. Formerly,
he taught theoretical computer science at various European and American universities,
including the University of Missouri, where he spent a decade teaching advanced topics
of formal language theory. He wrote over ninety papers related to theoretical computerscientist. His books include
References• Meduna, Alexander (2000). Automata and Languages: Theory and Applications.
Springer Science & Business Media. ISBN 9781852330743.
• Meduna, Alexander (2007). Elements of Compiler Design. CRC Press. ISBN
9781420063233.
• Meduna, Alexander (2014). Formal Languages and Computation: Models and TheirApplications. CRC Press. ISBN 9781466513457.
• Meduna, Alexander; Švec, Martin (2005). Grammars with Context Conditions andTheir Applications. John Wiley & Sons. ISBN 9780471736554.
• Meduna, Alexander; Techet, Jiřı́ (2010). Scattered Context Grammars and TheirApplications. WIT Press. ISBN 9781845644260.
• Meduna, Alexander; Zemek, Petr (2014). Regulated Grammars and Automata.
Springer. ISBN 9781493903696.
• Meduna, Alexander; Soukup, Ondřej (2017). Modern Language Models and Computation: Theory with Applications. Springer. ISBN 9783319630991.
• Meduna, Alexander; Horáček, Petr; Tomko, Martin (2020): Handbook of Mathematical Models for Languages and Computation, The Institution of Engineeringand Technology. ISBN 978-1-78561-660-0.

Carl-Fredrik Nyberg Brodda
University Gustave Eiﬀel,France

Title: Language-theoretic methods in semigroup theory
Abstract: ”Language-theoretic methods in combinatorial group theory go back to thefundamental work by Anisimov in the 1970s. Since then, the area has exploded, including such deep theorems as the Muller-Schupp theorem: a group has context-free word
problem if and only if it is virtually free. In this talk, I will give a brief overview ofhistoric developments, and then discuss how this area has a rich parallel in the theoryof combinatorial semigroup theory. I will give a taste of the kinds of results that canbe proved when using language-theoretic methods in semigroup theory, including resultson free products, hyperbolic semigroups, analogues of the Muller-Schupp theorem, andhow context-free semigroups can behave very diﬀerently from context-free groups. I willend by discussing how language-theoretic methods for semigroups can shed light on open
questions in group theory, including groups admitting an ET0L/indexed multiplicationtable, or groups with ET0L/indexed word problem.”Yuko MurakamiRikkyo University, Graduate School of Artiﬁcial Intelligence and Science Doctoral Program in
Artiﬁcial Intelligence and Science,Japan

Title: Elucidation of completeness of achievement stit logic of agency
Abstract: The see-to-it-that (stit) logic of agency is proposed in Belnap-Perloﬀ-Xu(2001).
Among stit logics, deliberative stit (dstit) logic has been popular in connection to otheroperators, especially epistemic and dynamic modalities. In the model of dstit agency, themoment of action evaluation coincides with that of the action itself. We do not have toconsider any tacit tense behind the notion of action in dstit. The very notion of tense,
however, is essential in the conceptual analysis of agency: the moment of action must
precede the moment of evaluation of the action. Achievement stit (astit) logic of agency
reﬂects the insight to model the concept of action on branching time model to allow
indeterminism of action for rooms of free will. This talk aims to illustrate the line ofthought behind the completeness theorem of achievement stit logic of agency, so as toinvite audience to investigate extensions and variations of astit.
References• Belnap-Perloﬀ-Xu, Facing the Future: Agents and Choices in Our Indeterminist
World. Oxford UP, 2001.
• G. K. Olkhovikov, H. Wansing, Inference as Doxastic Agency. Part I: The Basics ofJustiﬁcation Stit Logic. Studia Logica (2019) 107: 167-194, 1994.

In Japanese:Title: 達成行為論理の完全性証明の説明
Abstract: Belnap-Perloﬀ-Xu(2001) では stit 行為論理の背景となる哲学的洞察に基づく論理体系が提案されている。そのうちその後の研究が多くなされている (Olkhovikov-Wansing2019) 熟考行為論理 (deliberative stit logic) では行為時点が行為の評価と同時点となっている。だが、より行為論へ適切に応用できる達成行為論理については後続研究がほとんどない。達成行為論理では、行為評価に先立つ時点で行為がなされるタイプの行為概念について、時制論理の樹状モデル上に行為様相にかかる真理条件を導入してモデル化することにより、行為論における非決定論の数理モデルを与えようとする。この論理を公理化した達成行為論理体系の完全性証明について、直観的な理解につながるように説明する。

Takeo Uramoto
Kyushu University, Institute of Mathematics for Industry,Japan

Title: On algebraic language theory, Galois theory, and class ﬁeld theory
Abstract: In this talk, I will introduce some of my recent works on algebraic language
theory, and its connection to galois theory and classical class ﬁeld theory. Algebraic language theory generally concerns classiﬁcation of formal languages by means of algebra;
Eilenberg theory in particular focuses on classiﬁcation of regular languages by means ofﬁnite semigroup theory, where typical results, say Schutzenberger’s pioneering result in
1965, states that a regular language L can be deﬁned by ﬁrst-order formula of Buchi’smonadic second-order logic on ﬁnite words if and only if its syntactic monoid M(L) contains only trivial subgroups; this connects combinatorial/logical describability of regular
languages with purely semigroup-theoretic property of their syntactic monoids; and Eilenberg theory has developed similar results on the connection between regular languages
and ﬁnite monoids. These results in Eilenberg theory are analogous to classical resultsin galois theory, where, say, Galois’ theorem states that the solutions of a polynomial
equation f(x)=0 can be written by four arithmetic operations and taking roots if and only
if its galois group is soluble. This talk ﬁrst introduces that this analogy can be in fact
justiﬁed by a suitable category-theoretic duality theorem; and then that this connection
between Eilenberg’s theory and Galois’ theory sheds new light on classical class ﬁeld theory, in particular, the theory of complex multiplication. I may also discuss some future
directions related to these results.