Alternating finite automata on -words
From MaRDI portal
Publication:796990
DOI10.1016/0304-3975(84)90049-5zbMATH Open0544.68042OpenAlexW2050073538MaRDI QIDQ796990FDOQ796990
Authors: Satoru Miyano, Takeshi Hayashi 
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
Recommendations
- scientific article; zbMATH DE number 3866588
- On alternating \(\omega\)-automata
- Alternating finite automata and star-free languages
- Constructions for alternating finite automata∗
- \(\omega \)-automata
- ω-Automata
- scientific article; zbMATH DE number 1759492
- Alternating register automata on finite words and trees
- On emptiness and counting for alternating finite automata
- An alternating hierarchy for finite automata
nondeterminismnondeterministic finite automataalternationAlternating finite automatainfinite sequences of symbolsomega-language
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Alternation
- Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
- \(\omega\)-computations on Turing machines
- Testing and generating infinite sequences by a finite automaton
- Theories of automata on \(\omega\)-tapes: a simplified approach
- Decision problems forω-automata
- On ω-regular sets
- \(\omega\)-computations on deterministic pushdown machines
- Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sets of Numbers Defined by Finite Automata
Cited In (77)
- Constructions for alternating finite automata∗
- Projection for Büchi Tree Automata with Constraints between Siblings
- Alternation and \(\omega\)-type Turing acceptors
- Alternating automata: unifying truth and validity checking for temporal logics
- Visibly linear temporal logic
- Automata theory and model checking
- SYMBOLIC IMPLEMENTATION OF ALTERNATING AUTOMATA
- Model Checking Information Flow in Reactive Systems
- \(\omega \)-automata
- Size-change termination and satisfiability for linear-time temporal logics
- From bidirectionality to alternation.
- On regular temporal logics with past
- An automata-theoretic approach to model-checking systems and specifications over infinite data domains
- Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces
- Complexity and Succinctness Issues for Linear-Time Hybrid Logics
- Lattice Automata
- Probabilistic opacity for Markov decision processes
- Title not available (Why is that?)
- A Characterisation of Pi^0_2 Regular Tree Languages
- Blind counter automata on \(\omega\)-words
- Nondeterministic Tree Automata
- An alternating hierarchy for finite automata
- Title not available (Why is that?)
- A theory of ultimately periodic languages and automata with an application to time granularity
- New optimizations and heuristics for determinization of Büchi automata
- Don't care words with an application to the automata-based approach for real addition
- Optimal constructions for active diagnosis
- Determinization and limit-determinization of Emerson-Lei automata
- From linear temporal logics to Büchi automata: the early and simple principle
- Alternating automata and temporal logic normal forms
- Hybrid and first-order complete extensions of CaRet
- Title not available (Why is that?)
- Alternating automata on infinite trees
- ω-Automata
- Fuzzy alternating Büchi automata over distributive lattices
- Graph Games and Reactive Synthesis
- Alternating finite automata and star-free languages
- Title not available (Why is that?)
- Observations on determinization of Büchi automata
- Latticed-LTL synthesis in the presence of noisy inputs
- Automatic winning shifts
- Robust, expressive, and quantitative linear temporal logics: pick any two for free
- Complexity and succinctness issues for linear-time hybrid logics
- Converting a Büchi alternating automaton to a usual nondeterministic one
- Mechanizing the Powerset Construction for Restricted Classes of ω-Automata
- COMPUTING CONVEX HULLS BY AUTOMATA ITERATION
- Computing the width of non-deterministic automata
- Width of non-deterministic automata
- Pushdown module checking
- Parametrized verification diagrams: temporal verification of symmetric parametrized concurrent systems
- From complementation to certification
- On alternating \(\omega\)-automata
- Title not available (Why is that?)
- TYPENESS FOR ω-REGULAR AUTOMATA
- Parametric linear dynamic logic
- On the strength of unambiguous tree automata
- Title not available (Why is that?)
- NP reasoning in the monotone \(\mu\)-calculus
- Model-checking timed temporal logics
- A decision procedure for \(\mathrm{CTL}^{*}\) based on tableaux and automata
- Propositional Dynamic Logic for Hyperproperties
- Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata
- Singly exponential translation of alternating weak Büchi automata to unambiguous Büchi automata
- From Spot 2.0 to Spot 2.10: What’s New?
- On the power of finite ambiguity in Büchi complementation
- Modular mix-and-match complementation of Büchi automata
- Coalgebraic satisfiability checking for arithmetic \(\mu\)-calculi
- Complementing Büchi Automata with Ranker
- Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition
- Title not available (Why is that?)
- The quest for a tight translation of Büchi to co-Büchi automata
- Rabin vs. Streett automata
- COOL 2 – A Generic Reasoner for Modal Fixpoint Logics (System Description)
- A survey on satisfiability checking for the \(\mu \)-calculus through tree automata
- Towards a grand unification of Büchi complementation constructions
- An automata-theoretic approach to linear temporal logic
- Title not available (Why is that?)
This page was built for publication: Alternating finite automata on \(\omega\)-words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q796990)
