Testing and generating infinite sequences by a finite automaton

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (only showing first 100 items - show all)

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 ⋮ 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

This page was built for publication: Testing and generating infinite sequences by a finite automaton