To each

The closure of a language $L$ and a semicommutationsystem $SC$ is $f_{SC}(L) = \{ w \in A^\ast \mid \E u \in L, u \ra{*}{SC} w \}$ for $L \subseteq A^\ast$. We give a necessary and a sufficient condition for those semicommutationsystems, where for regular languages $R$ the closure $f_{SC}(R)$ can be recognized by a priority-multicounter-automaton and we show, that for these semicommutationsystems the questions $f_{SC}(R_1) \cap R_2 = \emptyset$? and $max_{SC}(R_1)=R_1$ are decidable for given regular languages $R_1$ and $R_2$. Furthermore we give a criterion for those semicommutaionsystems, where the questions $f_{SC}(R_1) \cap R_2 = \emptyset$? and $max_{SC}(R_1)=R_1$ are undecidable.

At last we a criterion for the confluence of a semicommutationsystem, which is

In the final section, we state that the coding property is undecidable in a naturally arising class of homomorphisms.

As a consequence the emptiness problem and the halting problem are decidable for

In the new version [Rei06b] we define 2 operators on relations over natural numbers such that they generalize the operators '+' and '*' and show that the membership and emptiness problem of relations constructed from finite relations with these operators and $\cup$ is decidable. This generalizes Presburger arithmetics and allows to decide the reachability problem for those Petri nets where inhibitor arcs occur only in some restricted way.

LogCFL/poly = UAuxPDA(log n, n^{O(1)})/poly

The proof makes use of the isolation lemma and a new extended version of the inductive counting technique.

In complexity theory, a number can be an essential information during computation. Small (logarithmic) representations of numbers allow us, in some cases, to get by with fewer resources than expected. This enables us to put problems in a lower complexity class. For example, the closure of nondeterministic logarithmic space under complement has been accomplished in this way with the inductive counting technique. In doing so, storing lots of different configurations was avoided. We extend this method to simulate nondeterministic logarithmic space even with unambiguous logarithmic space (NL/poly = UL/poly). Furthermore, when we consider complexity classes defined using other conditions on the number of accepting paths (such as SPL), we can specifically deal with the problem of the existence of a matching with less space than the matching itself would need. With a similar idea we get a low multi-party communication complexity by communicating the number of times certain properties are fulfilled in the input instead of communicating parts of the input.

Methods in formal languages allow us to represent a counter in several ways and to recognize if two numbers represented in some particular way are successors. This enables us to construct special context-free languages having a particular complexity with respect to measures such as height of the derivation tree, pushdown complexity, time for parallel recognition and ambiguity.

A different aspect of counting in formal languages is the ability to count letters in a string. This has always been viewed as a benchmark for language recognition formalisms. For example, $\{a^nb^n|n>0\}$ is the ``prototype'' of a language which is not regular. In contrast to this, we show that the language of pictures (two-dimensional words) with the same number of $a$'s and $b$'s is a recognizable picture language. Recognizable picture languages are the two-dimensional equivalent of regular languages, and we conclude that their recognition formalism has the ability to count. This also means that counting in two-dimensional arrays is definable in existential monadic second-order logic.

As a model of computation, we consider automata with various kinds of storages. In particular, we consider automata having some restricted access to counters. This brings us to the borderline of decidability. Emptiness and word problem for such automata correspond to the reachability problem for Petri nets and conditions about inhibitor arcs, where the value of a counter corresponds to the number of tokens on a place in a Petri net. In order to get a powerful but still decidable formalism, we define two operators on relations over natural numbers that generalize the operators '+' and '*' and show that the membership and emptiness problem for relations constructed from finite relations with these operators and $\cup$ is decidable. This generalizes Presburger arithmetic and allows us to decide the reachability problem for Petri nets in which inhibitor arcs occur only in some restricted way. A particular example of such Petri nets are the ones with only one inhibitor arc.

The special case, where the syntactic monoid is a finite group was already considered in [RT03] and extended to the case where the syntactic monoid lies in the variety DO.