Search

The power word problem for a group G asks whether an expression u 1 x 1 ⋯ 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 uNC 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 C without order two elements, the uniform power word problem in a graph product can be solved in AC 0 [ C = L UPowWP (C) ] , where UPowWP (C) denotes the uniform power word problem for groups from the class 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 (Lohrey and Weiß 2019b, Stober and Weiß 2022a). In Stober and Weiß (2022a) 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 in Stober and Weiß (2022a) is true, our proof relies on this additional assumption. [ABSTRACT FROM AUTHOR]

The computational complexity of the word problem in HNN-extension of groups is studied. HNN-extension is a fundamental construction in combinatorial group theory. It is shown that the word problem for an ascending HNN-extension of a group H is logspace reducible to the so-called compressed word problem for H. The main result of the paper states that the word problem for an HNN-extension of a hyperbolic group H with cyclic associated subgroups can be solved in polynomial time. This result can be easily extended to fundamental groups of graphs of groups with hyperbolic vertex groups and cyclic edge groups. [ABSTRACT FROM AUTHOR]

We prove that the power word problem for certain metabelian subgroups of G L (2 , ℂ) (including the solvable Baumslag–Solitar groups BS (1 , q) = 〈 a , t | t a t − 1 = a q 〉) belongs to the circuit complexity class T C 0 . In the power word problem, the input consists of group elements g 1 , ... , g d and binary encoded integers n 1 , ... , n d and it is asked whether g 1 n 1 ⋯ g d n d = 1 holds. Moreover, we prove that the knapsack problem for BS (1 , q) is N P -complete. In the knapsack problem, the input consists of group elements g 1 , ... , g d , h and it is asked whether the equation g 1 x 1 ⋯ g d x d = h has a solution in ℕ d . For the more general case of a system of so-called exponent equations, where the exponent variables x i can occur multiple times, we show that solvability is undecidable for BS (1 , q). [ABSTRACT FROM AUTHOR]

A knapsack equation in a group G is an equation of the form g 1 x 1 ⋯ g k x k = g where g 1 , ... , g k , g are elements of G and x 1 , ... , x k are variables that take values in the natural numbers. We study the class of groups G for which all knapsack equations have effectively semilinear solution sets. We show that the following group constructions preserve effective semilinearity: graph products, amalgamated free products with finite amalgamated subgroups, HNN-extensions with finite associated subgroups, and finite extensions. Moreover, we study a complexity measure, called magnitude, of the resulting semilinear solution sets. More precisely, we are interested in the growth of the magnitude in terms of the length of the knapsack equation (measured in number of generators). We investigate how this growth changes under the above group operations. [ABSTRACT FROM AUTHOR]

The definition of $\text {k}^{th}$ -order empirical entropy of strings is extended to node-labelled binary trees: A notion of $\text {k}^{th}$ -order empirical entropy for node-labelled binary trees is proposed that is able to capture regularities in both labels and structure of a tree. A suitable binary encoding of tree straight-line programs (that have been used for grammar-based tree compression before) is shown to yield binary tree encodings of size bounded by the $\text {k}^{th}$ -order empirical entropy plus some lower order terms. This result is then extended from node-labelled binary trees to node-labelled unranked trees. This generalizes recent results for grammar-based string compression to grammar-based tree compression. Additionally, experimental results with real XML document trees are presented, in which the proposed notion of $\text {k}^{th}$ -order empirical tree entropy is computed and compared to the performance of grammar-based tree compressors for those XML document trees. [ABSTRACT FROM AUTHOR]

A family of tree automata of size n is presented such that the size of the largest common prefix (lcp) tree of all accepted trees is exponential in n. Moreover, it is shown that this prefix tree is not compressible via DAGs (directed acyclic graphs) or tree straight-line programs. We also show that determining whether or not the lcp trees of two given tree automata are equal is coNP-complete; the result holds even for deterministic bottom-up tree automata accepting finite tree languages. These results are in sharp contrast to the case of context-free string grammars. [ABSTRACT FROM AUTHOR]

Recently knapsack problems have been generalized from the integers to arbitrary finitely generated groups. The knapsack problem for a finitely generated group G is the following decision problem: given a tuple (g , g 1 , ... , g k) of elements of G , are there natural numbers n 1 , ... , n k ∈ N such that g = g 1 n 1 ⋯ g k n k holds in G ? Myasnikov, Nikolaev, and Ushakov proved that for every (Gromov-)hyperbolic group, the knapsack problem can be solved in polynomial time. In this paper, the precise complexity of the knapsack problem for hyperbolic group is determined: for every hyperbolic group G , the knapsack problem belongs to the complexity class LogCFL , and it is LogCFL -complete if G contains a free group of rank two. Moreover, it is shown that for every hyperbolic group G and every tuple (g , g 1 , ... , g k) of elements of G the set of all (n 1 , ... , n k) ∈ N k such that g = g 1 n 1 ⋯ g k n k in G is semilinear and a semilinear representation where all integers are of size polynomial in the total geodesic length of the g , g 1 , ... , g k can be computed. Groups with this property are also called knapsack-tame. This enables us to show that knapsack can be solved in LogCFL for every group that belongs to the closure of hyperbolic groups under free products and direct products with Z. [ABSTRACT FROM AUTHOR]

We introduce forest straight-line programs (FSLPs for short) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative and/or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees. An extended abstract of this paper appeared in Gascóon et al. (2018). [ABSTRACT FROM AUTHOR]

Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labeled with powers x n for binary encoded numbers n. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to c o R N C 2 , which generalizes a corresponding result for (standard) skew circuits. Two applications of this result are presented: (i) Equivalence of higher-dimensional straight-line programs can be tested in c o R N C 2 ; this result is even new in the one-dimensional case, where the straight-line programs produce words. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products of finitely generated abelian groups belongs to c o R N C 2 . Using the Magnus embedding, it follows that the compressed word problem for a free metabelian group belongs to c o R N C 2 . [ABSTRACT FROM AUTHOR]

With its ability to detect, identify and, if applicable, recover from occurred faults, online-diagnosis can help achieving fault-tolerant systems. A sound decision on an occurred fault is the foundation for fault-specific recovery actions. For this, typically a large amount of data has to be analyzed and evaluated. A diagnostic process implemented on a distributed system needs to communicate all those data among the network which is an expensive affair in terms of communication resources and time. In this paper we present an architecture for a distributed online-diagnosis system with real time constraints that supports data compression to reduce the communication time. We further present a library of lossy compression methods with guaranteed compression ratios that are suitable for real time purposes. [ABSTRACT FROM AUTHOR]

It is shown that the subgroup membership problem for a virtually free group can be decided in polynomial time when all group elements are represented by so-called power words, i.e., words of the form p1z1p2z2⋯pkzk\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$p_1^{z_1} p_2^{z_2} \cdots p_k^{z_k}$$\end{document}. Here the pi\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$p_i$$\end{document} are explicit words over the generating set of the group and all zi\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$z_i$$\end{document} are binary encoded integers. As a corollary, it follows that the subgroup membership problem for the matrix group GL(2,Z)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\textsf{GL}(2,\mathbb {Z})$$\end{document} can be decided in polynomial time when elements of GL(2,Z)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\textsf{GL}(2,\mathbb {Z})$$\end{document} are represented by matrices with binary encoded integers. For the same input representation, it also shown that one can compute in polynomial time the index of a given finitely generated subgroup of GL(2,Z)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\textsf{GL}(2,\mathbb {Z})$$\end{document}. [ABSTRACT FROM AUTHOR]

A linear space data structure for grammar-compressed trees is presented which allows to carry out tree traversal operations and subtree equality checks in constant time. A traversal step consists of moving to the parent or to the ith child of a node. [ABSTRACT FROM AUTHOR]

We study the circuit evaluation problem (also known as the compressed word problem) for finitely generated linear groups. The best upper bound for this problem is coRP (the complements of problems in randomized polynomial time), which is shown by a reduction to polynomial identity testing for arithmetic circuits. Conversely, the compressed word problem for the linear group SL3(Z) is equivalent to polynomial identity testing. In the paper, we show that the compressed word problem for every finitely generated nilpotent group is in DET ⊆ NC2.Within the larger class of polycyclic groups we find examples where the compressed word problem is at least as hard as polynomial identity testing for skew arithmetic circuits. It is a major open problem, whether polynomial identity testing for skew arithmetic circuits can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical NP-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs to the class LogCFL (a subclass of P) if the graph group can be built up from the trivial group using the operations of free product and direct product with $\mathbb {Z}$ . In all other cases, the knapsack problem is NP-complete. [ABSTRACT FROM AUTHOR]

