Church’s Problem and a Tour through Automata Theory

DOI10.1007/978-3-540-78127-1_35MaRDI QIDQ5452202zbMATH OpenOpenAlexFDO

Authors Wolfgang Thomas

Publication date 25 March 2008

Published in Pillars of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78127-1_35

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• Solution of Church's problem: a tutorial
• Logical Refinements of Church’s Problem
• Control of Infinite Behavior of Finite Automata
• The Church synthesis problem with metric
• Synthesis of finite-state and definable winning strategies

Cites work

• scientific article; zbMATH DE number 3427224 (Why is no real title available?)
• scientific article; zbMATH DE number 3128652 (Why is no real title available?)
• scientific article; zbMATH DE number 3137366 (Why is no real title available?)
• scientific article; zbMATH DE number 3990873 (Why is no real title available?)
• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3237733 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3328724 (Why is no real title available?)
• scientific article; zbMATH DE number 3189696 (Why is no real title available?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision Problems of Finite Automata Design and Related Arithmetics
• Infinite games played on finite graphs
• On the synthesis of strategies in infinite games
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Solution of Church's problem: a tutorial
• Solving Sequential Conditions by Finite-State Strategies
• Testing and generating infinite sequences by a finite automaton
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(20)

• The complexity of transducer synthesis from multi-sequential specifications
• Distributed synthesis for well-connected architectures
• Realizability modulo theories
• Languages versus \(\omega\)-languages in regular infinite games
• Multiplayer cost games with simple Nash equilibria
• Computability and realizability for interactive computations
• Half-positional objectives recognized by deterministic Büchi automata
• Solution of Church's problem: a tutorial
• scientific article; zbMATH DE number 7376069 (Why is no real title available?)
• New optimizations and heuristics for determinization of Büchi automata
• Antichains and compositional algorithms for LTL synthesis
• Choice functions and well-orderings over the infinite binary tree
• The mu-calculus and Model Checking
• Infinite games specified by 2-tape automata
• Logical Refinements of Church’s Problem
• Decidable Extensions of Church’s Problem
• Automated synthesis: a distributed viewpoint
• Soundness in negotiations
• Boolean abstractions for realizability modulo theories
• Diagonalisation and Church's Thesis: Kleene's Homework

This page was built for publication: Church’s Problem and a Tour through Automata Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5452202)