Finite-state \(\omega\)-languages

DOI10.1016/0022-0000(83)90051-XzbMath0541.68052MaRDI QIDQ794443

Ludwig Staiger

Publication date: 1983

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

zbMATH Keywords

Borel hierarchyfinite state omega-languagesinfinite sequences of wordsminimization problem for finite automataregular omega-languagestopological considerations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (36)

Learning infinite-word automata with loop-index queries ⋮ Infinite-word languages and continuous mappings ⋮ Construction of a Deterministicω-Automaton Using Derivatives ⋮ Rebootable and suffix-closed $\omega $-power languages ⋮ Learning regular omega languages ⋮ Inferring regular languages and \(\omega\)-languages ⋮ The topological structure of adherences of regular languages ⋮ Classifying recognizable infinitary trace languages using word automata ⋮ A geometrical view of the determinization and minimization of finite-state automata ⋮ Going Beyond Turing with P Automata: Partial Adult Halting and Regular Observer $$\omega $$-Languages ⋮ Subword Metrics for Infinite Words ⋮ On the minimization problem for ω-automata ⋮ On syntactic congruences for \(\omega\)-languages ⋮ Unnamed Item ⋮ Concurrent Kleene algebra with observations: from hypotheses to completeness ⋮ Ambiguity, weakness, and regularity in probabilistic Büchi automata ⋮ First-Order Logic and Numeration Systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fractals, dimension, and formal languages ⋮ Finitely generated bi\(\omega\)-languages ⋮ Characterizations of rational \(\omega\)-languages by means of right congruences ⋮ Boolean TQFTs with accumulating defects, sofic systems, and automata for infinite words ⋮ Which finite monoids are syntactic monoids of rational \(\omega\)-languages ⋮ Polynomial Identification of $$\omega $$-Automata ⋮ \(X\)-automata on \(\omega\)-words ⋮ Ehrenfeucht-Fraïssé goes automatic for real addition ⋮ Regular \(\omega\)-languages with an informative right congruence ⋮ Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs ⋮ Finite automata encoding geometric figures ⋮ Half-positional objectives recognized by deterministic Büchi automata ⋮ The disjunctivities of \(\omega\)-languages. ⋮ \( \omega \)-automata ⋮ Iterated function systems and control languages ⋮ Efficient minimization of deterministic weak \(\omega\)-automata ⋮ Shift-invariant topologies for the Cantor space \(X^{\omega}\)

Cites Work

• Theories of automata on \(\omega\)-tapes: a simplified approach
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• \(\omega\)-computations on deterministic pushdown machines
• On the concept of strongly transitive systems in topology
• On?-Languages whose syntactic monoid is trivial
• On ω-regular sets
• On ω-sets associated with context-free languages
• Definability in the monadic second-order theory of successor
• Testing and generating infinite sequences by a finite automaton
• Derivatives of Regular Expressions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finite-state \(\omega\)-languages