We study the complexity of algorithmic problems for matrices that are represented by multi-terminal decision diagrams (MTDD). These are a variant of ordered decision diagrams, where the terminal nodes are labeled with arbitrary elements of a semiring (instead of 0 and 1). A simple example shows that the product of two MTDD-represented matrices cannot be represented by an MTDD of polynomial size. To overcome this deficiency, we extended MTDDs to + MTDDs by allowing componentwise symbolic addition of variables (of the same dimension) in rules. It is shown that accessing an entry, equality checking, matrix multiplication, and other basic matrix operations can be solved in polynomial time for + MTDD-represented matrices. On the other hand, testing whether the determinant of a MTDD-represented matrix vanishes is P S P A C E-complete, and the same problem is N P-complete for + MTDD-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is # P-complete. [ABSTRACT FROM AUTHOR]

A simple linear-time algorithm for constructing a linear context-free tree grammar of size O ( r g + r g log ⁡ ( n / r g ) ) for a given input tree T of size n is presented, where g is the size of a minimal linear context-free tree grammar for T , and r is the maximal rank of symbols in T (which is a constant in many applications). This is the first example of a grammar-based tree compression algorithm with a good, i.e. logarithmic in terms of the size of the input tree, approximation ratio. The analysis of the algorithm uses an extension of the recompression technique from strings to trees. [ABSTRACT FROM AUTHOR]

Unranked node-labeled trees can be represented using their minimal dag (directed acyclic graph). For XML this achieves high compression ratios due to their repetitive mark up. Unranked trees are often represented through first child/next sibling (fcns) encoded binary trees. We study the difference in size (= number of edges) of minimal dag versus minimal dag of the fcns encoded binary tree. One main finding is that the size of the dag of the binary tree can never be smaller than the square root of the size of the minimal dag, and that there are examples that match this bound. We introduce a new combined structure, the hybrid dag, which is guaranteed to be smaller than (or equal in size to) both dags. Interestingly, we find through experiments that last child/previous sibling encodings are much better for XML compression via dags, than fcns encodings. We determine the average sizes of unranked and binary dags over a given set of labels (under uniform distribution) in terms of their exact generating functions, and in terms of their asymptotical behavior. [ABSTRACT FROM AUTHOR]

It is shown that membership in rational subsets of wreath products H ≀ V with H a finite group and V a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product Z ≀ Z with an undecidable membership problem. [ABSTRACT FROM AUTHOR]

It is shown that there exist d, ℓ ≥ 3 and a sequence C1, ..., Cℓ of cyclic subgroups of the d-dimensional unitriangluar matrix group over ℤ (which is finitely generated nilpotent) such that membership in the product C1 C2 ⋯ Cℓ is undecidable. [ABSTRACT FROM AUTHOR]

Abstract: XML tree structures can conveniently be represented using ordered unranked trees. Due to the repetitiveness of XML markup these trees can be compressed effectively using dictionary-based methods, such as minimal directed acyclic graphs (DAGs) or straight-line context-free (SLCF) tree grammars. While minimal SLCF tree grammars are in general smaller than minimal DAGs, they cannot be computed in polynomial time unless . Here, we present a new linear time algorithm for computing small SLCF tree grammars, called TreeRePair, and show that it greatly outperforms the best known previous algorithm BPLEX. TreeRePair is a generalization to trees of Larsson and Moffat's RePair string compression algorithm. SLCF tree grammars can be used as efficient memory representations of trees. Using TreeRePair, we are able to produce the smallest queryable memory representation of ordered trees that we are aware of. Our investigations over a large corpus of commonly used XML documents show that tree traversals over TreeRePair grammars are 14 times slower than over pointer structures and 5 times slower than over succinct trees, while memory consumption is only 1/43 and 1/6, respectively. With respect to file compression we are able to show that a Huffman-based coding of TreeRePair grammars gives compression ratios comparable to the best known XML file compressors. [Copyright &y& Elsevier]

