Computer Science › Computational Theory and Mathematics

semigroups and automata theory

Works Count: 46421

Wikipedia

Description

This cluster of papers covers topics in automata theory, formal languages, and combinatorics on words. It includes research on regular expressions, finite automata, transducers, synchronizing automata, Sturmian words, and state complexity. The cluster also explores the connections between automata theory and semigroups.

Keywords

Automata; Formal Languages; Regular Expressions; Finite Automata; Combinatorics on Words; Transducers; Synchronizing Automata; Sturmian Words; State Complexity; Semigroups

Tree-Adjoining Grammars

1997-01-01

Aravind K. Joshi , Yves Schabes

Fundamentals of Semigroup Theory

1995-12-07

John Howie

Abstract This book is an indispensable source for anyone with an interest in semigroup theory or whose research overlaps with this increasingly important and active field of mathematics. It clearly … Abstract This book is an indispensable source for anyone with an interest in semigroup theory or whose research overlaps with this increasingly important and active field of mathematics. It clearly emphasizes "pure" semigroup theory, in particular the various classes of regular semigroups. More than 150 exercises, accompanied by relevant references to the literature, give pointers to areas of the subject not explicitly covered in the text.

Word Processing in Groups

1992-11-02

D. B. A. Epstein

From the Publisher: This study in combinatorial group theory introduces the concept of automatic groups. It contains a succinct introduction to the theory of regular languages, a discussion of related … From the Publisher: This study in combinatorial group theory introduces the concept of automatic groups. It contains a succinct introduction to the theory of regular languages, a discussion of related topics in combinatorial group theory, and the connections between automatic groups and geometry which motivated the development of this new theory. It is of interest to mathematicians and computer scientists and includes open problems that will dominate the research for years to come.

Concurrency and automata on infinite sequences

2005-11-22

David Park

View PDF Chat

Automata on Infinite Objects

1990-01-01

Wolfgang Thomas

Automata-Theoretic Aspects of Formal Power Series

1978-01-01

Arto Salomaa , Matti Soittola

Handbook of Formal Languages

1997-01-01

Grzegorz Rozenberg , Arto Salomaa

The algebraic theory of semigroups

1964-01-01

A. H. Clifford , G. B. Preston

This book, along with volume I, which appeared previously, presents a survey of the structure and representation theory of semi groups. Volume II goes more deeply than was possible in … This book, along with volume I, which appeared previously, presents a survey of the structure and representation theory of semi groups. Volume II goes more deeply than was possible in volume I into the theories of minimal ideals in a semi group, inverse semi groups, simple semi groups, congruences on a semi group, and the embedding of a semi group in a group. Among the more important recent developments of which an extended treatment is presented are B. M. Sain's theory of the representations of an arbitrary semi group by partial one-to-one transformations of a set, L. Redei's theory of finitely generated commutative semi groups, J. M. Howie's theory of amalgamated free products of semi groups, and E. J. Tully's theory of representations of a semi group by transformations of a set. Also a full account is given of Malcev's theory of the congruences on a full transformation semi group.

Tree Automata Techniques and Applications

2008-01-01

Hubert Comon , Max Dauchet , Rémi Gilleron +5 more

View PDF Chat

Mathematical Methods in Linguistics

1993-01-01

Barbara H. Partee , Alice Ter Meulen , Robert E. Wall

Languages, Automata, and Logic

1997-01-01

Wolfgang Thomas

Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems

1980-10-01

Gérard Huet

article Free Access Share on Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems Author: Gérard Huet INRIA, Domaine de Voluceau-Rocquencourt, … article Free Access Share on Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems Author: Gérard Huet INRIA, Domaine de Voluceau-Rocquencourt, B.P. 105-78150 Le Chesnay, France INRIA, Domaine de Voluceau-Rocquencourt, B.P. 105-78150 Le Chesnay, FranceView Profile Authors Info & Claims Journal of the ACMVolume 27Issue 4Oct. 1980 pp 797–821https://doi.org/10.1145/322217.322230Online:01 October 1980Publication History 818citation2,084DownloadsMetricsTotal Citations818Total Downloads2,084Last 12 Months223Last 6 weeks44 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

View PDF Chat

Reasoning about Infinite Computations

1994-11-01

Moshe Y. Vardi , Pierre Wolper

View PDF Chat

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

1975-12-01

T. P. Baker , John Gill , Robert M Solovay

