Search

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]

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]

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]

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]

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]

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]

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]

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]

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]

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: 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]

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]

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 show that satisfiability and finite satisfiability for ECTL ⁎ with equality-, order-, and modulo-constraints over Z are decidable. Since ECTL ⁎ is a proper extension of CTL ⁎ this greatly improves the previously known decidability results for certain fragments of CTL ⁎ , e.g., the existential and positive fragments and EF . We also show that our choice of local constraints is necessary for the result in the sense that, if we add the possibility to state non-local constraints over Z , the resulting logic becomes undecidable. [ABSTRACT FROM AUTHOR]

It is shown that every tree of size n over a fixed set of σ different ranked symbols can be produced by a so called straight-line linear context-free tree grammar of size O ( n log σ ⁡ n ) , which can be used as a compressed representation of the input tree. Two algorithms for computing such tree grammar are presented: One working in logarithmic space and the other working in linear time. As a consequence, it is shown that every arithmetical formula of size n , in which only m ≤ n different variables occur, can be transformed (in linear time as well as in logspace) into an arithmetical circuit of size O ( n ⋅ log ⁡ m log ⁡ n ) and depth O ( log ⁡ n ) . This refines a classical result of Brent from 1974, according to which an arithmetical formula of size n can be transformed into a logarithmic depth circuit of size O ( n ) . [ABSTRACT FROM AUTHOR]