Decision problems forω-automata

DOI10.1007/BF01691063zbMath0182.02402OpenAlexW117768600WikidataQ61687239 ScholiaQ61687239MaRDI QIDQ5573396

Publication date: 1969

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01691063

zbMATH Keywords

recursion theory, constructive mathematics

Related Items

An impossibility result in automata-theoretic reinforcement learning, Logic vs topology on regular $\omega $-languages, Minimization of automata for liveness languages, Liminf progress measures, Wadge hierarchy of omega context-free languages, On omega context free languages which are Borel sets of infinite rank., Specification and verification of decentralized daisy chain arbiters with $\omega$-extended regular expressions, Solving Infinite Games in the Baire Space, Infinite-word languages and continuous mappings, A branching time logic with past operators, Bounded model checking of infinite state systems, Alternation and $\omega$-type Turing acceptors, Spanning the spectrum from safety to liveness, On the classification of computable languages, Topological characterizations of infinite tree languages, Automata Theory and Model Checking, Prognosis of $\omega$-languages for the diagnosis of *-languages: a topological perspective, The Wadge Hierarchy of Petri Nets ω-Languages, Chain automata, Multi-Valued Reasoning about Reactive Systems, Somewhat finite approaches to infinite sentences., Descriptive set theory, from Cantor to Wadge and beyond, Rebootable and suffix-closed $\omega $-power languages, Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words), On the Topological Complexity of Infinitary Rational Relations, Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations, Accepting conditions for automata on $\omega$-languages, Saturating right congruences, On the classification of recursive languages, The Wadge-Wagner hierarchy of ω-rational sets, Problems concerning fairness and temporal logic for conflict-free Petri nets, Language-theoretical representations of $\omega$-languages, Terminal metric spaces of finitely branching and image finite linear processes, Subword Metrics for Infinite Words, Local rule distributions, language complexity and non-uniform cellular automata, On the High Complexity of Petri Nets $$\omega $$-Languages, On the complexity of $\omega$-type Turing acceptors, Ambiguity in omega context free languages, Profile trees for Büchi word automata, with application to determinization, Borel hierarchy and omega context free languages., Unambiguous Büchi automata., Sequential mappings of $\omega $-languages, Mechanizing the Powerset Construction for Restricted Classes of ω-Automata, On the continuity set of an Omega rational function, Ambiguity, weakness, and regularity in probabilistic Büchi automata, The three subfamilies of rational $\omega$-languages closed under $\omega$-transduction, Unnamed Item, Complexity of Topological Properties of Regular ω-Languages, Topology, monitorable properties and runtime verification, Certifying inexpressibility, The Hausdorff-Kuratowski hierarchy of $\omega$-regular languages and a hierarchy of Muller automata, Topological complexity of locally finite $\omega$-languages, A complete characterization of deterministic regular liveness properties, Characterizations of rational $\omega$-languages by means of right congruences, Fairness, distances and degrees, Strong fairness and ultra metrics, Synchronized rational relations of finite and infinite words, ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES, On the descriptional complexity of finite automata with modified acceptance conditions, $X$-automata on $\omega$-words, Level Two of the Quantifier Alternation Hierarchy over Infinite Words, The Quest for a Tight Translation of Büchi to co-Büchi Automata, Infinite behaviour of Petri nets, $\omega$-regular languages are testable with a constant number of queries, Weak Muller acceptance conditions for tree automata, An introduction to metric semantics: Operational and denotational models for programming and specification languages, Automated Compositional Reasoning of Intuitionistically Closed Regular Properties, Automata, Borel functions and real numbers in Pisot base, A decidability result for deterministic $\omega$-context-free languages, Polishness of some topologies related to word or tree automata, Theory of $\omega$-languages. I: Characterizations of $\omega$-context- free languages, Theory of $\omega$-languages. II: A study of various models of $\omega$- type generation and recognition, A note on accelerated Turing machines, Topological properties of omega context-free languages, $\omega$-computations on Turing machines, Unnamed Item, $\omega$-computations on deterministic pushdown machines, A Rice-style theorem for parallel automata, Highly Undecidable Problems For Infinite Computations, Prefix-free languages as $\omega$-generators, Finite acceptance of infinite words, Various hierarchies of $\omega$-regular sets, On Repetition Languages, Logic, semigroups and automata on words, Minimizing GFG Transition-Based Automata, AUTOMATED COMPOSITIONAL REASONING OF INTUITIONISTICALLY CLOSED REGULAR PROPERTIES, Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata, Characterization of $\omega$-regular languages by monadic second-order formulas, TYPENESS FOR ω-REGULAR AUTOMATA, Index sets in computable analysis, Some problems in automata theory which depend on the models of set theory, A note on $\omega$-regular languages, Relating word and tree automata, Alternating finite automata on $\omega$-words, The residue of vector sets with applications to decidability problems in Petri nets, Projection lemmas for $\omega$-languages, A classification of $\omega$-regular languages, Characterization of $\omega$-regular languages by first-order formulas, A taxonomy of fairness and temporal logic problems for Petri nets, Backward Deterministic Büchi Automata on Infinite Words, How Deterministic are Good-For-Games Automata?, On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words, Effectively closed sets and graphs of computable real functions., THE WAGNER HIERARCHY, Shift-invariant topologies for the Cantor space $X^{\omega}$

Cites Work