We investigate relativized versions of the open question of whether every language accepted nondeterministically in polynomial time can be recognized deterministically in polynomial time. For any set X, let $\mathcal{P}^X … We investigate relativized versions of the open question of whether every language accepted nondeterministically in polynomial time can be recognized deterministically in polynomial time. For any set X, let $\mathcal{P}^X (\text{resp. }\mathcal{NP}^X )$ be the class of languages accepted in polynomial time by deterministic (resp. nondeterministic) query machines with oracle X. We construct a recursive set A such that $\mathcal{P}^A = \mathcal{NP}^A $. On the other hand, we construct a recursive set B such that $\mathcal{P}^B \ne \mathcal{NP}^B $. Oracles X are constructed to realize all consistent set inclusion relations between the relativized classes $\mathcal{P}^X $, $\mathcal{NP}^X $, and co $\mathcal{NP}^X $, the family of complements of languages in $\mathcal{NP}^X $. Several related open problems are described.

Improved methods for calculating vectors of short length in a lattice, including a complexity analysis

1985-01-01

U. Fincke , Michael Pohst

The standard methods for calculating vectors of short length in a lattice use a reduction procedure followed by enumerating all vectors of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper Z Superscript … The standard methods for calculating vectors of short length in a lattice use a reduction procedure followed by enumerating all vectors of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper Z Superscript m"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">Z</mml:mi> </mml:mrow> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{{\mathbf {Z}}^m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in a suitable box. However, it suffices to consider those <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold x element-of bold upper Z Superscript m"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">x</mml:mi> </mml:mrow> </mml:mrow> <mml:mo>∈</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">Z</mml:mi> </mml:mrow> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbf {x}} \in {{\mathbf {Z}}^m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which lie in a suitable ellipsoid having a much smaller volume than the box. We show in this paper that searching through that ellipsoid is in many cases much more efficient. If combined with an appropriate reduction procedure our method allows to do computations in lattices of much higher dimensions. Several randomly constructed numerical examples illustrate the superiority of our new method over the known ones.

View PDF Chat

Word problems requiring exponential time(Preliminary Report)

1973-01-01

Larry J. Stockmeyer , Albert R. Meyer

The equivalence problem for Kleene's regular expressions has several effective solutions, all of which are computationally inefficient. In [1], we showed that this inefficiency is an inherent property of the … The equivalence problem for Kleene's regular expressions has several effective solutions, all of which are computationally inefficient. In [1], we showed that this inefficiency is an inherent property of the problem by showing that the problem of membership in any arbitrary context-sensitive language was easily reducible to the equivalence problem for regular expressions. We also showed that with a squaring abbreviation ( writing (E)2 for E×E) the equivalence problem for expressions required computing space exponential in the size of the expressions.

View PDF Chat

Generalized finite automata theory with an application to a decision problem of second-order logic

1968-03-01

J. W. Thatcher , Jesse B. Wright

Transition network grammars for natural language analysis

1970-10-01

William A. Woods

The use of augmented transition network grammars for the analysis of natural language sentences is described. Structure-building actions associated with the arcs of the grammar network allow for the reordering, … The use of augmented transition network grammars for the analysis of natural language sentences is described. Structure-building actions associated with the arcs of the grammar network allow for the reordering, restructuring, and copying of constituents necessary to produce deep-structure representations of the type normally obtained from a transformational analysis, and conditions on the arcs allow for a powerful selectivity which can rule out meaningless analyses and take advantage of semantic information to guide the parsing. The advantages of this model for natural language analysis are discussed in detail and illustrated by examples. An implementation of an experimental parsing system for transition network grammars is briefly described.

View PDF Chat

On certain formal properties of grammars

1959-06-01

Noam Chomsky

Finite Automata and Their Decision Problems

1959-04-01

M. O. Rabin , D. Scott

Finite automata are considered in this paper as instruments for classifying finite tapes. Each one-tape automaton defines a set of tapes, a two-tape automaton defines a set of pairs of … Finite automata are considered in this paper as instruments for classifying finite tapes. Each one-tape automaton defines a set of tapes, a two-tape automaton defines a set of pairs of tapes, et cetera. The structure of the defined sets is studied. Various generalizations of the notion of an automaton are introduced and their relation to the classical automata is determined. Some decision problems concerning automata are shown to be solvable by effective algorithms; others turn out to be unsolvable by algorithms.

On the translation of languages from left to right

1965-12-01

Donald E. Knuth

Programming Techniques: Regular expression search algorithm

1968-06-01

Thompson Ken

A method for locating specific character strings embedded in character text is described and an implementation of this method in the form of a compiler is discussed. The compiler accepts … A method for locating specific character strings embedded in character text is described and an implementation of this method in the form of a compiler is discussed. The compiler accepts a regular expression as source language and produces an IBM 7094 program as object language. The object program then accepts the text to be searched as input and produces a signal every time an embedded string in the text matches the given regular expression. Examples, problems, and solutions are also presented.

View PDF Chat

Finding All the Elementary Circuits of a Directed Graph

1975-03-01

D. Barton Johnson

An algorithm is presented which finds all the elementary circuits of a directed graph in time bounded by $O((n + e)(c + 1))$ and space bounded by $O(n + e)$, … An algorithm is presented which finds all the elementary circuits of a directed graph in time bounded by $O((n + e)(c + 1))$ and space bounded by $O(n + e)$, where there are n vertices, e edges and c elementary circuits in the graph. The algorithm resembles algorithms by Tiernan and Tarjan, but is faster because it considers each edge at most twice between any one circuit and the next in the output sequence.

Data types as lattices

2006-11-24

Dana Scott

AN n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON

1971-01-01

John E. Hopcroft

Finite-state transducers in language and speech processing

1997-06-01

Mehryar Mohri

Finite-machines have been used in various domains of natural language processing. We consider here the use of a type of transducer that supports very efficient programs: sequential transducers. We recall … Finite-machines have been used in various domains of natural language processing. We consider here the use of a type of transducer that supports very efficient programs: sequential transducers. We recall classical theorems and give new ones characterizing sequential string-to-string transducers. Transducers that outpur weights also play an important role in language and speech processing. We give a specific study of string-to-weight transducers, including algorithms for determinizing and minizizing these transducers very efficiently, and characterizations of the transducers admitting determinization and the corresponding algorithms. Some applications of these algorithms in speech recognition are described and illustrated.

The On-Line Encyclopedia of Integer Sequences

2007-08-14

N. J. A. Sloane

View PDF Chat

Tree adjunct grammars

1975-02-01

Aravind K. Joshi , Leon S. Levy , Masako Takahashi

An efficient context-free parsing algorithm

1983-01-01

Jay Earley

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR( k ) algorithm and the familiar top-down … A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR( k ) algorithm and the familiar top-down algorithm. It has a time bound proportional to n 3 (where n is the length of the string being parsed) in general; it has an n 2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.

Derivatives of Regular Expressions

1964-10-01

Janusz Brzozowski

article Free Access Share on Derivatives of Regular Expressions Author: Janusz A. Brzozowski Department of Electrical Engineering, University of Ottawa, Ottawa, 2, Canada and Princeton University, Princeton, New Jersey Department … article Free Access Share on Derivatives of Regular Expressions Author: Janusz A. Brzozowski Department of Electrical Engineering, University of Ottawa, Ottawa, 2, Canada and Princeton University, Princeton, New Jersey Department of Electrical Engineering, University of Ottawa, Ottawa, 2, Canada and Princeton University, Princeton, New JerseyView Profile Authors Info & Claims Journal of the ACMVolume 11Issue 401 October 1964pp 481–494https://doi.org/10.1145/321239.321249Published:01 October 1964Publication History 652citation7,982DownloadsMetricsTotal Citations652Total Downloads7,982Last 12 Months828Last 6 weeks71 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

View PDF Chat

On Context-Free Languages

1966-10-01

Rohit Parikh

In this report, certain properties of context-free (CF or type 2) grammars are investigated, like that of Chomsky. In particular, questions regarding structure, possible ambiguity and relationship to finite automata … In this report, certain properties of context-free (CF or type 2) grammars are investigated, like that of Chomsky. In particular, questions regarding structure, possible ambiguity and relationship to finite automata are considered. The following results are presented: The language generated by a context-free grammmar is linear in a sense that is defined precisely. The requirement of unambiguity—that every sentence has a unique phrase structure—weakens the grammar in the sense that there exists a CF language that cannot be generated unambiguously by a CF grammar. The result that not every CF language is a finite automaton (FA) language is improved in the following way. There exists a CF language L such that for any L′ ⊆ L , if L′ is FA, an L″ ⊆ L can be found such that L″ is also FA, L′ ⊆ L″ and L″ contains infinitely many sentences not in L′ . A type of grammar is defined that is intermediate between type 1 and type 2 grammars. It is shown that this type of grammar is essentially stronger than type 2 grammars and has the advantage over type 1 grammars that the phrase structure of a grammatical sentence is unique, once the derivation is given.

View PDF Chat

Decidability of second-order theories and automata on infinite trees.

1969-01-01

Michael O. Rabin

Introduction.In this paper we solve the decision problem of a certain secondorder mathematical theory and apply it to obtain a large number of decidability results.The method of solution involves the … Introduction.In this paper we solve the decision problem of a certain secondorder mathematical theory and apply it to obtain a large number of decidability results.The method of solution involves the development of a theory of automata on infinite trees-a chapter in combinatorial mathematics which may be of independent interest.Let £ = {0, 1}, and denote by T the set of all words (finite sequences) on 2. Let r0: T^-T and rx: T->■ T be, respectively, the successor functions ro(x)=x0 and r1(x) = xl, xeT.Our main result is that the (monadic) second-order theory of the structure (T, r0, rxy of two successor functions is decidable.This answers a question raised by Biichi [1].It turns out that this result is very powerful and many difficult decidability results follow from it by simple reductions.The decision procedures obtained by this method are elementary recursive (in the sense of Kalmar).The applications include the following.(Whenever we refer, in this paper, to second-order theories, we mean monadic second-order; weak second-order means quantification restricted to finite subsets of the domain.)The second-order theory of countable linearly ordered sets is proved decidable.As a corollary we get that the weak second-order theory of arbitrary linearly ordered sets is decidable ; a result due to Läuchli [9] which improves on a result of Ehrenfeucht [5].In [4] Ehrenfeucht announced the decidability of the first-order theory of a unary function.We prove that the second-order theory of a unary function with a countable domain is decidable.Also, the weak second-order theory of a unary function with an arbitrary domain is decidable.There are also applications to point set topology.Let CD be Cantor's discontinuum (i.e., (0, 1}™ with the product topology).Let Fa be the lattice of all subsets of CD which are denumerable unions of closed sets, and let Lc be the sublattice of all closed subsets of CD.The first-order theory of the lattice Fa, with Lc as a distinguished sublattice, is decidable.Similar results hold for the real line with the usual topology.This answers in the affirmative Grzegorczyk's question [8] whether Presented to the Society, July 5, 1967; received by the editors March 4, 1968.

View PDF Chat

Reducibility among Combinatorial Problems

1972-01-01

Richard M. Karp

One-parameter semigroups

2007-04-26

E. B. Davies

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content. A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Formal Languages and their Relation to Automata

1970-05-01

James B. Morris

"Formal Languages and their Relation to Automata." Nuclear Science and Engineering, 40(2), pp. 358–359 Additional informationNotes on contributorsJames B. MorrisAbout the Reviewer: James B. Morris received his PhD degree, with … "Formal Languages and their Relation to Automata." Nuclear Science and Engineering, 40(2), pp. 358–359 Additional informationNotes on contributorsJames B. MorrisAbout the Reviewer: James B. Morris received his PhD degree, with a major in computer science, from the University of Texas at Austin in August, 1969. He is currently employed by the computer science research group at the University of California, Los Alamos Scientific Laboratory, Los Alamos, New Mexico. His special interests include the design of programming language translators and the theory of alogorithm equivalence.

The mathematical theory of context-free languages

1967-07-01

H. P. Edmundson

Random generation of combinatorial structures from a uniform distribution

1986-01-01

Mark Jerrum , Leslie G. Valiant , Vijay V. Vazirani

Introduction to Algorithms

2021-01-01

Thomas Mailund

We briefly discussed what we mean by algorithms in Chapter 1 , but perhaps it bears repeating; algorithms are recipes for solving a specific computational problem. They describe the steps … We briefly discussed what we mean by algorithms in Chapter 1 , but perhaps it bears repeating; algorithms are recipes for solving a specific computational problem. They describe the steps you (or more usually your computer) must take to get from input to output and should guarantee you that if you follow the instructions exactly, you will (1) finish after a finite number of steps and (2) your output will be a solution to the problem they should solve, given the input you had.

The Algebraic Theory of Semigroups, Volume I

1961-12-31

A. Clifford , GB Preston

Weak Second‐Order Arithmetic and Finite Automata

1960-01-01

J Büchi

Alternation

1981-01-01

Ashok K. Chandra , Dexter Kozen , Larry J. Stockmeyer

article Free AccessAlternation Authors: Ashok K. Chandra IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown … article Free AccessAlternation Authors: Ashok K. Chandra IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New YorkView Profile , Dexter C. Kozen IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New YorkView Profile , Larry J. Stockmeyer IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New YorkView Profile Authors Info & Claims Journal of the ACMVolume 28Issue 1pp 114–133https://doi.org/10.1145/322234.322243Published:01 January 1981Publication History 1,298citation4,917DownloadsMetricsTotal Citations1,298Total Downloads4,917Last 12 Months465Last 6 weeks61 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

View PDF Chat

Introduction to automata theory, languages, and computation

1980-01-01

Counterexamples to the 𝑝(𝑡)-adic Littlewood conjecture over small finite fields

2025-06-24

Samuel Garrett , S. H. Robertson | Mathematics of Computation

De Mathan and Teulié [Monatsh. Math. 143 (2004), pp. 229–245] stated the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<italic>adic Littlewood Conjecture</italic> (<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" … De Mathan and Teulié [Monatsh. Math. 143 (2004), pp. 229–245] stated the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<italic>adic Littlewood Conjecture</italic> (<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula>) in analogy with the classical Littlewood Conjecture. Given a field <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper K"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">K</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb {K}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and an irreducible polynomial <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis t right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with coefficients in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper K"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">K</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb {K}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> admits a natural analogue over function fields, abbreviated to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis t right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> (and to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t"> <mml:semantics> <mml:mi>t</mml:mi> <mml:annotation encoding="application/x-tex">t</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis t right-parenthesis equals t"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p(t)=t</mml:annotation> </mml:semantics> </mml:math> </inline-formula>). In this paper, an explicit counterexample to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis t right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is found over fields of characteristic 5. Furthermore, an infinite family of Laurent series is described that is conjectured to disprove <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis t right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> over all fields of odd characteristic. This fills a gap left by a breakthrough paper from Adiceam, Nesharim and Lunnon [Duke Math. J. 170 (2021), pp. 2371–2419] in which they conjecture <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t"> <mml:semantics> <mml:mi>t</mml:mi> <mml:annotation encoding="application/x-tex">t</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> does not hold over all fields of characteristic <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p identical-to 3 mod 4"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>≡</mml:mo> <mml:mn>3</mml:mn> <mml:mspace width="0.667em"/> <mml:mi>mod</mml:mi> <mml:mspace width="thinmathspace"/> <mml:mspace width="thinmathspace"/> <mml:mn>4</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p\equiv 3\mod 4</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and prove this in the case <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p equals 3"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p=3</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Supported by computational evidence, this provides a complete picture on how <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis t right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is expected to behave over all fields with characteristic not equal to 2. Furthermore, the counterexample to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t"> <mml:semantics> <mml:mi>t</mml:mi> <mml:annotation encoding="application/x-tex">t</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper C"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">LC</mml:annotation> </mml:semantics> </mml:math> </inline-formula> over fields of characteristic 3 found by Adiceam, Nesharim and Lunnon is proven to also hold over fields of characteristic 7 and 11, which provides further evidence to the aforementioned conjecture. Following previous work in this area, these results are achieved by building upon combinatorial arguments and are computer assisted. A new feature of the present work is the development of an efficient algorithm (implemented in Python) that combines the theory of automatic sequences with Diophantine approximation over function fields. This algorithm is expected to be useful for further research around Littlewood-type conjectures over function fields.

On isolated subsemigroups of order-decreasing transformation semigroups

2025-06-24

Melek Yağcı , Hayrullah Ayık | Hacettepe Journal of Mathematics and Statistics

For $n\in \mathbb{N}$, let $\mathcal{D}_{n}$ be the semigroup of all order-decrasing transformations on $X_{n}=\{1,\ldots ,n\}$, under its natural order. In this paper, we determine isolated, completely isolated, and (left/right) convex … For $n\in \mathbb{N}$, let $\mathcal{D}_{n}$ be the semigroup of all order-decrasing transformations on $X_{n}=\{1,\ldots ,n\}$, under its natural order. In this paper, we determine isolated, completely isolated, and (left/right) convex subsemigroups of $\mathcal{D}_{n}$. Furthermore, for $\{ 1\}\neq U\subset X_{n}$ which contains $1$, we find the rank of $\mathcal{D}_{n}[U] =\{ \alpha \in \mathcal{D}_{n} :U\subseteq X_{n} \}$ which is a convex subsemigroup of $\mathcal{D}_{n}$.

Классы унаров, близкие к плоским

2025-06-22

Алексей Михайлович Пряничников | Чебышевский сборник

Данная статья посвящена описанию унаров, удовлетворяющих различным условиям, близким к плоскостности. И.А.Сахаровым было показано, что проективные унары совпадают со свободными и являются копроизведением лучей. Автором ранее были полно-стью описаны плоские … Данная статья посвящена описанию унаров, удовлетворяющих различным условиям, близким к плоскостности. И.А.Сахаровым было показано, что проективные унары совпадают со свободными и являются копроизведением лучей. Автором ранее были полно-стью описаны плоские унары. Данная статья продолжает это направление исследований и даёт полное описание унаров, близких к плоским, а именно: коуниверсально плоских,уравнительно плоских, слабо плоских, главно слабо плоских унаров, унаров без кручения, унаров, удовлетворяющих условию (Е) или (Р), точных, строго точных и регулярных унаров. Показано, что коуниверсально плоские унары совпадают с уравнительно плоскими и являются копроизведением прямых и лучей. Унары, удовлетворяющие условию (Р), плоские, слабо плоские, главно слабо плоские и унары без кручения совпадают и являются копроизведением прямых, лучей и циклов. Точные, строго точные, регулярные унары и унары, удовлетворяющие условию (Е) совпадают и являются в точности унарами, не содержащими цикл.

i-Fitting-Formations on Inverse Semigroups

2025-06-20

Gracinda M. S. Gomes , Ana-Catarina C. Monteiro | Semigroup Forum

Finite complete Rewriting systems and biautomatic structures for Stylic monoids

2025-06-20

Yan Luo , Zhen Jin , Wen Ting Zhang | Journal of Algebra and Its Applications

On minimal conditions in semigroups and biacts

2025-06-20

Craig Miller | Journal of Algebra and Its Applications

The Repetition Threshold for Ternary Rich Words

2025-06-19

James D. Currie , Lucas Mol , Jarkko Peltomäki | The Electronic Journal of Combinatorics

In 2017, Vesti proposed the problem of determining the repetition threshold for infinite rich words, i.e., for infinite words in which all factors of length $n$ contain $n$ distinct nonempty … In 2017, Vesti proposed the problem of determining the repetition threshold for infinite rich words, i.e., for infinite words in which all factors of length $n$ contain $n$ distinct nonempty palindromic factors. In 2020, Currie, Mol, and Rampersad proved a conjecture of Baranwal and Shallit that the repetition threshold for binary rich words is $2 + \sqrt{2}/2$. In this paper, we prove a structure theorem for $16/7$-power-free ternary rich words. Using the structure theorem, we deduce that the repetition threshold for ternary rich words is $1 + 1/(3 - \mu) \approx 2.25876324$, where $\mu$ is the unique real root of the polynomial $x^3 - 2x^2 - 1$.

On decidability of problems involving insertion operations

2025-06-14

Óscar H. Ibarra , Ian McQuillan | Natural Computing

Substitutions and Cantor real numeration systems

2025-06-02

Émilie Charlier , Célia Cisternino , Zuzana Masáková +1 more

History-deterministic Parikh Automata

2025-06-02

Enzo Erlich , Mario Grobler , Shibashis Guha +3 more | ACM Transactions on Computational Logic

Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of … Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable properties of finite automata. Deterministic Parikh automata are strictly weaker than nondeterministic ones, but enjoy better closure and algorithmic properties. This state of affairs motivates the study of intermediate forms of nondeterminism. Here, we investigate history-deterministic Parikh automata, i.e., automata whose nondeterminism can be resolved on the fly. This restricted form of nondeterminism is well-suited for applications which classically call for determinism, e.g., solving games and composition. We show that history-deterministic Parikh automata are strictly more expressive than deterministic ones, incomparable to unambiguous ones, and enjoy almost all of the closure properties of deterministic automata. Finally, we investigate the complexity of resolving nondeterminism in history-deterministic Parikh automata.

Monochromatic arithmetic progressions in the Fibonacci, Thue–Morse, and Rudin–Shapiro words

2025-06-01

G. C. Joshi , D. M. Rust | Theoretical Computer Science

The word problem for Hecke–Kiselman monoids of type $$A_n$$ and $$\widetilde{A}_n$$

2025-05-29

Victoria Lebed

Graph-Theoretic Characterizations of Quasi-Idempotents in Full Order-Preserving Transformation Semigroup

2025-05-28

Eze C , A. T. Imam , M. Balarabe +1 more | Deleted Journal

This paper presents a digraph-theoretic extension of the characterization of quasi-idempotent in the semigroup On of full order-preserving transformations on a finite chain. Building on earlier results . that describe … This paper presents a digraph-theoretic extension of the characterization of quasi-idempotent in the semigroup On of full order-preserving transformations on a finite chain. Building on earlier results . that describe quasi-idempotent as those transformations α ∈ On satisfying α≠α^2=α^4, we provide a novel interpretation using the functional digraphs of such maps. We show that a transformation is quasi-idempotent if and only if each vertex in its associated digraph is either fixed or maps directly into a fixed point, and every non-trivial strongly connected component forms a 2-cycle. Furthermore, we prove that no directed path of the form v1 → v2 → v3 exists where all vertices are non-stationary. These findings offer a new perspective on the structure of On, bridging algebraic properties with graphical structure, and set the stage for visual and computational analysis of quasi-idempotent generation in transformation semigroups.

Pattern Avoiding Permutations Enumerated by Inversions

2025-05-26

Atli Fannar Franklín

Permutations are usually enumerated by size, but new results can be found by enumerating them by inversions instead, in which case one must restrict one's attention to indecomposable permutations. In … Permutations are usually enumerated by size, but new results can be found by enumerating them by inversions instead, in which case one must restrict one's attention to indecomposable permutations. In the style of the seminal paper by Simion and Schmidt, we investigate all combinations of permutation patterns of length at most 3. Comment: Update: Address review comments after submission to DMTCS Update: Copy version for DMTCS

Pattern avoidance in revised ascent sequences

2025-05-26

Robin D. P. Zhou

Generalised power series determined by linear recurrence relations

2025-05-26

Lothar Sebastian Krapp , Salma Kuhlmann , Michele Serra

A remark on the Whitney Broken Circuit Theorem

2025-05-26

Paula M. S. Fialho , Emanuel Juliano , Aldo Procacci

Short Synchronizing Words for Random Automata

2025-05-23

Guillaume Chapuy , Guillem Perarnau

We prove that a uniformly random automaton with $n$ states on a 2-letter alphabet has a synchronizing word of length $O(n^{1/2}\log n)$ with high probability (w.h.p.). That is to say, … We prove that a uniformly random automaton with $n$ states on a 2-letter alphabet has a synchronizing word of length $O(n^{1/2}\log n)$ with high probability (w.h.p.). That is to say, w.h.p. there exists a word $\omega$ of such length, and a state $v_{0}$ , such that $\omega$ sends all states to $v_{0}$ . Prior to this work, the best upper bound was the quasilinear bound $O(n\log^{3}n)$ due to Nicaud [26]. The correct scaling exponent had been subject to various estimates by other authors between $0.5$ and $0.56$ based on numerical simulations, and our result confirms that the smallest one indeed gives a valid upper bound (with a log factor). Our proof introduces the concept of $w$ -trees, for a word $w$ , that is, automata in which the $w$ -transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on $n$ states is a $w$ -tree for some word $w$ of length at most $(1+\epsilon)\log_{2}(n)$ , for any $\epsilon>0$ . The existence of the (random) word $w$ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.

Reduced Words in the Free Product of Groups

2025-05-20

Mark Kleiner

Ergodic properties of concurrent systems

2025-05-19

Samy Abbes , Vincent Jugé

Publisher Correction: The homology of completely simple semigroups

2025-05-12

Benjamin Steinberg

From Context-Free Languages to Mildly Context-Sensitive Languages Complexity Views

2025-05-11

Liliana Cojocaru

The class of context-free languages is the second class in the Chomsky hierarchy, and probably it is the most exciting one. It is easy to be parsed but not trivial, … The class of context-free languages is the second class in the Chomsky hierarchy, and probably it is the most exciting one. It is easy to be parsed but not trivial, it is rich in algebraic and combinatorial properties, it stands at the basis of programming languages, and besides, it provides structural patterns for the so called mildly context-sensitive formalisms used in Natural Language Processing. Usually parsing algorithms for mildly context-sensitive grammars are generalized parsing algorithms for context-free grammars. In this paper we deal with the main parsing algorithms for context-free and mildly context-sensitive grammars, motivated by potential applications in Computational Complexity, Parsing Theory and DNA Computing. These algorithms are based on graphical, combinatorial, or algebraic approaches, on Boolean matrix multiplication techniques and on regular approximations for context-free and mildly context-sensitive languages.

Complexity Results for Some Subclasses of Context-Free Languages

2025-05-11

Liliana Cojocaru

We deal with a normal form for context-free grammars, called Dyck normal form. This normal form is a syntactical restriction of the Chomsky normal form, in which the two nonterminals … We deal with a normal form for context-free grammars, called Dyck normal form. This normal form is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals. This pairwise property, along with several other terminal rewriting conditions, makes it possible to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. As an application we give an alternative proof of the inclusion of the class of even linear languages in the circuit complexity class AC1.

SEMIGROUPS IN WHICH THE RADICAL OF EVERY BI-INTERIOR IDEAL IS A SUBSEMIGROUP

2025-05-10

W. Jantanan , S. Phalasak , S. Tiangtas +1 more

Pretzel monoids

2025-05-09

Daniel J. Heath , Mark Kambites , Nóra Szakács

Products of Nilpotents in Partial Transformation Semigroups using Digraphic Paths and Chains

2025-05-08

Usman Mohammed Yusuf , Abdullahi M. Babayo , Moses Anayo Mbah

In this paper, we investigate the factorization of singular partial self-maps on a finite set into products of the least number of nilpotent elements. This research demonstrates that the semigroup … In this paper, we investigate the factorization of singular partial self-maps on a finite set into products of the least number of nilpotent elements. This research demonstrates that the semigroup of such maps can be expressed within a union of nilpotent-generated sets, specifically up to the third power. Some of our key findings include the determination of the nilpotent rank and the nilpotent depth for these maps, which vary based on whether the set size is even or odd. Additionally, this study surveys the relationship between these results and Stirling numbers, leveraging the Vagner Theorem and digraphic representations. We also examine stable quasi-idempotents, which correspond to specific digraphic paths and chains, providing further insights into the structure of partialtransformation semigroups.

Closing star-free closure

2025-05-06

Thomas Place , Marc Zeitoun

We introduce an operator on classes of regular languages, the star-free closure. Our motivation is to generalize standard results of automata theory within a unified framework. Given an arbitrary input … We introduce an operator on classes of regular languages, the star-free closure. Our motivation is to generalize standard results of automata theory within a unified framework. Given an arbitrary input class $\mathscr {C} $ , the star-free closure operator outputs the least class closed under Boolean operations and language concatenation, and containing all languages of $\mathscr {C} $ as well as all finite languages. We establish several equivalent characterizations of star-free closure: in terms of regular expressions, first-order logic, pure future and future-past temporal logic, and recognition by finite monoids. A key ingredient is that star-free closure coincides with another closure operator, defined in terms of regular operations where Kleene stars are allowed in restricted contexts. A consequence of this first result is that we can decide membership of a regular language in the star-free closure of a class whose separation problem is decidable. Moreover, we prove that separation itself is decidable for the star-free closure of any finite class, and of any class of group languages having itself decidable separation (plus mild additional properties). We actually show decidability of a stronger property, called covering.

О теориях алгебр подмножеств и решёток подпространств в конечных линейных пространствах

2025-05-05

Sergey Mikhailovich Dudakov

В наших предыдущих работах мы видели, что теории фигур и подпространств для бесконечных линейных пространств имеют высокую степень неразрешимости: они допускают интерпретацию элементарной арифметики, а в случае бесконечных фигур - … В наших предыдущих работах мы видели, что теории фигур и подпространств для бесконечных линейных пространств имеют высокую степень неразрешимости: они допускают интерпретацию элементарной арифметики, а в случае бесконечных фигур - даже арифметики второго порядка. В случае конечных линейных пространств эти утверждения конечно же неверны, так как мы можем построить алгоритм, перебирающий все конечные линейные пространства и выдающий все формулы, модель которых нашлась. Следовательно, для конечных линейных пространств теории фигур и подпространств принадлежат классу $\Pi_1$ - дополнений рекурсивно перечислимых множеств. В настоящей работе мы показываем, что эти теории являются полными задачами для класса $\Pi_1$, то есть по"=прежнему неразрешимы и не рекурсивно аксиоматизируемы. For infinite linear spaces, in our previous works, we have shown that theories of figures and subspaces are of high undecidability degree. They allow interpreting elementary arithmetic or second-order arithmetic (for infinite figures). For finite linear spaces, such a claim doesn't hold. It is because we can algorithmically enumerate all finite linear spaces and find all formulas with finite models. So, for finite linear spaces, theories of figures and subspaces are in the class $\Pi_1$. It is the class of problems whose complements are recursively enumerable. In the present paper, we prove that these theories are $\Pi_1$-complete, therefore, they are algorithmically undecidable and not recursively axiomatizable.

Probabilistic input-driven pushdown automata

2025-05-01

Alex Rose , Alexander Okhotin

Maximal Universal Width of an AFA is NP-hard

2025-05-01

John Alajaji , Kai Salomaa

Essential Semigroups and Branching Rules

2025-05-01

A. A. Gornitskii

Combinatorial twists in gl_n Yangians

2025-04-30

Anastasia Doikou

We introduce the special set-theoretic Yang-Baxter algebra and show that it is a Hopf algebra. The associated universal R-matrix is also obtained via an admissible Drinfel'd twist, making the algebra … We introduce the special set-theoretic Yang-Baxter algebra and show that it is a Hopf algebra. The associated universal R-matrix is also obtained via an admissible Drinfel'd twist, making the algebra a quasi-triangular Hopf algebra. The fundamental representation of the universal R-matrix yields the familiar set-theoretic (combinatorial) solutions of the Yang-Baxter equation. We then apply the same Drinfel'd twist to the gl_n Yangian after introducing the augmented Yangian. We show that the augmented Yangian is also a Hopf algebra and we obtain the twisted version of the augmented gl_n Yangian as well as the twisted R-matrix.

View PDF Chat

The converse of the Cowling–Obrechkoff–Thron theorem

2025-04-28

Devon N. Munger , Pietro Paparella