We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference …
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation $P$ coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given $P$ under which we can find a uniquely defined string over either a binary or ternary alphabet having $P$ as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows-Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions.
The power word problem for a group $G$ asks whether an expression $u_1^{x_1} \cdots u_n^{x_n}$, where the $u_i$ are words over a finite set of generators of $G$ and the …
The power word problem for a group $G$ asks whether an expression $u_1^{x_1} \cdots u_n^{x_n}$, where the $u_i$ are words over a finite set of generators of $G$ and the $x_i$ binary encoded integers, is equal to the identity of $G$. It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over $G$). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group $G$ is $NC^1$-many-one reducible to the power word problem for a finite-index subgroup of $G$. For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is $AC^0$-Turing-reducible to the word problem for the free group $F_2$ and the power word problems of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups $\mathcal{C}$ without order two elements, the uniform power word problem in a graph product can be solved in $\mathsf{AC^0(C_=L^{UPowWP(\mathcal{C})})}$, where $UPowWP(\mathcal{C})$ denotes the uniform power word problem for groups from the class $\mathcal{C}$. As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is NP-complete. The present paper is a combination of the two conference papers. In [StoberW22] and previous iterations of this paper our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated previously is true, our proof relies on this additional assumption.
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. …
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the average case behavior. In particular, we establish an upper bound of $n \log n - 1.4005n + o(n)$ comparisons. We also give an exact description of the probability distribution of the length of the chain a given element is inserted into and use it to approximate the average number of comparisons numerically. Moreover, we compute the exact average number of comparisons for $n$ up to 148. Furthermore, we experimentally explore the impact of different decision trees for binary insertion. To conclude, we conduct experiments showing that a slightly different insertion order leads to a better average case and we compare the algorithm to the recent combination with (1,2)-Insertionsort by Iwama and Teruyama.
It is a long-standing open question to determine the minimum number of comparisons S (n) that suffice to sort an array of n elements. Indeed, before this work, S(n) has …
It is a long-standing open question to determine the minimum number of comparisons S (n) that suffice to sort an array of n elements. Indeed, before this work, S(n) has been known only for n ≤ 22 with the exception of n = 16, 17, and 18.
It is a long-standing open question to determine the minimum number of comparisons $S(n)$ that suffice to sort an array of $n$ elements. Indeed, before this work $S(n)$ has been …
It is a long-standing open question to determine the minimum number of comparisons $S(n)$ that suffice to sort an array of $n$ elements. Indeed, before this work $S(n)$ has been known only for $n\leq 22$ with the exception for $n=16$, $17$, and $18$. In this work, we fill that gap by proving that sorting $n=16$, $17$, and $18$ elements requires $46$, $50$, and $54$ comparisons respectively. This fully determines $S(n)$ for these values and disproves a conjecture by Knuth that $S(16) = 45$. Moreover, we show that for sorting $28$ elements at least 99 comparisons are needed. We obtain our result via an exhaustive computer search which extends previous work by Wells (1965) and Peczarski (2002, 2004, 2007, 2012). Our progress is both based on advances in hardware and on novel algorithmic ideas such as applying a bidirectional search to this problem.
In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a …
In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a wide range of papers appeared investigating their peculiar properties. Yet, a complete classification of geodetic graphs is out of reach. In this work we present a program enumerating all geodetic graphs of a given size. Using our program, we succeed to find all geodetic graphs with up to 25 vertices and all regular geodetic graphs with up to 32 vertices. This leads to the discovery of two new infinite families of geodetic graphs.
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference …
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation P coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given P under which we can find a uniquely defined string over either a binary or ternary alphabet having P as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows–Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions.
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the …
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the only geodetic Cayley graphs which occur are odd cycles and complete graphs. In this article we present a series of theoretical results which contribute to a computer search verifying this conjecture for all groups of size up to 1024. The conjecture is also verified theoretically for several infinite families of groups including dihedral and some families of nilpotent groups. Two key results which enable the computer search to reach as far as it does are: if the center of a group has even order, then the conjecture holds (this eliminates all 2-groups from our computer search); if a Cayley graph is geodetic then there are bounds relating the size of the group, generating set and center (which cuts down the number of generating sets which must be searched significantly).
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership …
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership problem, as well as the conjugacy problem, for finite inverse semigroups. The closely related membership problem for finite semigroups has been shown to be PSPACE-complete in the transformation model by Kozen (1977) and NL-complete in the Cayley table model by Jones, Lien, and Laaser (1976). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be PSPACE-complete in the partial bijection model by Jack (2023). Here we present a more detailed analysis of the complexity of the membership and conjugacy problems parametrized by varieties of finite inverse semigroups. We establish dichotomy theorems for the partial bijection model and for the Cayley table model. In the partial bijection model these problems are in NC (resp. NP for conjugacy) for strict inverse semigroups and PSPACE-complete otherwise. In the Cayley table model we obtain general LOGSPACE-algorithms as well as NPOLYLOGTIME upper bounds for Clifford semigroups and LOGSPACE-completeness otherwise. Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is PSPACE-complete even for automata with only two states; the subpower membership problem is in NC for every strict inverse semi-group and PSPACE-complete otherwise; the minimum generating set and the equation satisfiability problems are in NP for varieties of finite strict inverse semigroups and PSPACE-complete otherwise.
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership …
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership problem, as well as the conjugacy problem, for finite inverse semigroups. The closely related membership problem for finite semigroups has been shown to be PSPACE-complete in the transformation model by Kozen (1977) and NL-complete in the Cayley table model by Jones, Lien, and Laaser (1976). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be PSPACE-complete in the partial bijection model by Jack (2023). Here we present a more detailed analysis of the complexity of the membership and conjugacy problems parametrized by varieties of finite inverse semigroups. We establish dichotomy theorems for the partial bijection model and for the Cayley table model. In the partial bijection model these problems are in NC (resp. NP for conjugacy) for strict inverse semigroups and PSPACE-complete otherwise. In the Cayley table model we obtain general LOGSPACE-algorithms as well as NPOLYLOGTIME upper bounds for Clifford semigroups and LOGSPACE-completeness otherwise. Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is PSPACE-complete even for automata with only two states; the subpower membership problem is in NC for every strict inverse semi-group and PSPACE-complete otherwise; the minimum generating set and the equation satisfiability problems are in NP for varieties of finite strict inverse semigroups and PSPACE-complete otherwise.
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the …
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the only geodetic Cayley graphs which occur are odd cycles and complete graphs. In this article we present a series of theoretical results which contribute to a computer search verifying this conjecture for all groups of size up to 1024. The conjecture is also verified theoretically for several infinite families of groups including dihedral and some families of nilpotent groups. Two key results which enable the computer search to reach as far as it does are: if the center of a group has even order, then the conjecture holds (this eliminates all 2-groups from our computer search); if a Cayley graph is geodetic then there are bounds relating the size of the group, generating set and center (which cuts down the number of generating sets which must be searched significantly).
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference …
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation P coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given P under which we can find a uniquely defined string over either a binary or ternary alphabet having P as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows–Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions.
It is a long-standing open question to determine the minimum number of comparisons S (n) that suffice to sort an array of n elements. Indeed, before this work, S(n) has …
It is a long-standing open question to determine the minimum number of comparisons S (n) that suffice to sort an array of n elements. Indeed, before this work, S(n) has been known only for n ≤ 22 with the exception of n = 16, 17, and 18.
In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a …
In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a wide range of papers appeared investigating their peculiar properties. Yet, a complete classification of geodetic graphs is out of reach. In this work we present a program enumerating all geodetic graphs of a given size. Using our program, we succeed to find all geodetic graphs with up to 25 vertices and all regular geodetic graphs with up to 32 vertices. This leads to the discovery of two new infinite families of geodetic graphs.
The power word problem for a group $G$ asks whether an expression $u_1^{x_1} \cdots u_n^{x_n}$, where the $u_i$ are words over a finite set of generators of $G$ and the …
The power word problem for a group $G$ asks whether an expression $u_1^{x_1} \cdots u_n^{x_n}$, where the $u_i$ are words over a finite set of generators of $G$ and the $x_i$ binary encoded integers, is equal to the identity of $G$. It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over $G$). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group $G$ is $NC^1$-many-one reducible to the power word problem for a finite-index subgroup of $G$. For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is $AC^0$-Turing-reducible to the word problem for the free group $F_2$ and the power word problems of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups $\mathcal{C}$ without order two elements, the uniform power word problem in a graph product can be solved in $\mathsf{AC^0(C_=L^{UPowWP(\mathcal{C})})}$, where $UPowWP(\mathcal{C})$ denotes the uniform power word problem for groups from the class $\mathcal{C}$. As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is NP-complete. The present paper is a combination of the two conference papers. In [StoberW22] and previous iterations of this paper our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated previously is true, our proof relies on this additional assumption.
It is a long-standing open question to determine the minimum number of comparisons $S(n)$ that suffice to sort an array of $n$ elements. Indeed, before this work $S(n)$ has been …
It is a long-standing open question to determine the minimum number of comparisons $S(n)$ that suffice to sort an array of $n$ elements. Indeed, before this work $S(n)$ has been known only for $n\leq 22$ with the exception for $n=16$, $17$, and $18$. In this work, we fill that gap by proving that sorting $n=16$, $17$, and $18$ elements requires $46$, $50$, and $54$ comparisons respectively. This fully determines $S(n)$ for these values and disproves a conjecture by Knuth that $S(16) = 45$. Moreover, we show that for sorting $28$ elements at least 99 comparisons are needed. We obtain our result via an exhaustive computer search which extends previous work by Wells (1965) and Peczarski (2002, 2004, 2007, 2012). Our progress is both based on advances in hardware and on novel algorithmic ideas such as applying a bidirectional search to this problem.
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference …
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation $P$ coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given $P$ under which we can find a uniquely defined string over either a binary or ternary alphabet having $P$ as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows-Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions.
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. …
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the average case behavior. In particular, we establish an upper bound of $n \log n - 1.4005n + o(n)$ comparisons. We also give an exact description of the probability distribution of the length of the chain a given element is inserted into and use it to approximate the average number of comparisons numerically. Moreover, we compute the exact average number of comparisons for $n$ up to 148. Furthermore, we experimentally explore the impact of different decision trees for binary insertion. To conclude, we conduct experiments showing that a slightly different insertion order leads to a better average case and we compare the algorithm to the recent combination with (1,2)-Insertionsort by Iwama and Teruyama.
The quotient groups Qn(G) =GnGn+i of the lower central series G = G1 D G, D G, D * * of a finitely generated group G are finitely generated abelian …
The quotient groups Qn(G) =GnGn+i of the lower central series G = G1 D G, D G, D * * of a finitely generated group G are finitely generated abelian groups. Our object is to develop an algorithm for the calculation of Qn from any given finite presentation of G. As a preliminary step, the special case of a free group X is considered. It is known [2], [7] that, for a free group X of rank q, the group Qn(X) is a free abelian group whose rank is the Witt number 0b,(q), and a basis for QJ(X) has been exhibited by M. Hall [42]. Our approach is somewhat different in that we construct, by means of the free differential calculus, a basis for the dual group Qn* = Hom [QnJ]. The corresponding dual basis of Q. is not the same as the Hall basis, although it bears a superficial resemblance to it. In the course of this construction we re-prove Witt's result [7] that the elements of Xn are just those for which the non-constant terms of the Magnus expansion are all of degree at least n, in short, that the lower central groups coincide with the dimension groups of Magnus [2]. Further, we derive a complete set of finite identities for the coefficients in the Magnus expansion of an element of X. The algorithm for Qn(G) is to be found in the last section. The authors wish to thank Julian Brody for his help in simplifying the arguments, and for selection of the example in ?4.
For some text algorithms, the real measure for the complexity analysis is not the string itself but its structure stored in its prefix table or equivalently border table. In this …
For some text algorithms, the real measure for the complexity analysis is not the string itself but its structure stored in its prefix table or equivalently border table. In this paper, we define the combinatorial class of prefix lists, namely a sequence of integers together with their size, and an injection ψ from the class of prefix tables to the class of prefix lists. We call a valid prefix list the image by ψ of a prefix table. In particular, we describe algorithms converting a prefix/border table to a prefix list and inverse linear algorithms from computing from a prefix list L = ψ ( P ) two words respectively in a minimal size alphabet and on a maximal size alphabet with P as prefix table. We then give a new upper bound on the number of prefix tables for strings of length n (on any alphabet) which is of order (1 + ϕ) n (with $\varphi=\frac{1+\sqrt{5}}{2}$ the golden mean) and also present a corresponding lower bound.
A degenerate or indeterminate string on an alphabet Σ is a sequence of non-empty subsets of Σ. Given a degenerate string t of length n and its Burrows–Wheeler transform we …
A degenerate or indeterminate string on an alphabet Σ is a sequence of non-empty subsets of Σ. Given a degenerate string t of length n and its Burrows–Wheeler transform we present a new method for searching for a degenerate pattern of length m in t running in O(mn) time on a constant size alphabet Σ. Furthermore, it is a hybrid pattern matching technique that works on both regular and degenerate strings. A degenerate string is said to be conservative if its number of non-solid letters is upper-bounded by a fixed positive constant q; in this case we show that the search time complexity is O(qm2) for counting the number of occurrences and O(qm2+occ) for reporting the found occurrences where occ is the number of occurrences of the pattern in t. Experimental results show that our method performs well in practice.
Given a string of characters, the Burrows-Wheeler Transform rearranges the characters in it so as to produce another string of the same length which is more amenable to compression techniques …
Given a string of characters, the Burrows-Wheeler Transform rearranges the characters in it so as to produce another string of the same length which is more amenable to compression techniques such as move to front, run-length encoding, and entropy encoders. We present a variant of the transform which gives rise to similar or better compression value, but, unlike the original, the transform we present is bijective, in that the inverse transformation exists for all strings. Our experiments indicate that using our variant of the transform gives rise to better compression ratio than the original Burrows-Wheeler transform. We also show that both the transform and its inverse can be computed in linear time and consuming linear storage.
Abstract Given a group G and a finite generating set G , we take p G : G → Z to be the function which counts the number of geodesics …
Abstract Given a group G and a finite generating set G , we take p G : G → Z to be the function which counts the number of geodesics for each group element g . This generalizes Pascal's triangle. We compute p G for word hyperbolic and describe generic behaviour in abelian groups.
In this paper, we shall first describe the theory of distance-regular graphs and then apply it to the classification of Moore graphs. The object of the paper is to prove …
In this paper, we shall first describe the theory of distance-regular graphs and then apply it to the classification of Moore graphs. The object of the paper is to prove that there are no Moore graphs (other than polygons) of diameter ≥ 3. An independent proof of this result has been given by Barmai and Ito(1). Taken with the result of (4), this shows that the only possible Moore graphs are the following:
We prove that the groups presented by finite convergent monadic rewriting systems with generators of finite order are exactly the free products of finitely many finite groups, thereby confirming Gilman’s …
We prove that the groups presented by finite convergent monadic rewriting systems with generators of finite order are exactly the free products of finitely many finite groups, thereby confirming Gilman’s conjecture in a special case. We also prove that the finite cyclic groups of order at least three are the only finite groups admitting a presentation by more than one finite convergent monadic rewriting system (up to relabelling), and these admit presentation by exactly two such rewriting systems.
We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the …
We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are $\mathbf {P}$-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is $\mathbf {NP}$-complete.
In this work we introduce a new succinct variant of the word problem in a finitely generated group G, which we call the power word problem: the input word may …
In this work we introduce a new succinct variant of the word problem in a finitely generated group G, which we call the power word problem: the input word may contain powers p^x, where p is a finite word over generators of G and x is a binary encoded integer. The power word problem is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over G). The main result of the paper states that the power word problem for a finitely generated free group F is AC^0-Turing-reducible to the word problem for F. Moreover, the following hardness result is shown: For a wreath product G Wr Z, where G is either free of rank at least two or finite non-solvable, the power word problem is complete for coNP. This contrasts with the situation where G is abelian: then the power word problem is shown to be in TC^0.
This paper describes a new approach to the problem of generating the class of all geodetic graphs homeomorphic to a given geodetic one. An algorithmic procedure is elaborated to carry …
This paper describes a new approach to the problem of generating the class of all geodetic graphs homeomorphic to a given geodetic one. An algorithmic procedure is elaborated to carry out a systematic finding of such a class of graphs. As a result, the enumeration of the class of geodetic graphs homeomorphic to certain Moore graphs has been performed.
We call a graph k-geodetic, for some [Formula: see text], if it is connected and between any two vertices there are at most k geodesics. It is shown that any …
We call a graph k-geodetic, for some [Formula: see text], if it is connected and between any two vertices there are at most k geodesics. It is shown that any hyperbolic group with a k-geodetic Cayley graph is virtually-free. Furthermore, in such a group the centralizer of any infinite order element is an infinite cyclic group. These results were known previously only in the case that [Formula: see text]. A key tool used to develop the theorem is a new graph theoretic result concerning “ladder-like structures” in a k-geodetic graph.
We prove that the conjugacy problem in a large and natural class of subgroups of right-angled Artin groups can be solved in linear time. This class of subgroups has been …
We prove that the conjugacy problem in a large and natural class of subgroups of right-angled Artin groups can be solved in linear time. This class of subgroups has been previously studied by Crisp and Wiest, and independently by Haglund and Wise, as fundamental groups of compact special cube complexes.
Computing normal forms in groups (or monoids) is in general harder than solving the word problem (equality testing). However, normal form computation has a much wider range of applications. It …
Computing normal forms in groups (or monoids) is in general harder than solving the word problem (equality testing). However, normal form computation has a much wider range of applications. It is therefore interesting to investigate the complexity of computing normal forms for important classes of groups.
For Coxeter groups we show that the following algorithmic tasks can be solved by a deterministic Turing machine using logarithmic work space, only: 1. Compute the length of any geodesic normal form. 2. Compute the set of letters occurring in any geodesic normal form. 3. Compute the Parikh-image of any geodesic normal form in case that all defining relations have even length (i.e., in even Coxeter groups.) 4. For right-angled Coxeter groups we can do actually compute the short length normal form in logspace. (Note that short length normal forms are geodesic.)
Next, we apply the results to right-angled Artin groups. They are also known as free partially commutative groups or as graph groups. As a consequence of our result on right-angled Coxeter groups we show that shortlex normal forms in graph groups can be computed in logspace, too. Graph groups play an important role in group theory, and they have a close connection to concurrency theory. As an application of our results we show that the word problem for free partially commutative inverse monoids is in logspace. This result generalizes a result of Ondrusch and the third author on free inverse monoids. Concurrent systems which are deterministic and co-deterministic can be studied via inverse monoids.
Journal Article MOORE GEOMETRIES AND RANK 3 GROUPS HAVING μ=1 Get access WILLIAM M. KANTOR WILLIAM M. KANTOR University of OregonEugene, Oregon 97403 U.S.A. Search for other works by this …
Journal Article MOORE GEOMETRIES AND RANK 3 GROUPS HAVING μ=1 Get access WILLIAM M. KANTOR WILLIAM M. KANTOR University of OregonEugene, Oregon 97403 U.S.A. Search for other works by this author on: Oxford Academic Google Scholar The Quarterly Journal of Mathematics, Volume 28, Issue 3, September 1977, Pages 309–328, https://doi.org/10.1093/qmath/28.3.309 Published: 01 September 1977 Article history Received: 13 November 1975 Revision received: 24 September 1976 Published: 01 September 1977
This note treats the existence of connected, undirected graphs homogeneous of degree d and of diameter k, having a number of nodes which is maximal according to a certain definition. …
This note treats the existence of connected, undirected graphs homogeneous of degree d and of diameter k, having a number of nodes which is maximal according to a certain definition. For k = 2 unique graphs exist for d = 2,3,7 and possibly for d = 57 (which is undecided), but for no other degree. For k = 3 a graph exists only for d = 2. The proof exploits the characteristic roots and vectors of the adjacency matrix (and its principal submatrices) of the graph.