Testing and generating infinite sequences by a finite automaton

From MaRDI portal
Publication:5613960

DOI10.1016/S0019-9958(66)80013-XzbMath0212.33902OpenAlexW2094912129MaRDI QIDQ5613960

Robert McNaughton

Publication date: 1966

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(66)80013-x



Related Items

CTL\(^*\) and ECTL\(^*\) as fragments of the modal \(\mu\)-calculus, 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, Progress measures, immediate determinacy, and a subset construction for tree automata, Deterministic asynchronous automata for infinite traces, The complementation problem for Büchi automata with applications to temporal logic, Finitely generated \(\omega\)-languages, Prognosis of \(\omega\)-languages for the diagnosis of *-languages: a topological perspective, On generators of rational \(\omega\)-power languages, Factorization forests for infinite words and applications to countable scattered linear orderings, Finite automata and ordinals, Chain automata, Somewhat finite approaches to infinite sentences., Determinization and memoryless winning strategies, Learning regular omega languages, Inferring regular languages and \(\omega\)-languages, On control of systems modelled as deterministic Rabin automata, On a subclass of \(\infty\)-regular languages, Etude syntaxique des parties reconnaissables de mots infinis. (Syntactic study of recognizable parts of infinite words), Observations on determinization of Büchi automata, Logic programming approach to automata-based decision procedures, Complementing deterministic Büchi automata in polynomial time, An automata theoretic decision procedure for the propositional mu- calculus, On the classification of recursive languages, Using automata theory for characterizing the semantics of terminological cycles, Characterization and closure properties of linear \(\omega\)-languages, Choice functions and well-orderings over the infinite binary tree, Determinization of ordinal automata, Axiomatising extended computation tree logic, On the complexity of \(\omega\)-type Turing acceptors, Path sets in one-sided symbolic dynamics, Finite automata on timed \(\omega\)-trees, Ambiguity in omega context free languages, The complexity of the temporal logic with ``until over general linear time, Profile trees for Büchi word automata, with application to determinization, Borel hierarchy and omega context free languages., From bidirectionality to alternation., Unambiguous Büchi automata., A gap property of deterministic tree languages., Groups, graphs, languages, automata, games and second-order monadic logic, Probabilistic verification of communication protocols, The three subfamilies of rational \(\omega\)-languages closed under \(\omega\)-transduction, Topology, monitorable properties and runtime verification, Generalized automata on infinite trees and Muller-McNaughton's theorem, Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems, Finitely generated bi\(\omega\)-languages, Certifying inexpressibility, On automata on infinite trees, Quantum \(\omega\)-automata over infinite words and their relationships, Characterizations of rational \(\omega\)-languages by means of right congruences, Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra, On Gabbay's temporal fixed point operator, Finite automata on directed graphs, A denotational theory of synchronous reactive systems, Fairness, distances and degrees, Alternating automata, the weak monadic theory of trees and its complexity, Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts, \(\infty\)-regular temporal logic and its model checking problem, On the descriptional complexity of finite automata with modified acceptance conditions, \(X\)-automata on \(\omega\)-words, Theories of automata on \(\omega\)-tapes: a simplified approach, Infinite behaviour of Petri nets, \(\omega\)-regular languages are testable with a constant number of queries, Weak Muller acceptance conditions for tree automata, On the monadic theory of \(\omega_1\) without A.C, A tighter analysis of Piterman's Büchi determinization, Automata on infinite objects and their applications to logic and programming, A decidability result for deterministic \(\omega\)-context-free languages, 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, \(\omega\)-computations on Turing machines, \(\omega\)-computations on deterministic pushdown machines, Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes, Temporal logic with recursion, Mathematical logic and quantum finite state automata, Finite acceptance of infinite words, Logic, semigroups and automata on words, Two characterizations of rational adherences, On the complementation of Büchi automata, \( \omega \)-automata, Minimal separating sets for acceptance conditions in Muller automata, On relation between linear temporal logic and quantum finite automata, An axiomatization of PCTL*, Dynamic linear time temporal logic, Some remarks on non-algebraic adherences, Automata techniques for query inference machines, Finite-state \(\omega\)-languages, Alternating finite automata on \(\omega\)-words, A classification of \(\omega\)-regular languages, On probabilistic timed automata., Star-free sets of words on ordinals, Equivalence of infinite behavior of finite automata, Characterization of \(\omega\)-regular languages by first-order formulas, Langages infinitaires et produit de mixage, Relations rationnelles infinitaires, Towards a formal proof system for \(\omega\)-rational expressions, Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices, A theory of timed automata, Shift-invariant topologies for the Cantor space \(X^{\omega}\), Description and reasoning of VLSI circuit in temporal logic, Index Problems for Game Automata, Limited Set quantifiers over Countable Linear Orderings, On Determinisation of Good-for-Games Automata, Decision problems forω-automata, Automata Theory and Model Checking, The Wadge Hierarchy of Petri Nets ω-Languages, Unnamed Item, Multi-Valued Reasoning about Reactive Systems, Unnamed Item, Rebootable and suffix-closed $\omega $-power languages, Unnamed Item, Definability in the monadic second-order theory of successor, Algorithmic solvability of comparison problems for finitely ambiguous sequence transducers on superwords, Continuous monoids and yields of infinite trees, Parallel generation of infinite images, Saturating right congruences, Unnamed Item, Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization, Subword Metrics for Infinite Words, On the minimization problem for ω-automata, A product version of dynamic linear time temporal logic, Finite state automata and monadic definability of singular cardinals, Jumping automata over Infinite words, An interval temporal logic characterization of extended \(\omega\)-regular languages, Universal first-order quantification over automata, Unnamed Item, On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases, Some Algebraic Properties of Machine Poset of Infinite Words, Unnamed Item, Automata, Semigroups and Recognizability of Words on Ordinals, Distributed ω-Automata, Unnamed Item, New Optimizations and Heuristics for Determinization of Büchi Automata, The recursive sets in certain monadic second order fragments of arithmetic, Axiomatising extended computation tree logic, Model Checking Quantitative Linear Time Logic, An axiomatization of full Computation Tree Logic, Level Two of the Quantifier Alternation Hierarchy over Infinite Words, On Expressive Power of Regular Expressions over Infinite Orders, On?-Languages whose syntactic monoid is trivial, The Quest for a Tight Translation of Büchi to co-Büchi Automata, On Monadic Theories of Monadic Predicates, Unnamed Item, Converting a Büchi alternating automaton to a usual nondeterministic one, Topological properties of omega context-free languages, Wadge hierarchy of omega context-free languages, Computing the Rabin Index of a Parity Automaton, On the bounded monadic theory of well-ordered structures, Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey, Church’s Problem and a Tour through Automata Theory, Incremental reasoning on monadic second-order logics with logic programming, Selection in the monadic theory of a countable ordinal, Facets of Synthesis: Revisiting Church’s Problem, Tighter Bounds for the Determinisation of Büchi Automata, Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata, Unnamed Item, COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS, Unnamed Item, Monoidal-closed categories of tree automata, Unnamed Item, On Repetition Languages, On the Way to Alternating Weak Automata, Unnamed Item, Unnamed Item, Cardinality Quantifiers in MLO over Trees, TYPENESS FOR ω-REGULAR AUTOMATA, Unnamed Item, Relating word and tree automata, State-strategies for games in FσδGδσ, Decidability and undecidability of theories with a predicate for the primes, Rabin vs. Streett Automata, Backward Deterministic Büchi Automata on Infinite Words