One-counter automata (OCA) are pushdown automata which operate only on a unary stack alphabet. We study the computational complexity of model checking computation tree logic (CTL) on transition systems induced by OCA. A PSPACE upper bound is inherited from the modal μ-calculus for this problem proved by Serre. First, we analyze the periodic behavior of CTL over OCA and derive a model checking algorithm whose running time is exponential only in the number of control locations and a syntactic notion of the formula that we call leftward until depth. In particular, model checking fixed OCA against CTL formulas with a fixed leftward until depth is in P. This generalizes a corresponding recent result of Göller, Mayr, and To for the expression complexity of CTL's fragment EF. Second, we prove that already over some fixed OCA, CTL model checking is PSPACE-hard, i.e., expression complexity is PSPACE-hard. Third, we show that there already exists a fixed CTL formula for which model checking of OCA is PSPACE-hard, i.e., data complexity is PSPACE-hard as well. To obtain the latter result, we employ two results from complexity theory: (i) Converting a natural number in Chinese remainder presentation into binary presentation is in logspace-uniform NC¹ and (ii) PSPACE is AC0-serializable. We demonstrate that our approach can be used to obtain further results. We show that model checking CTL's fragment EF over OCA is hard for PNP, thus establishing a matching lower bound. Moreover, we show that the following problem is hard for PSPACE: Given a one-counter Markov decision process, a set of target states with counter value zero each, and an initial state, to decide whether the probability that the initial state will eventually reach one of the target states is arbitrarily close to 1. This improves a recently proved lower bound for every level of the boolean hierarchy shown by Brázdil et al. Finally, we prove that there is a fixed CTL formula for which model checking 2-clock timed automata is PSPACE-hard, generalizing a PSPACE-hardness result for the combined complexity by Laroussinie, Markey, and Schnoebelen. [ABSTRACT FROM AUTHOR]

Abstract: The computational complexity of the isomorphism problem for regular trees, regular linear orders, and regular words is analyzed. A tree is regular if it is isomorphic to the prefix order on a regular language. In case regular languages are represented by NFAs (DFAs), the isomorphism problem for regular trees turns out to be -complete (resp. -complete). In case the input automata are acyclic NFAs (acyclic DFAs), the corresponding trees are (succinctly represented) finite trees, and the isomorphism problem turns out to be -complete (resp. -complete). A linear order is regular if it is isomorphic to the lexicographic order on a regular language. A polynomial time algorithm for the isomorphism problem for regular linear orders (and even regular words, which generalize the latter) given by DFAs is presented. This solves an open problem by Ésik and Bloom. Similar techniques can be used to show that one can check in polynomial time whether a given regular linear order has a non-trivial automorphism. This improves a recent decidability result of Kuske. [Copyright &y& Elsevier]

It is shown that the compressed word problem of a graph product of finitely generated groups is polynomial time Turing-reducible to the compressed word problems of the vertex groups. A direct corollary of this result is that the word problem for the automorphism group of a right-angled Artin group or a right-angled Coxeter group can be solved in polynomial time. Moreover, it is shown that a restricted variant of the simultaneous compressed conjugacy problem is polynomial time Turing-reducible to the same problem for the vertex groups. A direct corollary of this result is that the word problem for the outer automorphism group of a right-angled Artin group or a right-angled Coxeter group can be solved in polynomial time. Finally, it is shown that the compressed variant of the ordinary conjugacy problem can be solved in polynomial time for right-angled Artin groups. [ABSTRACT FROM AUTHOR]

Abstract: Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, polynomial time algorithms are presented for testing whether a given (i) nondeterministic tree automaton or (ii) nondeterministic tree automaton with sibling-constraints or (iii) nondeterministic tree walking automaton, accepts a tree represented by a linear straight-line context-free tree grammar. It is also shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size. [Copyright &y& Elsevier]

Abstract: Hierarchical graph definitions allow a modular description of structures using modules for the specification of repeated substructures. Beside this modularity, hierarchical graph definitions allow us to specify structures of exponential size using polynomial size descriptions. In many cases, this succinctness increases the computational complexity of decision problems when input structures are defined hierarchically. In this paper, the model-checking problem for first-order logic (FO), monadic second-order logic (MSO), and second-order logic (SO) on hierarchically defined input structures is investigated. It is shown that in general these model-checking problems are exponentially harder than their non-hierarchical counterparts, where the input structures are given explicitly. As a consequence, several new complete problems for the levels of the polynomial time hierarchy and the exponential time hierarchy are obtained. Based on classical results of Gaifman and Courcelle, two restrictions on the structure of hierarchical graph definitions that lead to more efficient model-checking algorithms are presented. [Copyright &y& Elsevier]

