One-Directional Non-Counting Languages

Idempotencies received a great deal of interest
through a problem stated by Burnside in 1902: Is
every group, which satisfies the identity x^r=1 and
has a finite set of generators, finite? In the
context of Formal Languages, the derived problem of
non-counting classes, also called Brzozowski''s
Problem, remained open for over 30 years. We treat a
variant of this, where the relations in question can
be applied only in one direction. That is, they
always increase or decrease a word''s length. The
main motivation for this came from the field of DNA
computation. The operation of duplication, which
plays a role there, is just one particular case of
such a relation. In contrast to non-counting
classes, here many of the arising languages are not
regular but rather complex. Thus many interesting
problems remain to be solved.

Autorentext

Peter Leupold received a Diplom in Informatics from Friedrich-Schiller University Jena in 2002. In 2006 he successfully defended his doctoral thesis at the Rovira i Virgili University in Tarragona.

Klappentext

Idempotencies received a great deal of interest through a problem stated by Burnside in 1902: Is every group, which satisfies the identity x^r=1 and has a finite set of generators, finite? In the context of Formal Languages, the derived problem of non-counting classes, also called Brzozowski's Problem, remained open for over 30 years. We treat a variant of this, where the relations in question can be applied only in one direction. That is, they always increase or decrease a word's length. The main motivation for this came from the field of DNA computation. The operation of duplication, which plays a role there, is just one particular case of such a relation. In contrast to non-counting classes, here many of the arising languages are not regular but rather complex. Thus many interesting problems remain to be solved.