Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition

DOI10.1016/S0022-0000(77)80005-6zbMath0363.68114OpenAlexW1997093946MaRDI QIDQ1240575

Arie Y. Gold, Rina S. Cohen

Publication date: 1977

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(77)80005-6

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Closure properties of locally finite \(\omega\)-languages ⋮ Somewhat finite approaches to infinite sentences. ⋮ On a subclass of \(\infty\)-regular languages ⋮ On the complexity of \(\omega\)-type Turing acceptors ⋮ On direct products of automaton decidable theories ⋮ Unnamed Item ⋮ \(X\)-automata on \(\omega\)-words ⋮ Automata on infinite objects and their applications to logic and programming ⋮ Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages ⋮ \(\omega\)-computations on Turing machines ⋮ \(\omega\)-computations on deterministic pushdown machines ⋮ Highly Undecidable Problems For Infinite Computations ⋮ Real functions and numbers defined by Turing machines ⋮ Init and Anf operating on \(\omega\)-languages ⋮ Alternating finite automata on \(\omega\)-words ⋮ Computability and realizability for interactive computations ⋮ Safety and liveness of \(\omega\)-context-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• \(\omega\)-computations on Turing machines
• \(\omega\)-computations on deterministic pushdown machines
• Strict deterministic grammars
• On certain formal properties of grammars
• A note on asymmetry in phrase structure grammars
• Control sets on grammars
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton