Recent and upcoming talks by Frank Stephan

Frank Stephan: A fast exponential time algorithm for Max Hamming Distance X3SAT

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 24 October 2018, 17:00 hrs Room: S17#04-05, Department of Mathematics, NUS Speaker: Frank Stephan Title: A fast exponential time algorithm for Max Hamming Distance X3SAT URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html SAT is the problem which asks whether a given list of clauses in n Boolean variables can be satisfied by an assignment to the variables which is common for all clauses, XSAT is the variant of SAT which asks the same, but requires in addition that in each clause exactly one literal is true; X3SAT is the corresponding problem with the additional constraint that every clause contains up to three literals only. continue reading…

Frank Stephan: Computational aspects of the hyperimmune-free degrees

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 15 August 2018, 17:00 hrs Room: S17#04-05, Department of Mathematics, NUS Speaker: Frank Stephan Title: Computational aspects of the hyperimmune-free degrees URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html A set A has hyperimmune-free degree, if every set B Turing equivalent to A is already truth-table equivalent to A. continue reading…

Frank Stephan: Finitely generated semiautomatic groups

Update on the Logic Seminar at the National University of Singapore (the originally announced speaker is ill and will speak on 12 April 2017) Date: Wednesday, 22 March 2016, 17:00 hrs Room: S17#04-05, Department of Mathematics, NUS Speaker: Frank Stephan Title: Finitely generated semiautomatic groups URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html The present work shows that Cayley automatic groups are semiautomatic and exhibits some further constructions of semiautomatic groups. continue reading…

Frank Stephan: On block pumpable languages

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, Wednesday 10 Aug 2016, 17:00 hrs Room: S17#04-05, Department of Mathematics, NUS Speaker: Frank Stephan Title: On block pumpable languages URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html Abstract: Call a language L block pumpable iff there is a constant p>1 such that for every splitting of a word in the language L into p+1 blocks, one can find a subword consisting of an interval of the interior blocks such that each modified word obtained by repeating or omitting this subword is also in the language L. continue reading…

Frank Stephan: Learning automatatic families of languages

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 9 March 2016, 17:00 hrs Room: S17#05-11, Department of Mathematics, NUS Speaker: Frank Stephan Title: Learning automatatic families of languages URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html A class of languages is automatic if it is uniformly regular using some regular index set for the languages. continue reading…

Frank Stephan: The complexity of semiautomatic structures

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 21 October 2015, 17:00 hrs Room: S17#04-06, Department of Mathematics, NUS Speaker: Frank Stephan Title: The complexity of semiautomatic structures URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html Abstract: This talk extends previous work on semiautomatic structures and in particular investigates complexity issues with groups and semigroups; furthermore, results from recursion theory are used to show that one specific structure is not semiautomatic while a related one can be shown to be semiautomatic. continue reading…

Frank Stephan: Covering the Recursive Sets

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 14 October 2015, 17:00 hrs Room: S17#04-06, Department of Mathematics, NUS Speaker: Frank Stephan Title: Covering the Recursive Sets URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html The talk gives an overview of recent work which solves two problems of Brendle, Brooke-Taylor, Ng and Nies. continue reading…

Frank Stephan: Covering the Recursive Sets

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 19 August 2015, 17:00 hrs Room: S17#04-06, Department of Mathematics, NUS Speaker: Frank Stephan Title: Covering the Recursive Sets URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html The talk gives an overview of recent work which solves two problems of Brendle, Brooke-Taylor, Ng and Nies. continue reading…

Frank Stephan: Automatic Structures – recent results and open questions

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 25 March 2015, 17:00 hrs Room: S17#05-11, Department of Mathematics, NUS Speaker: Frank Stephan Title: Automatic Structures – recent results and open questions URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html Abstract: Automatic structures are a way to represent algebraic structures using finite automata; all the algebraic operations and relations have to be recognised / verified by finite automata which read the inputs and outputs with the same speed (one symbol per cycle). continue reading…

Frank Stephan: Recent progress on partial learning and related notions

Invitation to the Logic Seminar at the National University of Singapore Date: Wednesday, 14 January 2015, 17:00 hrs Room: S17#05-22, Department of Mathematics, NUS Speaker: Frank Stephan Title: Recent progress on partial learning and related notions. continue reading…