Church’s Problem and a Tour through Automata Theory

DOI10.1007/978-3-540-78127-1_35zbMATH Open1133.68367OpenAlexW1569390362MaRDI QIDQ5452202FDOQ5452202

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Title not available (Why is that?)
• Weak Second‐Order Arithmetic and Finite Automata
• Title not available (Why is that?)
• Decision Problems of Finite Automata Design and Related Arithmetics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the synthesis of strategies in infinite games
• Testing and generating infinite sequences by a finite automaton
• Infinite games played on finite graphs
• Title not available (Why is that?)
• Solution of Church's problem: a tutorial
• Solving Sequential Conditions by Finite-State Strategies
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (21)

• Realizability modulo theories
• Distributed synthesis for well-connected architectures
• Languages versus \(\omega\)-languages in regular infinite games
• Multiplayer cost games with simple Nash equilibria
• Half-positional objectives recognized by deterministic Büchi automata
• Solution of Church's problem: a tutorial
• Computability and realizability for interactive computations
• Title not available (Why is that?)
• 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
• Logical Refinements of Church’s Problem
• Infinite games specified by 2-tape automata
• Title not available (Why is that?)
• 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
• The complexity of transducer synthesis from multi-sequential specifications

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)