go-v.orgdoi

Watson-Crick ω-Automata

Petre, Elena · Journal of automata, languages and combinatorics · 2003

  • DOI 10.25596/jalc-2003-059
  • Publisher University of Giessen
  • Type article
  • Issued 2003

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

Journal of automata, languages and combinatorics · University of Giessen · article · 2003

Abstract

Watson-Crick $\omega$-automata are finite automata working with infinite double-stranded words, where the two strands relate to each other through a complementary relation inspired by the DNA complementarity. There are several natural possibilities to define such automata, in particular to define the acceptance condition for such infinite double-stranded words. We present here several results on the equivalence of B{\"{u}}chi, Rabin, Streett, and Muller-like acceptance conditions. We prove that these acceptance conditions are equivalent for nondeterministic Watson-Crick $\omega$-automata.

For deterministic automata, we prove that the four conditions are equivalent for non-empty stateless automata, while the general case remains open. We also investigate the relationship between the classes of languages accepted by several types of Watson-Crick $\omega$-automata.

Open the resolved locator · 10.25596/jalc-2003-059

Metadata licence: OpenAlex metadata (CC0)