It is shown that the compressed word problem for an HNN-extension 〈 H, t∣ t at= ϕ( a) ( a∈ A)〉 with A finite is polynomial time Turing-reducible to the compressed word problem for the base group H. An analogous result for amalgamated free products is shown as well. [ABSTRACT FROM AUTHOR]

Abstract: Tight connections between leaf languages and strings compressed by straight-line programs (SLPs) are established. It is shown that the compressed membership problem for a language L is complete for the leaf language class defined by L via logspace machines. A more difficult variant of the compressed membership problem for L is shown to be complete for the leaf language class defined by L via polynomial time machines. As a corollary, it is shown that there exists a fixed linear visibly pushdown language for which the compressed membership problem is PSPACE-complete. For XML languages, it is shown that the compressed membership problem is coNP-complete.Furthermore it is shown that the embedding problem for SLP-compressed strings is hard for PP (probabilistic polynomial time). [Copyright &y& Elsevier]

In this paper we show that membership in finitely generated submonoids is undecidable for the free metabelian group of rank 2 and for the wreath product ℤ ≀(ℤ×ℤ). We also show that subsemimodule membership is undecidable for finite rank free (ℤ×ℤ)-modules. The proof involves an encoding of Turing machines via tilings. We also show that rational subset membership is undecidable for two-dimensional lamplighter groups. [ABSTRACT FROM AUTHOR]

Hierarchical graph definitions allow a modular description of graphs using modules for the specification of repeated substructures. Beside this modularity, hierarchical graph definitions also allow to specify graphs of exponential size using polynomial size descriptions. In many cases, this succinctness increases the computational complexity of decision problems. In this paper, the model-checking problem for the modal μ-calculus and (monadic) least fixpoint logic on hierarchically defined input graphs is investigated. In order to analyze the modal μ-calculus, parity games on hierarchically defined input graphs are investigated. Precise upper and lower complexity bounds are derived. A restriction on hierarchical graph definitions that leads to more efficient model-checking algorithms is presented. [ABSTRACT FROM AUTHOR]

Membership problems for compressed strings in regular languages are investigated. Strings are represented by straight-line programs, i.e., context-free grammars that generate exactly one string. For the representation of regular languages, various formalisms with different degrees of succinctness (e.g., suitably extended regular expressions, hierarchical automata) are considered. Precise complexity bounds are derived. Among other results, it is shown that the compressed membership problem for regular expressions with intersection is PSPACE-complete. This solves an open problem of Plandowski and Rytter. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we show that the membership problems for finitely generated submonoids and for rational subsets are recursively equivalent for groups with two or more ends. [Copyright &y& Elsevier]

Free partially commutative inverse monoids are investigated. As in the case of free partially commutative monoids or groups ( trace monoids or graph groups), free partially commutative inverse monoids are defined as quotients of free inverse monoids modulo a partially defined commutation relation on the generators. A quasi linear time algorithm for the word problem is presented. More precisely, we give an $\mathcal {O}(n\log(n))$ algorithm for a RAM. $\mathsf {NP}$ -completeness of the submonoid membership problem (also known as the generalized word problem) and the membership problem for rational sets is shown. Moreover, free partially commutative inverse monoids modulo a finite idempotent presentation are studied. It turns out that the word problem is decidable if and only if the complement of the partial commutation relation is transitive. [ABSTRACT FROM AUTHOR]

Abstract: We show that the membership problem in a finitely generated submonoid of a graph group (also called a right-angled Artin group or a free partially commutative group) is decidable if and only if the independence graph (commutation graph) is a transitive forest. As a consequence we obtain the first example of a finitely presented group with a decidable generalized word problem that does not have a decidable membership problem for finitely generated submonoids. We also show that the rational subset membership problem is decidable for a graph group if and only if the independence graph is a transitive forest, answering a question of Kambites, Silva, and the second author [M. Kambites, P.V. Silva, B. Steinberg, On the rational subset problem for groups, J. Algebra 309 (2) (2007) 622–639]. Finally we prove that for certain amalgamated free products and HNN-extensions the rational subset and submonoid membership problems are recursively equivalent. In particular, this applies to finitely generated groups with two or more ends that are either torsion-free or residually finite. [Copyright &y& Elsevier]

