BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Georg Zetzsche

Georg Zetzsche appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata Theorymath.GRLogic in Computer ScienceComputational Complexity

Catalog footprint

What is connected

21works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2022arXiv

Membership Problems in Finite Groups

We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed $n \geq 3$, where $n$ is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks, which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reachability in Bidirected Pushdown VASS

A pushdown vector addition system with states (PVASS) extends the model of vector addition systems with a pushdown store. A PVASS is said to be \emph{bidirected} if every transition (pushing/popping a symbol or modifying a counter) has an accompanying opposite transition that reverses the effect. Bidirectedness arises naturally in many models; it can also be seen as a overapproximation of reachability. We show that the reachability problem for \emph{bidirected} PVASS is decidable in Ackermann time and primitive recursive for any fixed dimension. For the special case of one-dimensional bidirected PVASS, we show reachability is in $\mathsf{PSPACE}$, and in fact in polynomial time if the stack is polynomially bounded. Our results are in contrast to the \emph{directed} setting, where decidability of reachability is a long-standing open problem already for one dimensional PVASS, and there is a $\mathsf{PSPACE}$-lower bound already for one-dimensional PVASS with bounded stack. The reachability relation in the bidirected (stateless) case is a congruence over $\mathbb{N}^d$. Our upper bounds exploit saturation techniques over congruences. In particular, we show novel elementary-time constructions of semilinear representations of congruences generated by finitely many vector pairs. In the case of one-dimensional PVASS, we employ a saturation procedure over bounded-size counters. We complement our upper bound with a $\mathsf{TOWER}$-hardness result for arbitrary dimension and $k$-$\mathsf{EXPSPACE}$ hardness in dimension $2k+6$ using a technique by Lazić and Totzke to implement iterative exponentiations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The complexity of bidirected reachability in valence systems

Reachability problems in infinite-state systems are often subject to extremely high complexity. This motivates the investigation of efficient overapproximations, where we add transitions to obtain a system in which reachability can be decided more efficiently. We consider bidirected infinite-state systems, where for every transition there is a transition with opposite effect. We study bidirected reachability in the framework of valence systems, an abstract model featuring finitely many control states and an infinite-state storage that is specified by a finite graph. By picking suitable graphs, valence systems can uniformly model counters as in vector addition systems, pushdowns, integer counters, and combinations thereof. We provide a comprehensive complexity landscape for bidirected reachability and show that the complexity drops (often to polynomial time) from that of general reachability, for almost every storage mechanism where reachability is known to be decidable.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A characterization of wreath products where knapsack is decidable

The knapsack problem for groups was introduced by Miasnikov, Nikolaev, and Ushakov. It is defined for each finitely generated group $G$ and takes as input group elements $g_1,\ldots,g_n,g\in G$ and asks whether there are $x_1,\ldots,x_n\ge 0$ with $g_1^{x_1}\cdots g_n^{x_n}=g$. We study the knapsack problem for wreath products $G\wr H$ of groups $G$ and $H$. Our main result is a characterization of those wreath products $G\wr H$ for which the knapsack problem is decidable. The characterization is in terms of decidability properties of the indiviual factors $G$ and $H$. To this end, we introduce two decision problems, the intersection knapsack problem and its restriction, the positive intersection knapsack problem. Moreover, we apply our main result to $H_3(\mathbb{Z})$, the discrete Heisenberg group, and to Baumslag-Solitar groups $\mathsf{BS}(1,q)$ for $q\ge 1$. First, we show that the knapsack problem is undecidable for $G\wr H_3(\mathbb{Z})$ for any $G\ne 1$. This implies that for $G\ne 1$ and for infinite and virtually nilpotent groups $H$, the knapsack problem for $G\wr H$ is decidable if and only if $H$ is virtually abelian and solvability of systems of exponent equations is decidable for $G$. Second, we show that the knapsack problem is decidable for $G\wr\mathsf{BS}(1,q)$ if and only if solvability of systems of exponent equations is decidable for $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Approach to Regular Separability in Vector Addition Systems

We study the problem of regular separability of languages of vector addition systems with states (VASS). It asks whether for two given VASS languages K and L, there exists a regular language R that includes K and is disjoint from L. While decidability of the problem in full generality remains an open question, there are several subclasses for which decidability has been shown: It is decidable for (i) one-dimensional VASS, (ii) VASS coverability languages, (iii) languages of integer VASS, and (iv) commutative VASS languages. We propose a general approach to deciding regular separability. We use it to decide regular separability of an arbitrary VASS language from any language in the classes (i), (ii), and (iii). This generalizes all previous results, including (iv).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rational subsets of Baumslag-Solitar groups

