Theories of automata on \(\omega\)-tapes: a simplified approach
From MaRDI portal
Publication:1211504
DOI10.1016/S0022-0000(74)80051-6zbMath0292.02033MaRDI QIDQ1211504
Publication date: 1974
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Related Items (56)
Ramsey-Based Inclusion Checking for Visibly Pushdown Automata ⋮ Specification and verification of decentralized daisy chain arbiters with \(\omega\)-extended regular expressions ⋮ Infinite-word languages and continuous mappings ⋮ Asymptotic Subword Complexity ⋮ The complementation problem for Büchi automata with applications to temporal logic ⋮ Automata Theory and Model Checking ⋮ Finite automata and ordinals ⋮ Multi-Valued Reasoning about Reactive Systems ⋮ On a subclass of \(\infty\)-regular languages ⋮ Unnamed Item ⋮ Valuations, regular expressions, and fractal geometry ⋮ Complementing deterministic Büchi automata in polynomial time ⋮ Determinization of ordinal automata ⋮ On the complexity of \(\omega\)-type Turing acceptors ⋮ Zielonka DAG acceptance and regular languages over infinite words ⋮ Linear-Time Model Checking: Automata Theory in Practice ⋮ From bidirectionality to alternation. ⋮ \textit{Once} and \textit{for all} ⋮ On direct products of automaton decidable theories ⋮ Inferring answers to queries ⋮ Knowledge-based programs ⋮ First-order and counting theories ofω-automatic structures ⋮ Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems ⋮ \(\omega\)-languages accepted by finite automata whose structures are cascade products o resets ⋮ On condition/event systems with discrete state realizations ⋮ Interval logics and their decision procedures. I: An interval logic ⋮ Muller message-passing automata and logics ⋮ ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES ⋮ Bridging the gap between fair simulation and trace inclusion ⋮ Infinite behaviour of Petri nets ⋮ A compositional approach to CTL\(^*\) verification ⋮ Verification by augmented abstraction: The automata-theoretic view ⋮ Verification of concurrent programs: The automata-theoretic framework ⋮ 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 ⋮ \(\omega\)-computations on Turing machines ⋮ \(\omega\)-computations on deterministic pushdown machines ⋮ Automata-Theoretic Model Checking Revisited ⋮ Lattice Automata ⋮ Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes ⋮ Büchi Complementation and Size-Change Termination ⋮ On the complementation of Büchi automata ⋮ Alternating automata: Unifying truth and validity checking for temporal logics ⋮ Classes of Timed Automata and the Undecidability of Universality ⋮ Pictures of functions and their acceptability by automata ⋮ Automata techniques for query inference machines ⋮ Finite-state \(\omega\)-languages ⋮ From complementation to certification ⋮ Alternating finite automata on \(\omega\)-words ⋮ A classification of \(\omega\)-regular languages ⋮ Verification by augmented finitary abstraction ⋮ Process logic with regular formulas ⋮ Decidability and undecidability of theories with a predicate for the primes ⋮ Rabin vs. Streett Automata ⋮ A theory of timed automata
Cites Work
- Weak Second‐Order Arithmetic and Finite Automata
- Decision Problems of Finite Automata Design and Related Arithmetics
- Decision methods in the theory of ordinals
- Testing and generating infinite sequences by a finite automaton
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Theories of automata on \(\omega\)-tapes: a simplified approach