Alternating finite automata on \(\omega\)-words

DOI10.1016/0304-3975(84)90049-5zbMath0544.68042OpenAlexW2050073538MaRDI QIDQ796990

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90049-5

zbMATH Keywords

nondeterminism alternation nondeterministic finite automata Alternating finite automata infinite sequences of symbols omega-language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Model Checking Information Flow in Reactive Systems, Alternation and \(\omega\)-type Turing acceptors, Size-Change Termination and Satisfiability for Linear-Time Temporal Logics, Automata Theory and Model Checking, Graph Games and Reactive Synthesis, Optimal constructions for active diagnosis, Unnamed Item, Alternating automata on infinite trees, Determinization and limit-determinization of Emerson-Lei automata, On alternating \(\omega\)-automata, Observations on determinization of Büchi automata, Parametrized verification diagrams: temporal verification of symmetric parametrized concurrent systems, Latticed-LTL synthesis in the presence of noisy inputs, Fuzzy alternating Büchi automata over distributive lattices, Width of Non-deterministic Automata, Robust, expressive, and quantitative linear temporal logics: pick any two for free, Automatic winning shifts, On the power of finite ambiguity in Büchi complementation, From linear temporal logics to Büchi automata: the early and simple principle, SYMBOLIC IMPLEMENTATION OF ALTERNATING AUTOMATA, Towards a grand unification of Büchi complementation constructions, A survey on satisfiability checking for the \(\mu \)-calculus through tree automata, From bidirectionality to alternation., Mechanizing the Powerset Construction for Restricted Classes of ω-Automata, Unnamed Item, Unnamed Item, Complexity and Succinctness Issues for Linear-Time Hybrid Logics, Probabilistic opacity for Markov decision processes, New Optimizations and Heuristics for Determinization of Büchi Automata, Hybrid and First-Order Complete Extensions of CaRet, Visibly linear temporal logic, Parametric linear dynamic logic, Pushdown module checking, Alternating automata and temporal logic normal forms, The Quest for a Tight Translation of Büchi to co-Büchi Automata, On regular temporal logics with past, A Decision Procedure for CTL* Based on Tableaux and Automata, On the Strength of Unambiguous Tree Automata, Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces, Converting a Büchi alternating automaton to a usual nondeterministic one, Lattice Automata, A theory of ultimately periodic languages and automata with an application to time granularity, Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata, Propositional Dynamic Logic for Hyperproperties, COMPUTING CONVEX HULLS BY AUTOMATA ITERATION, Model-checking Timed Temporal Logics, Don't care words with an application to the automata-based approach for real addition, TYPENESS FOR ω-REGULAR AUTOMATA, Alternating automata: Unifying truth and validity checking for temporal logics, \( \omega \)-automata, A Characterisation of Pi^0_2 Regular Tree Languages, Complexity and succinctness issues for linear-time hybrid logics, An automata-theoretic approach to model-checking systems and specifications over infinite data domains, From complementation to certification, NP reasoning in the monotone \(\mu\)-calculus, Projection for Büchi Tree Automata with Constraints between Siblings, Rabin vs. Streett Automata

Cites Work