We consider the rational subset membership problem for Baumslag-Solitar groups. These groups form a prominent class in the area of algorithmic group theory, and they were recently identified as an obstacle for understanding the rational subsets of $\text{GL}(2,\mathbb{Q})$. We show that rational subset membership for Baumslag-Solitar groups $\text{BS}(1,q)$ with $q\ge 2$ is decidable and PSPACE-complete. To this end, we introduce a word representation of the elements of $\text{BS}(1,q)$: their pointed expansion (PE), an annotated $q$-ary expansion. Seeing subsets of $\text{BS}(1,q)$ as word languages, this leads to a natural notion of PE-regular subsets of $\text{BS}(1, q)$: these are the subsets of $\text{BS}(1,q)$ whose sets of PE are regular languages. Our proof shows that every rational subset of $\text{BS}(1,q)$ is PE-regular. Since the class of PE-regular subsets of $\text{BS}(1,q)$ is well-equipped with closure properties, we obtain further applications of these results. Our results imply that (i) emptiness of Boolean combinations of rational subsets is decidable, (ii) membership to each fixed rational subset of $\text{BS}(1,q)$ is decidable in logarithmic space, and (iii) it is decidable whether a given rational subset is recognizable. In particular, it is decidable whether a given finitely generated subgroup of $\text{BS}(1,q)$ has finite index.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Coverability is Undecidable in One-dimensional Pushdown Vector Addition Systems with Resets

We consider the model of pushdown vector addition systems with resets. These consist of vector addition systems that have access to a pushdown stack and have instructions to reset counters. For this model, we study the coverability problem. In the absence of resets, this problem is known to be decidable for one-dimensional pushdown vector addition systems, but decidability is open for general pushdown vector addition systems. Moreover, coverability is known to be decidable for reset vector addition systems without a pushdown stack. We show in this note that the problem is undecidable for one-dimensional pushdown vector addition systems with resets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Complexity of regular abstractions of one-counter languages

We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) B that recognizes an abstraction of the language L(A): its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown if appropriate NFA of sub-exponential size exist.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Permutations of context-free, ET0L and indexed languages

For a language $L$, we consider its cyclic closure, and more generally the language $C^k(L)$, which consists of all words obtained by partitioning words from $L$ into $k$ factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators $C^k$. This both sharpens and generalises Brandstädt's result that if $L$ is context-free then $C^k(L)$ is context-sensitive and not context-free in general for $k\geq 3$. We also show that the cyclic closure of an indexed language is indexed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The complexity of downward closure comparisons

The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of every language is regular. Moreover, recent results show that downward closures are computable for quite powerful system models. One advantage of abstracting a language by its downward closure is that then equivalence and inclusion become decidable. In this work, we study the complexity of these two problems. More precisely, we consider the following decision problems: Given languages $K$ and $L$ from classes $\mathcal{C}$ and $\mathcal{D}$, respectively, does the downward closure of $K$ include (equal) that of $L$? These problems are investigated for finite automata, one-counter automata, context-free grammars, and reversal-bounded counter automata. For each combination, we prove a completeness result either for fixed or for arbitrary alphabets. Moreover, for Petri net languages, we show that both problems are Ackermann-hard and for higher-order pushdown automata of order~$k$, we prove hardness for complements of nondeterministic $k$-fold exponential time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Complexity of Knapsack in Graph Groups

Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In previous work, the authors proved that for each graph group, the knapsack problem can be solved in $\mathsf{NP}$. Here, we determine the exact complexity of the problem for every graph group. While the problem is $\mathsf{TC}^0$-complete for complete graphs, it is $\mathsf{LogCFL}$-complete for each (non-complete) transitive forest. For every remaining graph, the problem is $\mathsf{NP}$-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An approach to computing downward closures

The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular. While the downward closure appears to be a powerful abstraction, algorithms for computing a finite automaton for the downward closure of a given language have been established only for few language classes. This work presents a simple general method for computing downward closures. For language classes that are closed under rational transductions, it is shown that the computation of downward closures can be reduced to checking a certain unboundedness property. This result is used to prove that downward closures are computable for (i) every language class with effectively semilinear Parikh images that are closed under rational transductions, (ii) matrix languages, and (iii) indexed languages (equivalently, languages accepted by higher-order pushdown automata of order 2).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups

