Watson-Crick ω-Automata
Petre, Elena · Journal of automata, languages and combinatorics · 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)