Abstract: Implementations that load XML documents and give access to them via, e.g., the DOM, suffer from huge memory demands: the space needed to load an XML document is usually many times larger than the size of the document. A considerable amount of memory is needed to store the tree structure of the XML document. In this paper, a technique is presented that allows to represent the tree structure of an XML document in an efficient way. The representation exploits the high regularity in XML documents by compressing their tree structure; the latter means to detect and remove repetitions of tree patterns. Formally, context-free tree grammars that generate only a single tree are used for tree compression. The functionality of basic tree operations, like traversal along edges, is preserved under this compressed representation. This allows to directly execute queries (and in particular, bulk operations) without prior decompression. The complexity of certain computational problems like validation against XML types or testing equality is investigated for compressed input trees. [Copyright &y& Elsevier]

For monoids that satisfy a weak cancellation condition, it is shown that the decidability of the existential theory of word equations is preserved under graph products. Furthermore, it is shown that the positive theory of a graph product of groups can be reduced to the positive theories of those factors, which commute with all other factors, and the existential theories of the remaining factors. Both results also include suitable constraints for the variables. Larger classes of constraints lead in many cases to undecidability results. [ABSTRACT FROM AUTHOR]

Several transfer results for rational subsets and finitely generated subgroups of HNN-extensions G = 〈 H,t; t-1 at = φ(a) (a ∈ A) 〉 and amalgamated free products G = H *A J such that the associated subgroup A is finite. These transfer results allow to transfer decidability properties or structural properties from the subgroup H (resp. the subgroups H and J) to the group G. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates the word problem for inverse monoids generated by a set Γ subject to relations of the form e = f, where e and f are both idempotents in the free inverse monoid generated by Γ. It is shown that for every fixed monoid of this form the word problem can be solved both in linear time on a RAM as well as in deterministic logarithmic space, which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node x to a node y that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced. [Copyright &y& Elsevier]

Those graph products of groups that are virtually-free are characterized. [ABSTRACT FROM AUTHOR]

Abstract: The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts in a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the evaluation problem for (structural) XPath queries on trees that are compressed via straight-line context-free tree grammars is investigated. [Copyright &y& Elsevier]

Cayley-graphs of monoids are investigated under a logical point of view. It is shown that the class of monoids, for which the Cayley-graph has a decidable monadic second-order theory, is closed under free products. This result is derived from a result of Walukiewicz, stating that the decidability of monadic second-order theories is preserved under tree-like unfoldings. Concerning first-order logic, it is shown that the class of monoids, for which the Cayley-graph has a decidable first-order theory, is closed under arbitrary graph products, which generalize both, free and direct products. For the proof of this result, tree-like unfoldings are generalized to so-called factorized unfoldings. It is shown that the decidability of the first-order theory of a structure is preserved by factorized unfoldings. Several additional results concerning factorized unfoldings are shown. [ABSTRACT FROM AUTHOR]

We consider a compressed form of the word problem for finitely presented monoids, where the input consists of two compressed representations of words over the generators of a monoid M, and we ask whether these two words represent the same monoid element of M. Words are compressed using straight-line programs, i.e., context-free grammars that generate exactly one word. For several classes of finitely presented monoids we obtain completeness results for complexity classes in the range from P to EXPSPACE. As a by-product of our results on compressed word problems we obtain a fixed deterministic context-free language with a PSPACE-complete compressed membership problem. The existence of such a language was open so far. Finally, we will investigate the complexity of the compressed membership problem for various circuit complexity classes. [ABSTRACT FROM AUTHOR]

Abstract: When a process is capable of executing an unbounded number of non-observable actions it is said to be divergent. Different capabilities of an observer to identify this phenomena along the execution leads to different divergent sensitive semantics. This paper develops sound and complete axiomatisations for the divergence sensitive spectrum of weak bisimulation equivalence. The axiomatisations separates the axioms concerning recursion and those that capture the essence of diverging behaviour. [Copyright &y& Elsevier]