It is shown that the knapsack problem (introduced by Myasnikov, Nikolaev, and Ushakov) is undecidable in a direct product of sufficiently many copies of the discrete Heisenberg group (which is nilpotent of class 2). Moreover, for the discrete Heisenberg group itself, the knapsack problem is decidable. Hence, decidability of the knapsack problem is not preserved under direct products. It is also shown that for every co-context-free group, the knapsack problem is decidable. For the subset sum problem (also introduced by Myasnikov, Nikolaev, and Ushakov) we show that it belongs to the class NL (nondeterministic logspace) for every finitely generated virtually nilpotent group and that there exists a polycyclic group with an NP-complete subset sum problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Knapsack in graph groups, HNN-extensions and amalgamated products

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 graph groups. This result even holds if the group elements are represented in a compressed form by SLPs, which generalizes the classical NP-completeness result of the integer knapsack problem. We also prove general transfer results: NP-membership of the knapsack problem is passed on to finite extensions, HNN-extensions over finite associated subgroups, and amalgamated products with finite identified subgroups.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Computing downward closures for stacked counter automata

The downward closure of a language $L$ of words is the set of all (not necessarily contiguous) subwords of members of $L$. It is well known that the downward closure of any language is regular. Although the downward closure seems to be a promising abstraction, there are only few language classes for which an automaton for the downward closure is known to be computable. It is shown here that for stacked counter automata, the downward closure is computable. Stacked counter automata are finite automata with a storage mechanism obtained by \emph{adding blind counters} and \emph{building stacks}. Hence, they generalize pushdown and blind counter automata. The class of languages accepted by these automata are precisely those in the hierarchy obtained from the context-free languages by alternating two closure operators: imposing semilinear constraints and taking the algebraic extension. The main tool for computing downward closures is the new concept of Parikh annotations. As a second application of Parikh annotations, it is shown that the hierarchy above is strict at every level.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The monoid of queue actions

We investigate the monoid of transformations that are induced by sequences of writing to and reading from a queue storage. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties, e.g., conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NL-complete. Furthermore, we present an algebraic characterization of this monoid's recognizable subsets. Finally, we prove that it is not Thurston-automatic.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Semilinearity and Context-Freeness of Languages Accepted by Valence Automata

Valence automata are a generalization of various models of automata with storage. Here, each edge carries, in addition to an input word, an element of a monoid. A computation is considered valid if multiplying the monoid elements on the visited edges yields the identity element. By choosing suitable monoids, a variety of automata models can be obtained as special valence automata. This work is concerned with the accepting power of valence automata. Specifically, we ask for which monoids valence automata can accept only context-free languages or only languages with semilinear Parikh image, respectively. First, we present a characterization of those graph products (of monoids) for which valence automata accept only context-free languages. Second, we provide a necessary and sufficient condition for a graph product of copies of the bicyclic monoid and the integers to yield only languages with semilinear Parikh image when used as a storage mechanism in valence automata. Third, we show that all languages accepted by valence automata over torsion groups have a semilinear Parikh image.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Silent Transitions in Automata with Storage

We consider the computational power of silent transitions in one-way automata with storage. Specifically, we ask which storage mechanisms admit a transformation of a given automaton into one that accepts the same language and reads at least one input symbol in each step. We study this question using the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid. This work presents generalizations of known results on silent transitions. For two classes of monoids, it provides characterizations of those monoids that allow the removal of λ-transitions. Both classes are defined by graph products of copies of the bicyclic monoid and the group of integers. The first class contains pushdown storages as well as the blind counters while the second class contains the blind and the partially blind counters.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the capabilities of grammars, automata, and transducers controlled by monoids

During the last decades, classical models in language theory have been extended by control mechanisms defined by monoids. We study which monoids cause the extensions of context-free grammars, finite automata, or finite state transducers to exceed the capacity of the original model. Furthermore, we investigate when, in the extended automata model, the nondeterministic variant differs from the deterministic one in capacity. We show that all these conditions are in fact equivalent and present an algebraic characterization. In particular, the open question of whether every language generated by a valence grammar over a finite monoid is context-free is provided with a positive answer.

0 citations0 reviewsNo code linkedOpen access