Peter Leupold

One-Directional Non-Counting Languages

The Anti-Symmetric Case of Brzozowski's Problem

• Broschiertes Buch

Produktbeschreibung

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.

Produktdetails

• Verlag: VDM Verlag Dr. Müller
• Seitenzahl: 116
• Englisch
• Abmessung: 220mm
• ISBN-13: 9783639168891
• ISBN-10: 3639168895
• Artikelnr.: 26569322

Autorenporträt

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.