Hierarchies over the context-free languages [Rei90]

Alternation is a generalized principle of nondeterminism. The alternating turing machine is used to characterize the polynomial hierarchy. In this paper we show, that a hierarchy can be characterized with alternating pushdown automata, which we expect to be strict in contrast to a hierarchy with alternating finite automata or alternating space bounded automata. We describe a similar oracle hierarchy over the context-free languages, for which we construct complete languages. We show, that each level of the hierarchy with alternating pushdown automata is included in the corresponding level of the oracle hierarchy and that the logarithmic closure over both levels is the corresponding level of the polynomial hierarchy with one alternation less. The principle of the alternation is also transfered to grammars. Hereby we prove, that the hierarchy with alternating context-free grammars is identical with the oracle hierarchy over the context-free languages and that in case of unbounded alternation context-free and context-sensitive grammars have the same power.

Counting and empty alternating pushdown automata [Rei92a]

We show that the class of context free languages CFL is not equal to $\oplus 1-PDA = \oplus CFL$, the class of languages, which are recognized by a nondeterministic one-way push-down automaton equipped with parity acceptance. Furthermore we show that $LOG(\oplus CFL = \oplus AuxPDA_{pt}$ contains all languages, which can be recognized by a uniform weak unambiguous $AC^1$-circuit introduced in \cite{LR90a}. Therefore, it contains all languages, which can be recognized by a $CREW$-PRAM. We show, that $L^{\# Aux^{log}PDA_{pt}}$ is contained in uniform $TC^1$, which sharpens a result in \cite{Vin91}, where inclusion in $NC^2$ was shown. At last we show, that $AC^k$, $SAC^k$ and $P$ can be characterized as the logarithmic closure of certain types of languages. These languages are either those given by linear alternating grammars or they are languages which are recognized by alternating pushdown automata with the restriction that their storage has to be empty if they make an alternating transition. In particular, we consider the cases when the depth of alternation is bounded by a constant or a polylogarithmic function.

Sorting in-place with a worst case complexity of n log n - 1.3 + o(log(n)) comparisons and n log n + o(1) transports [Rei92b]

First we present a new variant of Merge-sort, which needs only 1.25 n space, because it uses space again, which becomes available within the current stage. It does not need more comparisons than classical Merge-sort. The main result is an easy to implement method of iterating the procedure in-place starting to sort 4/5 of the elements. Hereby we can keep the additional transport costs linear and only very few comparisons get lost, so that n \log n - 0.8 n comparisons are needed. We show that we can improve the number of comparisons if we sort blocks of constant length with Merge-Insertion, before starting the algorithm. Another improvement is to start the iteration with a better version, which needs only (1+ \varepsilon) n space and again additional O(n) transports. The result is, that we can improve this theoretically up to n \log n - 1.3289 n comparisons in the worst case. This is close to the theoretical lower bound of n \log n - 1.443 n. The total number of transports in all these versions can be reduced to \varepsilon\, n \log n + O(1) for any \varepsilon > 0.

Priority-multicounter-automata and the synchronization of semitrace-languages [Rei94b]

It was already known, that the halting problem and the emptyness problem for the accepted language is decidable for a multicounter-automaton without zero-test but undecidable for a two-counterautomaton with zero-test. We define a priority-multicounter-automaton by a restrictive zero-test according to an order of the counters in the following way: The first counter can be tested for zero at any time; the second counter can only be tested for zero simultaneously to the first counter; any further counter can only be tested for zero simultaneously to all preceding counters. We show, that the halting problem and the emptyness problem for the accepted language is decidable for priority-multicounter-automata using the result in [Rei94a], that the reachability problem is decidable in such petrinets, where the places can be ordered in a way (like the counters) such that a place has an inhibitor arc to all those transitions, which have an inhibitor arc to a preceding place (e.g. for petrinets with only one inhibitor arc). The classes k-PMC of languages accepted by a priority-multicounter-automaton with $k>0$ counters are incomparable to the class $LIN$ of linear languages and it holds k-1-PMC$\not\supseteq$k-PMC. With the same argument this also holds for the classes k-BLIND and k-PBLIND.
To each semi-dependence alphabet, which is a pair $(A_i,SD_i)$ where $SD \subseteq A_i \times A_i$ is reflexive but possibly asymmetric, we have an associated semi-commutation system $SC_i = \{ ab \ra{}{} ba \mid (a,b) \notin SD_i \}$. A semi-trace over $(A_i,SD_i)$ is by definition the set of words $[u \rangle_i = \{ w \in A_i^\ast \mid u \ra{*}{SC_i} w \}$, which can be derived from a word $u \in A_i^\ast$ by applying semi-{commutation} rules from $SC_i$. We show, that the semitrace-inclusion Problem is in ${\rm \bf TC}^0$. The synchronization of two or more semitraces describes the possible evaluation of a concurrent system, which consists of two or more concurrent subsystems in a modular way, where communication between the subsystems restricts the order. We give criterions, which tell us for given semitraces in given semicommutaionsystem, whether they are synchronizable and whether the synchronization is a semitrace in this case; and criterions, which tell us for given semicommutationsystems, whether all semitraces have this property. We prove that deciding these criterions is NLOGSPACE-complete %with respect to $NC^1$-reduction for given semitraces and the synchronizability of all semitraces for given semicommutationsystems and co-NP-complete for the question, whether for given semicommutationsystems the synchronization of synchronizable semitraces is always a semitrace. Furthermore we give a co-NP-complete condition for being able to decide synchronizability locally in ${\rm \bf TC}^0$.
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 co-NP-complete and a criterion for the existence of a nonconfluent situation for one special semitrace, which is NLOGSPACE-complete.

Empty alternation [LR94]

We introduce the notion of empty alternation by investigating alternating automata which are restricted to empty their storage except for a logarithmically space-bounded tape before making an alternating transition. In particular, we consider the cases when the depth of alternation is bounded by a constant or a polylogarithmic function. In this way we get new characterizations of the classes $AC^k$, $SAC^k$ and $P$ using a push-down store and new characterizations of the class $\Theta^P_2$ using Turing tapes.

On confluent semi-commutation systems - decidability and complexity results. [DOR94]

The subject of this paper is the confluence of finite semi-commutation systems. Confluence of such systems is proved to be a decidable property. Existence of a finite complete presentation of a trace monoid using rules only from another given trace monoid is proved to be reducible to the existence of a confluent semi-commutation system. Complexity results related to the preceding problems are proved: deciding the existence of finite complete presentations is $\Sigma_2^P$-complete, whereas deciding confluence of semi-commutation systems is Co-NP-complete. Additionally, an open problem about trace synchronizations is solved: The local checking property is Co-NP-complete.

On codings of traces [DMR95]

The paper solves the main open problem of \cite{bfg94}. We show that given two dependence alphabets $(\Sigma, D)$ and $(\Sigma', D')$, it is decidable whether there exists a strong coding $h: M(\Sigma, D) \longrightarrow M(\Sigma', D')$ between the associated trace monoids. In fact, we show that the problem is NP-complete. (A coding is an injective homomorphism, it is strong if independent letters are mapped to independent traces.) We exhibit an example of trace monoids where a coding between them exists, but no strong coding. The decidability of codings remains open, in general. We have a lower and an upper bound, which show both to be strict. We further discuss encodings of free products of trace monoids and give almost optimal constructions.
In the final section, we state that the coding property is undecidable in a naturally arising class of homomorphisms.

Optimal Average Case Sorting on Arrays [KNRR95] [KNR99]

We present algorithms for sorting and routing on two-dimensional mesh-connected parallel architectures that are optimal on average. If one processor has many packets then we asymptotically halve the up to now best running times. For a load of one optimal algorithms are known for the mesh. We improve this to a load of eight without increasing the running time. For tori no optimal algorithms were known even for a load of one. Our algorithm is optimal for every load. Other architectures we consider include meshes with diagonals and reconfigurable meshes.

On the synchronization of semi-traces [Rei95a]

The synchronization of two or more semi-traces describes the possible evaluation of a concurrent system, which consists of two or more concurrent subsystems in a modular way, where communication between the subsystems restricts the order of the actions. In this paper we give criteria, which tell us for given semi-traces in given semi-commutation systems, whether they are synchronizable and whether the synchronization is again a semi-trace; and criteria, which tell us for given semi-commutation systems, whether all semi-traces have this property. We prove that deciding these criteria is NLOGSPACE-complete for given semi-traces. The same holds for the synchronizability of all semi-traces for given semi-commutation systems. On the other hand the question, whether for given semi-commutation systems the synchronization of synchronizable semi-traces is a semi-trace is co-NP-complete. Furthermore we give a co-NP-complete condition for being able to decide synchronizability locally in $TC^0$.

Reachability in Petri Nets with Inhibitor arcs [Rei95b] [Rei06b]

We define a new structure called nested Petri net. We show that the question whether a complex transition in a nested Petri net can fire is decidable. From this it follows that the reachability problem is decidable for those Petri nets where the places can be ordered in such a way that, if a transition has an inhibitor arc from a place, then this transition has an inhibitor arc from every smaller place. Especially the reachability problem is decidable for Petri nets with only one inhibitor arc, which solves an open problem from \cite{KLM89} .
As a consequence the emptiness problem and the halting problem are decidable for priority-multicounter-automata which can only perform a zero test of a counter if all counters with smaller index are already zero, and for restricted priority-multipushdown-automata.
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.

Set automata [LR96]

In order to characterize certain formal languages capturing some syntactic aspects of higher programming languages we introduce automata with the storage type set, called set automata. We show the corresponding language class to have an NP-complete membership problem and a decidable emptiness problem.

Advocating ownership [FLR96]

We show the equivalence of deterministic auxiliary push-down automata to owner write PRAMs in a fairly large setting by proving that the sequential class DAuxPDA-TISP(f^{O(1)},log g) and the parallel class CROW-TIPR(log f,g^{O(1)}) coincide. In doing so, we provide the first circuit characterizations of depth O(log f) for deterministic sequential automata which are f time bounded.

Strict Sequential P-completeness [Rei97]

In this paper we present a new notion of what it means for a problem in P to be inherently sequential. Informally, a problem L is strictly sequential P-complete if when the best known sequential algorithm for L has polynomial speedup by parallelization, this implies that all problems in P have a polynomial speedup in the parallel setting. The motivation for defining this class of problems is to try and capture the problems in P that are truly inherently sequential. Our work extends the results of Condon who exhibited problems such that if a polynomial speedup of their best known parallel algorithms could be achieved, then all problems in P would have polynomial speedup. We demonstrate one such natural problem, namely the Multiplex-select Circuit Problem (MCP). MCP has one of the highest degrees of sequentiality of any problem yet defined. On the way to proving MCP is strictly sequential P-complete, we define an interesting model, the register stack machine, that appears to be of independent interest for exploring pure sequentiality.

Towards optimal locality in mesh-indexings [NRS97]

The efficiency of many algorithms in parallel processing, computational geometry, image processing, and several other fields relies on ``locality-preserving'' indexing schemes for meshes. We concentrate on the case where the maximum distance between two mesh nodes indexed i and j shall be a slow-growing function of |i-j| (using the Euclidean, the maximum, and the Manhattan metric). In this respect, space-filling, self-similar curves like the Hilbert curve are superior to simple indexing schemes like ``row-major.'' We present new tight results on 2-D and 3-D Hilbert indexings which are easy to generalize to a quite large class of curves. We then present a new indexing scheme we call H-indexing, which has superior locality. For example, with respect to the Euclidean metric the H-indexing provides locality approximately 50% better than the usually used Hilbert indexing. This answers an open question of Gotsman and Lindenbaum. In addition, H-indexings have the useful property to form a Hamiltonian cycle and they are optimally locality-preserving among all cyclic indexings.

Making Nondeterminism Unambiguous [RA97] [RA00]

We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as: NL/poly = UL/poly
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.

Isolation, Matching, and Counting [AR98] [ARZ99]

We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew (defined and studied in \cite{bdhm} coincides with NL in the nonuniform setting. Finally, we also provide evidence that our results also hold in the uniform setting.

On some recognizable picture-languages [Rei98]

We show that the language of pictures over $\{a,b\}$, where all occurring $b$'s are connected is recognizable, which solves an open problem in \cite{Mat98}. We generalize the used construction to show that monocausal deterministically recognizable picture languages are recognizable, which is surprisingly nontrivial. Furthermore we show that the language of pictures over $\{a,b\}$, where the number of $a$'s is equal to the number of $b$'s is nonuniformly recognizable.

Decidability of Code Properties [FRS99]

We explore the borderline between decidability and undecidability of the following question: ``Let ${\cal C}$ be a class of codes. Given a machine $\frM$ of type $X$, is it decidable whether the language $L({\frM})$ lies in ${\cal C}$ or not?'' for codes in general, $\omega$-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.

A parallel contextfree derivation hierarchy [Rei99]

We are interested in those contextfree languages, where the recognition can be parallelized efficiently. Therefor we consider for a function f the class CFLth(f(n)) of contexfree languages being generated by a contextfree grammar such that every word in the language can be derived in f(n) parallel steps, that means with f(n) bounded tree height. We give a non-regular language with logarithmic tree height disproving a conjecture of Culik and Maurer. As a new method we use counter-representations, where the successor relation can be handled as the complement of context-free languages. We show that a strict and dense hierarchy is obtained between CFLth$(\log n)$ and CFLth$(lin)$=CFL.

Circuits and Contextfree Languages [MRV99]

We give simpler proofs that SAC^1 = LOG(CFL) and DAuxPDA-TIME(pol) = LOG(DCFL) which avoid Sudborough's multi-head automata \cite{Sud78}. Then we consider circuits built from the multiplex select gates of \cite{FLR96}. We show that the classes LOG(DCFL), L and NC^1 are characterized, respectively, by such circuits with polynomial size proof trees, by self-similar logarithmic depth such circuits, and by bounded width polynomial size such circuits.

The #a=#b Pictures are Recognizable. [Rei00]

We show that the language of pictures over $\{a,b\}$, where the number of $a$'s is equal to the number of $b$'s, is recognizable.

Über die Multiparty-Kommunikationskomlexität regulärer Sprachen [PRTT01]

Gem\"ass dem algebraischen Ansatz von \cite{RaymondTT98} untersuchen wir die Kommunikationskomplexit\"at aperiodischer Monoide im Multiparty-model von Chandra, Furst und Lipton. Wir stellen eine Vermutung vor, die die aperiodischen Monoide, die beschr\"ankte Kommunikationskomplexit\"at haben, charakterisieren w\"urde und zeigen verschiedene Ergebnisse in dieser Richtung.

The Complexity of Translating Logic to Finite Automata [Rei02b]

we show a non elementary lower bound for the complexity of translating logic to finite automata. This is done directly by constructing a sequence of formulas describing consecutive counter representations with non elementary growing size. In doing so, we show that the equivalent finite automaton must have a non elementary size.

On the parameterized complexity of a generalized Rush Hour puzzle [FHNRR03]

We consider the parameterized complexity of a generalized version of the game \emph{Rush Hour}\footnote{The name ``Rush Hour'' is a trademark of Binary Arts, Inc.}, which is a puzzle requiring the player to find a sequence of moves by vehicles to enable a special target vehicle to escape from a grid-shaped game board that may contain obstacles. Although the problem is %NP-hard and PSPACE-complete, we demonstrate algorithms that work in polynomial time when either the total number of vehicles or the total number of moves is bounded by a constant. Our contributions are two-fold, entailing the application of ideas of parameterized complexity to games and to motion-planning problems (albeit motion-planning problems of a very constrained nature).

A quadratic distance bound on sliding between crossing-free spanning trees. [AR04]

Let $S$ be a set of $n$ points in the plane in general position and let ${\cal T}_S$ be the set of all crossing-free spanning trees of $S$. We show that it is possible to transform any two trees in ${\cal T}_S$ into each other by $O(n2)$ local and constant-size edge slide operations. Previously in [AichholzerAurenhammerHurtado] a bound of $O(n^2 \log n)$ operations was conjectured.

Finding the shore of a lake. [Rei04c]

We search for the shortest curve in the plane that does not fit inside some given polygon. This generalizes the ``river shore'' problem to the ``lake shore'' problem. We give solutions for several polygons including rectangles and all regular polygons and mainly focus on the triangle case, where we can give optimal solutions in some cases and approximative solutions in other cases.

Counting as Method, Model and Task in Theoretical Computer Science. [Rei05]

Counting is trivial from a mathematical viewpoint. However, in theoretical computer science there are various interesting aspects concerning counting. In complexity theory, counting is an important method. In formal languages, the idea of augmenting a finite automaton with one or more counters leads to interesting models which, in one case, directly correspond to the places in Petri nets. Considering counting as a task for a logic formalism gives insight into its complexity and into its ability to describe languages. Therefore, counting is an important point in the close connections among these fields.
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.

Searching paths of constant bandwidth. [BR06]

As a generalization of paths, the notion of paths of bandwidth w is introduced. We show that, for constant w?1, the corresponding search problem for such a path of length k in a given graph is NP-complete and fixed-parameter tractable in the parameter k, like this is known for the special case w=1, the LONGEST PATH problem. We state the FPT algorithm in terms of a guess and check protocol which uses witnesses of size polynomial in the parameter.

Refining the Nonterminal Complexity of Graph-controlled Grammars. [FFOR05]

We refine the classical notion of the nonterminal complexity of graph-controlled grammars, programmed grammars, and matrix grammars by also counting, in addition, the number of nonterminal symbols that are actually used in the appearance checking mode. We prove that every recursively enumerable language can be generated by a graph-controlled grammar with only two nonterminal symbols when both symbols are used in the appearance checking mode. This result immediately implies that programmed grammars with three nonterminal symbols where two of them are used in the appearance checking mode as well as matrix grammars with three nonterminal symbols all of them used in the appearance checking mode are computationally complete. On the other hand, every unary language is recursive if it is generated by a graph-controlled grammar with an arbitrary number of nonterminal symbols but only one of the nonterminal symbols being allowed to be used in the appearance checking mode. This implies, in particular, that the result proving the computational completeness of graph-controlled grammars with two nonterminal symbols and both of them being used in the appearance checking mode is already optimal with respect to the overall number of nonterminal symbols as well as with respect to the number of nonterminal symbols used in the appearance checking mode, too.

The complexity of the bigamist matching problem. [Rei06]

We describe a polynomial time algorithm to construct a maximal bigamist matching for a given bipartite graph, that is the maximal set of vertex disjoint triples consisting of one bigamist vertex and two monogamist vertices. This solves an open problem in \cite{SGY05}. As a method we use a "double reachability" algorithm to find a simple path in a switch graph, which is equivalent to finding an augmenting path for the bigamist matchings. Furthermore, we show that some other problems of this kind are NP-complete.

Deterministically and Sudoku-deterministically recognizable picture languages [BR06b]

The recognizable 2-dimensional languages are a robust class with many characterizations, comparable to the regular languages in the 1-dimensional case. One characterization is by tiling systems. The corresponding word problem is NP-complete. Therefore, notions of determinism for tiling systems were suggested. For the notion which was called "deterministically recognizable" it was open since 1998 whether it implies recognizability. By showing that acyclicity of grid graphs is recognizable we answer this question positively. In contrast to that, we show that non-recognizable languages can be accepted by a generalization of this tiling system determinism which we call Sudoku-determinism. Its word problem, however, is still in linear time. We show that Sudoku-determinism even contains the set of 2-dimensional languages which can be recognized by 4-way alternating automata.

Exponential Multiplication Schemes [BR06c]

We present an idea to describe a polynomial with 2n distinct integer zeros by an n-tuple of integers via a scheme of n recurring equations. We call such an n-tuple an exponential multiplication scheme of size n. Exponential multiplication schemes of size 1,2,3, and 4 are presented. Under the assumption that fast exponential multiplication scheme generators exist we suggest a fast randomized heuristic for the factorization problem.

Securing Online Accounts from Manipulation and Eavesdropping [BR07b] [BR07c]

The two patent applications present different solutions to the following problem: For online accounts - especially for online banking accounts - the PC of the user is a major security problem: SSL encryption prevents malware in the Internet to eavesdrop and to manipulate the user input but SSL cannot prevent malware on the PC of the user to do so. For example, a so-called keylogger can record the account password while the user is typing it. For online banking there is the special danger of a Man-in-the-Middle attack to a money transfer confirmed by a TAN or iTAN: a different amount of money is transferred to a different recipient account, and the user does not even notice the manipulation. The first patent applies visual cryptography in a transparency-on-screen version to this security problem. The second patent describes a wireless electronic card with a display on the front and a camera on the back which has many one-time-pad keys stored: the electronic card reads the number of a key shown in an encrypted message on the screen, decrypts the rest of the message, and then >shows the decrypted message on its display. For comfortable usage the card simulates the user's mouse by a mouse on its display.

Arithmetic Circuits having few Gates but many Distict Integer Zeros [BMR09][BMR13]

A d-gem is a {+,-,\times}-circuit having very few multiplication-gates and computing from {x}\cup Z a univariate polynomial of degree d having d distinct integer roots. We introduce d-gems because they offer the remote possibility of being helpful for factoring integers, and because their existence for infinitely many d would disprove a form of the Blum-Cucker-Shub-Smale conjecture (strengthened to allow arbitrary constants). A natural step towards a better understanding of the BCSS conjecture thus would be to construct d-gems or to rule out their existence. Ruling out d-gems for large d is currently totally out of reach. Here the best we can do towards that goal is to prove that skew 2n-gems if they exist require n {+,-}-gates and that skew 2n-gems or any n5 would provide new solutions to the Prouhet-Tarry-Escott problem in number theory (skew meaning the further restriction that each {+,-}-gate merely adds an integer to a polynomial). In the opposite direction, here we do manage to construct skew d-gems for several values of d up to 55.

Regular Languages are Church Rosser Congruential [DKRW12]

This paper proves a long standing conjecture in formal language theory. It shows that all regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by \mbox{McNaughton}, Narendran, and Otto in 1988. A language $L$ is Church-Rosser congruential if there exists a finite, confluent, and length-reducing semi-Thue system $S$ such that $L$ is a finite union of congruence classes modulo $S$. It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but on the other hand it was strongly believed that all regular languages are of this form. This paper solves the conjecture affirmatively by actually proving a more general result about finite monoids and weight reducing systems.
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.

last modified by Klaus Reinhardt