On ω-regular sets
From MaRDI portal
Publication:3873568
DOI10.1016/S0019-9958(79)90653-3zbMath0434.68061MaRDI QIDQ3873568
Publication date: 1979
Published in: Information and Control (Search for Journal in Brave)
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Related Items (83)
On omega context free languages which are Borel sets of infinite rank. ⋮ Infinite-word languages and continuous mappings ⋮ Bounded model checking of infinite state systems ⋮ A Survey on Difference Hierarchies of Regular Languages ⋮ The Wadge Hierarchy of Petri Nets ω-Languages ⋮ Chain automata ⋮ Descriptive set theory, from Cantor to Wadge and beyond ⋮ Towards a descriptive set theory for domain-like structures ⋮ Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words) ⋮ More complicated questions about maxima and minima, and some closures of NP ⋮ On alternating \(\omega\)-automata ⋮ Accepting conditions for automata on \(\omega\)-languages ⋮ A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I ⋮ A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II ⋮ The Wadge-Wagner hierarchy of ω-rational sets ⋮ Unnamed Item ⋮ Effective wadge hierarchy in computable quasi-Polish spaces ⋮ Language-theoretical representations of \(\omega\)-languages ⋮ Fine hierarchy of regular \(\omega\)-languages ⋮ Expressive Power of Non-deterministic Evolving Recurrent Neural Networks in Terms of Their Attractor Dynamics ⋮ Going Beyond Turing with P Automata: Partial Adult Halting and Regular Observer $$\omega $$-Languages ⋮ Fine hierarchy of regular ω-languages ⋮ Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time ⋮ On the Weak Index Problem for Game Automata ⋮ Fixed point characterization of infinite behavior of finite-state systems ⋮ On syntactic congruences for \(\omega\)-languages ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ Turing reducibility in the fine hierarchy ⋮ On infinitary finite length codes ⋮ Zielonka DAG acceptance and regular languages over infinite words ⋮ On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words ⋮ Ambiguity in omega context free languages ⋮ The Rabin index of parity games: its complexity and approximation ⋮ A hierarchy of deterministic context-free \(\omega\)-languages. ⋮ Borel hierarchy and omega context free languages. ⋮ The Algebraic Counterpart of the Wagner Hierarchy ⋮ Sequential mappings of $\omega $-languages ⋮ Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages ⋮ Logic vs topology on regular \(\omega \)-languages ⋮ Extending Wagner's hierarchy to deterministic visibly pushdown automata ⋮ Two Effective Properties of ω-Rational Functions ⋮ Fine hierarchies via Priestley duality ⋮ Semantic flowers for good-for-games and deterministic automata ⋮ Some Algebraic Properties of Machine Poset of Infinite Words ⋮ Unnamed Item ⋮ Complexity of Topological Properties of Regular ω-Languages ⋮ FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Certifying inexpressibility ⋮ Topological complexity of locally finite \(\omega\)-languages ⋮ Characterizations of rational \(\omega\)-languages by means of right congruences ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ On the separation question for tree languages ⋮ The Borel hierarchy is infinite in the class of regular sets of trees ⋮ \(X\)-automata on \(\omega\)-words ⋮ Computer science and the fine structure of Borel sets ⋮ Automated Compositional Reasoning of Intuitionistically Closed Regular Properties ⋮ Polishness of some topologies related to word or tree automata ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ Computing the Rabin Index of a Parity Automaton ⋮ Expressive power of first-order recurrent neural networks determined by their attractor dynamics ⋮ THE MISSING LINK FOR ω-RATIONAL SETS, AUTOMATA, AND SEMIGROUPS ⋮ Prefix-free languages as \(\omega\)-generators ⋮ A Fine Hierarchy of ω-Regular k-Partitions ⋮ Finite acceptance of infinite words ⋮ Various hierarchies of \(\omega\)-regular sets ⋮ AUTOMATED COMPOSITIONAL REASONING OF INTUITIONISTICALLY CLOSED REGULAR PROPERTIES ⋮ Wadge Degrees ofω-Languages of Deterministic Turing Machines ⋮ Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata ⋮ Wadge-Wagner hierarchies ⋮ A characterization of Büchi tree automata ⋮ How to decide continuity of rational functions on infinite words ⋮ Finite-state \(\omega\)-languages ⋮ Alternating finite automata on \(\omega\)-words ⋮ Boolean algebras of regular languages ⋮ Efficient minimization of deterministic weak \(\omega\)-automata ⋮ Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ THE WAGNER HIERARCHY ⋮ Input-driven pushdown automata on well-nested infinite strings ⋮ Shift-invariant topologies for the Cantor space \(X^{\omega}\)
This page was built for publication: On ω-regular sets
