Abstracts
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.
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.
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.
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.
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.
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.
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.
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.
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$.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
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 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.
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.
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.
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.
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.
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.
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.
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 n≥5 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.
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