Several complexity and decidability results for automatic monoids are shown: (i) there exists an automatic monoid with a P-complete word problem, (ii) there exists an automatic monoid such that the first-order theory of the corresponding Cayley-graph is not elementary decidable, and (iii) there exists an automatic monoid such that reachability in the corresponding Cayley-graph is undecidable. Moreover, it is shown that for every hyperbolic group the word problem belongs to LOGCFL, which improves a result of Cai [8]. [ABSTRACT FROM AUTHOR]

We prove that a finitely generated group is context-free whenever its Cayley-graph has a decidable monadic second-order theory. Hence, by the seminal work of Muller and Schupp, our result gives a logical characterization of context-free groups and also proves a conjecture of Schupp. To derive this result, we investigate general graphs and show that a graph of bounded degree with a high degree of symmetry is context-free whenever its monadic second-order theory is decidable. Further, it is shown that the word problem of a finitely generated group is decidable if and only if the first-order theory of its Cayley-graph is decidable. [Copyright &y& Elsevier]

We prove that the first-order theory of the one-step rewriting relation associated with a trace rewriting system is decidable but in general not elementary. This extends known results on semi-Thue systems but our proofs use new methods; these new methods yield the decidability of local properties expressed in first-order logic augmented by modulo-counting quantifiers. Using the main decidability result, we define several subclasses of trace rewriting systems for which the confluence problem is decidable. [ABSTRACT FROM AUTHOR]

Message sequence charts (MSCs) and high-level message sequence charts (HMSCs) are popular formalisms for the specification of communication protocols between asynchronous processes. An important concept in this context is the size of the communication buffers used between processes. Since real systems impose limitations on the capacity (or speed) of communication links, we ask whether a given HMSC can be implemented with respect to a given buffer size imposed by the environment. We introduce four different measures for buffer sizes and investigate for each of these measures the complexity of deciding whether a given MSC (or HMSC, or nested MSC) satisfies a given bound on the buffer size. The complexity of these problems varies between the classes P, NP, and coNP. [Copyright &y& Elsevier]

We prove that the existential theory of equations with normalized rational constraints in a fixed graph product of finite monoids, free monoids, and free groups is PSPACE-complete. Under certain restrictions this result also holds if the graph product is part of the input. As the second main result we prove that the positive theory of equations with recognizable constraints in graph products of finite and free groups is decidable. [ABSTRACT FROM AUTHOR]

We study the notion of safe realizability for high-level message sequence charts (HMSCs) (Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), Crete (Greece), Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 797–808). We show that safe realizability is EXPSPACE-complete for bounded HMSCs but undecidable for the class of all HMSCs. This solves two open problems from Alur et al. Moreover we prove that safe realizability is also EXPSPACE-complete for the larger class of globally-cooperative HMSCs. [Copyright &y& Elsevier]

Based on a PSPACE-completeness result for free monoids with involution [4] it is shown that the existential theory of equations with rational constraints in plain groups is PSPACE-complete. As a corollary this settles a question from [16]. [ABSTRACT FROM AUTHOR]

Online fault-diagnosis is applied to various systems to enable an automatic monitoring and, if applicable, the recovery from faults to prevent the system from failing. For a sound decision on occurred faults, typically a large amount of sensor measurements and state variables has to be gathered, analyzed and evaluated in real-time. Due to the complexity and the nature of distributed systems all this data needs to be communicated among the network, which is an expensive affair in terms of communication resources and time. In this paper we present compression strategies that utilize the fact that many of these data streams are highly correlated and can be compressed simultaneously. Experimental results show that this can lead to better compression ratios compared to an individual compression of the data streams. Moreover, the algorithms support real-time constraints for time-triggered architectures and enable the data to be transmitted by means of shorter messages, leading to a reduced communication time and improved scheduling results. With an example data set we show that, depending on the parameters of the compression algorithm, more than one third of the bits (34.3%) in the data communication can be saved while only on about 0.2% of all data values a slight loss of accuracy occurs. This means 99.8% of the data values can be correctly delivered without any loss but with a significant reduction of bandwidth demands. [ABSTRACT FROM AUTHOR]