One-Directional Non-Counting Languages
The Anti-Symmetric Case of Brzozowski's Problem
Versandkostenfrei!
Versandfertig in 6-10 Tagen
32,99 €
inkl. MwSt.
PAYBACK Punkte
16 °P sammeln!
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...
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.
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.
Andere Kunden interessierten sich für
