Frank Stephan

Affiliations:
  • National University of Singapore (NUS), Departments of Mathematics and Computer Science, Singapore


According to our database1, Frank Stephan authored at least 240 papers between 1993 and 2022.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
Randomness and initial segment complexity for measures.
Theor. Comput. Sci., 2022

A computation model with automatic functions and relations as primitive operations.
Theor. Comput. Sci., 2022

Deciding Parity Games in Quasi-polynomial Time.
SIAM J. Comput., 2022

Learners based on transducers.
Inf. Comput., 2022

An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs.
CoRR, 2022

Lamplighter groups and automata.
Acta Informatica, 2022

On Trees Without Hyperimmune Branches.
Proceedings of the Revolutions and Revelations in Computability, 2022

2021
Improved algorithms for the general exact satisfiability problem.
Theor. Comput. Sci., 2021

Bi-immunity over different size alphabets.
Theor. Comput. Sci., 2021

On the amount of nonconstructivity in learning formal languages from text.
Inf. Comput., 2021

Addition Machines, Automatic Functions and Open Problems of Floyd and Knuth.
CoRR, 2021

Alternating Automatic Register Machines.
CoRR, 2021

Computable irrational numbers with representations of surprising complexity.
Ann. Pure Appl. Log., 2021

Learnability and Positive Equivalence Relations.
Proceedings of the Language and Automata Theory and Applications, 2021

2020
Searching for shortest and least programs.
Theor. Comput. Sci., 2020

Chaitin's ω as a continuous function.
J. Symb. Log., 2020

Randomness and Initial Segment Complexity for Probability Measures.
Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Ordered Semiautomatic Rings with Applications to Geometry.
Proceedings of the Language and Automata Theory and Applications, 2020

A Faster Exact Algorithm to Count X3SAT Solutions.
Proceedings of the Principles and Practice of Constraint Programming, 2020

2019
An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space.
Int. J. Softw. Tools Technol. Transf., 2019

The complexity of verbal languages over groups.
J. Comput. Syst. Sci., 2019

The isomorphism problem for tree-automatic ordinals with addition.
Inf. Process. Lett., 2019

Reductions between types of numberings.
Ann. Pure Appl. Log., 2019

Exact Satisfiabitity with Jokers.
Proceedings of the Theory and Applications of Models of Computation, 2019

Random Subgroups of Rationals.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Measure and Conquer for Max Hamming Distance XSAT.
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT.
Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Pumping, with or Without Choice.
Proceedings of the Programming Languages and Systems - 17th Asian Symposium, 2019

2018
Learning pattern languages over groups.
Theor. Comput. Sci., 2018

Effectivity questions for Kleene's recursion theorem.
Theor. Comput. Sci., 2018

Implementing fragments of ZFC within an r.e. Universe.
J. Log. Comput., 2018

Randomness and Solovay degrees.
J. Log. Anal., 2018

Limit-depth and DNR degrees.
Inf. Process. Lett., 2018

Equivalences between learning of data and probability distributions, and their applications.
Inf. Comput., 2018

Finitely generated semiautomatic groups.
Comput., 2018

On the Values for Factor Complexity.
Proceedings of the Implementation and Application of Automata, 2018

Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

On General Sum Approximations of Irrational Numbers.
Proceedings of the Sailing Routes in the World of Computation, 2018

On the Help of Bounded Shot Verifiers, Comparators and Standardisers for Learnability in Inductive Inference.
Proceedings of the Algorithmic Learning Theory, 2018

2017
Query-Based Learning.
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Inductive Inference.
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Computational Complexity of Learning.
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Complexity of Inductive Inference.
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Semiautomatic Structures.
Theory Comput. Syst., 2017

Automatic learning from positive data and negative counterexamples.
Inf. Comput., 2017

Special issue on the conference Theory and Applications of Models of Computation.
Inf. Comput., 2017

Depth, Highness and DNR degrees.
Discret. Math. Theor. Comput. Sci., 2017

Algorithmic learning of probability distributions from random data in the limit.
CoRR, 2017

Closed left-r.e. sets.
Comput., 2017

Covering the recursive sets.
Ann. Pure Appl. Log., 2017

Deciding parity games in quasipolynomial time.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

An ordered approach to solving parity games in quasi polynomial time and quasi linear space.
Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software, 2017

Weakly Represented Families in Reverse Mathematics.
Proceedings of the Computability and Complexity, 2017

Automatic Learning from Repetitive Texts.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016
Guest Editors' foreword.
Theor. Comput. Sci., 2016

Tree-automatic scattered linear orders.
Theor. Comput. Sci., 2016

Reducibilities among equivalence relations induced by recursively enumerable structures.
Theor. Comput. Sci., 2016

Partial learning of recursively enumerable languages.
Theor. Comput. Sci., 2016

On block pumpable languages.
Theor. Comput. Sci., 2016

Enlarging learnable classes.
Inf. Comput., 2016

On the role of update constraints and text-types in iterative learning.
Inf. Comput., 2016

Finite state incompressible infinite sequences.
Inf. Comput., 2016

How to verify computation with a rational network.
CoRR, 2016

On Martin's pointed tree theorem.
Comput., 2016

Inductive inference and reverse mathematics.
Ann. Pure Appl. Log., 2016

Learning Automatic Families of Languages.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

2015
Deterministic Frequency Pushdown Automata.
J. Univers. Comput. Sci., 2015

Partial functions and domination.
Log. Methods Comput. Sci., 2015

Cone avoidance and randomness preservation.
Ann. Pure Appl. Log., 2015

Priced Learning.
Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015

Combining Models of Approximation with Partial Learning.
Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015

2014
Confident and consistent partial learning of recursive functions.
Theor. Comput. Sci., 2014

Robust learning of automatic classes of languages.
J. Comput. Syst. Sci., 2014

Automatic learners with feedback queries.
J. Comput. Syst. Sci., 2014

Things that can be made into themselves.
Inf. Comput., 2014

Initial segment complexities of randomness notions.
Inf. Comput., 2014

The Complexity of Recursive Splittings of Random Sets.
Comput., 2014

Algorithmic Aspects of Lipschitz Functions.
Comput., 2014

A reducibility related to being hyperimmune-free.
Ann. Pure Appl. Log., 2014

Graphs realised by r.e. equivalence relations.
Ann. Pure Appl. Log., 2014

2013
Learning and classifying.
Theor. Comput. Sci., 2013

Guest Editors' foreword.
Theor. Comput. Sci., 2013

Anti-complex sets and reducibilities with tiny use.
J. Symb. Log., 2013

Automatic functions, linear time and learning.
Log. Methods Comput. Sci., 2013

Highness, locally noncappability and nonboundings.
Ann. Pure Appl. Log., 2013

Automatic models of first order theories.
Ann. Pure Appl. Log., 2013

Automata on ordinals and automaticity of linear orders.
Ann. Pure Appl. Log., 2013

Selection by Recursively Enumerable Sets.
Proceedings of the Theory and Applications of Models of Computation, 2013

On Conservative Learning of Recursively Enumerable Languages.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

Editors' Introduction.
Proceedings of the Algorithmic Learning Theory - 24th International Conference, 2013

2012
Arithmetic complexity via effective names for random sequences.
ACM Trans. Comput. Log., 2012

How Powerful Are Integer-Valued Martingales?
Theory Comput. Syst., 2012

An incomplete set of shortest descriptions.
J. Symb. Log., 2012

Learnability of automatic classes.
J. Comput. Syst. Sci., 2012

Learning with ordinal-bounded memory from positive data.
J. Comput. Syst. Sci., 2012

Automatic learning of subclasses of pattern languages.
Inf. Comput., 2012

On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data.
Proceedings of the Theory and Applications of Models of Computation, 2012

Learnability of Co-r.e. Classes.
Proceedings of the Language and Automata Theory and Applications, 2012

Learning Families of Closed Sets in Matroids.
Proceedings of the Computation, Physics and Beyond, 2012

The Discrete Time Behaviour of Restricted Linear Hybrid Automata.
Proceedings of the Modern Applications of Automata Theory., 2012

2011
Uncountable automatic classes and learning.
Theor. Comput. Sci., 2011

Universal recursively enumerable sets of strings.
Theor. Comput. Sci., 2011

Van Lambalgen's Theorem and High Degrees.
Notre Dame J. Formal Log., 2011

Index sets and universal numberings.
J. Comput. Syst. Sci., 2011

Representation of left-computable ε-random reals.
J. Comput. Syst. Sci., 2011

On the Parameterised Complexity of Learning Patterns.
Proceedings of the Computer and Information Sciences II, 2011

Automata on Ordinals and Linear Orders.
Proceedings of the Models of Computation in Context, 2011

2010
Query-Based Learning.
Proceedings of the Encyclopedia of Machine Learning, 2010

Inductive Inference.
Proceedings of the Encyclopedia of Machine Learning, 2010

Computational Complexity of Learning.
Proceedings of the Encyclopedia of Machine Learning, 2010

Complexity of Inductive Inference.
Proceedings of the Encyclopedia of Machine Learning, 2010

Iterative learning of simple external contextual languages.
Theor. Comput. Sci., 2010

Schnorr trivial sets and truth-table reducibility.
J. Symb. Log., 2010

Numberings optimal for learning.
J. Comput. Syst. Sci., 2010

Regular patterns, regular languages and context-free languages.
Inf. Process. Lett., 2010

Enumerating randoms
CoRR, 2010

Higher Kurtz randomness.
Ann. Pure Appl. Log., 2010

Splitting of Learnable Classes.
Proceedings of the Grammatical Inference: Theoretical Results and Applications, 2010

Editors' Introduction.
Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010

2009
Prescribed learning of r.e. classes.
Theor. Comput. Sci., 2009

Input-Dependence in Function-Learning.
Theory Comput. Syst., 2009

Constructive Dimension and Turing Degrees.
Theory Comput. Syst., 2009

Consistent Partial Identification.
Proceedings of the COLT 2009, 2009

Learning from Streams.
Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009

2008
Preface.
Theor. Comput. Sci., 2008

Absolute versus probabilistic classification in a logical setting.
Theor. Comput. Sci., 2008

Mitotic Classes in Inductive Inference.
SIAM J. Comput., 2008

Immunity and Hyperimmunity for Sets of Minimal Indices.
Notre Dame J. Formal Log., 2008

Non-U-shaped vacillatory and team learning.
J. Comput. Syst. Sci., 2008

Learning in Friedberg numberings.
Inf. Comput., 2008

When unlearning helps.
Inf. Comput., 2008

Prescribed Learning of Indexed Families.
Fundam. Informaticae, 2008

Computable categoricity and the Ershov hierarchy.
Ann. Pure Appl. Log., 2008

<i>I</i> classes, LR degrees and Turing degrees.
Ann. Pure Appl. Log., 2008

2007
Deduction, Induction, and beyond in Parametric Logic.
Proceedings of the Induction, Algorithmic Learning Theory, and Philosophy, 2007

On the data consumption benefits of accepting increased uncertainty.
Theor. Comput. Sci., 2007

Invertible classes.
Theor. Comput. Sci., 2007

Post's Programme for the Ershov Hierarchy.
J. Log. Comput., 2007

Automatic Structures: Richness and Limitations.
Log. Methods Comput. Sci., 2007

Applications of Kolmogorov complexity to computable model theory.
J. Symb. Log., 2007

On the learnability of vector spaces.
J. Comput. Syst. Sci., 2007

Results on memory-limited U-shaped learning.
Inf. Comput., 2007

Mitotic Classes.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

On C-Degrees, H-Degrees and T-Degrees.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

Constructive Dimension and Weak Truth-Table Degrees.
Proceedings of the Computation and Logic in the Real World, 2007

2006
On ordinal VC-dimension and some notions of complexity.
Theor. Comput. Sci., 2006

Unifying logic, topology and learning in Parametric logic.
Theor. Comput. Sci., 2006

Learning a subclass of regular patterns in polynomial time.
Theor. Comput. Sci., 2006

Infinitely-Often Autoreducible Sets.
SIAM J. Comput., 2006

Enumerations of the Kolmogorov function.
J. Symb. Log., 2006

Randomness and universal machines.
J. Complex., 2006

Variations on U-shaped learning.
Inf. Comput., 2006

Lowness Properties and Approximations of the Jump.
Electron. Notes Theor. Comput. Sci., 2006

Kolmogorov-Loveland randomness and stochasticity.
Ann. Pure Appl. Log., 2006

Lowness for Weakly 1-generic and Kurtz-Random.
Proceedings of the Theory and Applications of Models of Computation, 2006

Some Recent Results in U-Shaped Learning.
Proceedings of the Theory and Applications of Models of Computation, 2006

Kolmogorov Complexity and the Recursion Theorem.
Proceedings of the STACS 2006, 2006

Behavioural Approximations for Restricted Linear Differential Hybrid Automata.
Proceedings of the Hybrid Systems: Computation and Control, 9th International Workshop, 2006

Memory-Limited U-Shaped Learning.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

Degrees of Weakly Computable Reals.
Proceedings of the Logical Approaches to Computational Barriers, 2006

Editors' Introduction.
Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005
Automatic linear orders and trees.
ACM Trans. Comput. Log., 2005

Lowness for the Class of Schnorr Random Reals.
SIAM J. Comput., 2005

Randomness, relativization and Turing degrees.
J. Symb. Log., 2005

The dot-depth and the polynomial hierarchies correspond on the delta levels.
Int. J. Found. Comput. Sci., 2005

Presentations of K-Trivial Reals and Kolmogorov Complexity.
Proceedings of the New Computational Paradigms, 2005

2004
Learning how to separate.
Theor. Comput. Sci., 2004

Trees and learning.
J. Comput. Syst. Sci., 2004

Robust learning--rich and poor.
J. Comput. Syst. Sci., 2004

Generalized notions of mind change complexity.
Inf. Comput., 2004

Counting extensional differences in BC-learning.
Inf. Comput., 2004

Classes with easily learnable subclasses.
Inf. Comput., 2004

On the classification of recursive languages.
Inf. Comput., 2004

Identifying Clusters from Positive Data
Electron. Colloquium Comput. Complex., 2004

A Polynomial Time Learner for a Subclass of Regular Patterns
Electron. Colloquium Comput. Complex., 2004

Definability and Regularity in Automatic Structures.
Proceedings of the STACS 2004, 2004

The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels.
Proceedings of the Developments in Language Theory, 2004

Finding Isolated Cliques by Queries -- An Approach to Fault Diagnosis with Many Faults.
Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

2003
Refuting learning revisited.
Theor. Comput. Sci., 2003

Learning power and language expressiveness.
Theor. Comput. Sci., 2003

Topological aspects of numberings.
Math. Log. Q., 2003

Learning by switching type of information.
Inf. Comput., 2003

Strong Reductions and Immunity for Exponential Time.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

On Automatic Partial Orders.
Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

2002
Learning classes of approximations to non-recursive function.
Theor. Comput. Sci., 2002

Avoiding coding tricks by hyperrobust learning.
Theor. Comput. Sci., 2002

Learning to Win Process-Control Games Watching Game-Masters.
Inf. Comput., 2002

Trivial Reals.
Electron. Notes Theor. Comput. Sci., 2002

Classes bounded by incomplete sets.
Ann. Pure Appl. Log., 2002

Learning in Logic with RichProlog.
Proceedings of the Logic Programming, 18th International Conference, 2002

Learning, Logic, and Topology in a Common Framework.
Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

2001
Learning algebraic structures from text.
Theor. Comput. Sci., 2001

Robust learning with infinite additional information.
Theor. Comput. Sci., 2001

Predictive learning models for concept drift.
Theor. Comput. Sci., 2001

On The Structures Inside Truth-Table Degrees.
J. Symb. Log., 2001

On one-sided versus two-sided classification.
Arch. Math. Log., 2001

A General Theory of Deduction, Induction, and Learning.
Proceedings of the Discovery Science, 4th International Conference, DS 2001, Washington, 2001

Hausdorff Dimension in Exponential Time.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
Structural measures for games and process control in the branch learning model.
Theor. Comput. Sci., 2000

Vacillatory and BC learning on noisy data.
Theor. Comput. Sci., 2000

Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.
Math. Log. Q., 2000

The Comlexity of Odd<sup>A</sup><sub>n</sub>.
J. Symb. Log., 2000

Robust Learning Aided by Context.
J. Comput. Syst. Sci., 2000

Counting Extensional Differences in BC-Learning.
Proceedings of the Grammatical Inference: Algorithms and Applications, 2000

Unlearning Helps.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Average-Case Complexity of Learning Polynomials.
Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999
Characterizations of Recursively Enumerable Languages by Programmed Grammars With Unconditional Transfer.
J. Autom. Lang. Comb., 1999

The Complexity of Universal Text-Learners.
Inf. Comput., 1999

On the Uniform Learnability of Approximations to Non-Recursive Functions.
Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

The VC-Dimension of Subclasses of Pattern.
Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

1998
On the Relative Sizes of Learnable Sets.
Theor. Comput. Sci., 1998

Learning via Queries and Oracles.
Ann. Pure Appl. Log., 1998

Classification Using Information.
Ann. Math. Artif. Intell., 1998

Learning Algebraic Structures from Text Using Semantical Knowledge.
Proceedings of the Algorithmic Learning Theory, 9th International Conference, 1998

1997
Noisy Inference and Oracles.
Theor. Comput. Sci., 1997

Correction to "A Cohesive Set which is not High".
Math. Log. Q., 1997

On Existentially First-Order Definable Languages and their Relation to NP
Electron. Colloquium Comput. Complex., 1997

On the Classification of Computable Languages.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

The Complexity of Learning Branches and Strategies from Queries.
Proceedings of the Algorithms and Computation, 8th International Symposium, 1997

How Powerful is Unconditional Transfer? - When UT meets AC.
Proceedings of the 3rd International Conference Developments in Language Theory, 1997

Resource Bounded Next Value and Explanatory Identification: Learning Automata, Patterns and Polynomials On-Line.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996
Inclusion Problems in Parallel Learning and Games.
J. Comput. Syst. Sci., 1996

On the Structure of Degrees of Inferability.
J. Comput. Syst. Sci., 1996

Looking for an Analogue of Rice's Theorem in Complexity Theory
Electron. Colloquium Comput. Complex., 1996

On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions
Electron. Colloquium Comput. Complex., 1996

On the Query Complexity of Sets.
Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

1995
Approximable Sets
Inf. Comput., August, 1995

Recursion Theoretic Properties of Frequency Computation and Bounded Queries
Inf. Comput., July, 1995

Quantifying the Amount of Verboseness
Inf. Comput., April, 1995

Language Learning from Texts: Mindchanges, Limited Memory, and Monotonicity.
Inf. Comput., 1995

Measure, Category and Learning Theory.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

The Power of Frequency Computation (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

Language Learning from Texts: Mind Changes, Limited Memory and Monotonicity (Extended Abstract).
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994
Effective Search Problems.
Math. Log. Q., 1994

Extremes in the Degrees of Inferability.
Ann. Pure Appl. Log., 1994

Inclusion Problems in Parallel Learning and Games (Extended Abstract).
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993
On Optimizing Diameter and Average Distance of Directed Interconnected Networks.
IEEE Trans. Computers, 1993

A Cohesive Set which is not High.
Math. Log. Q., 1993

Weakly Semirecursive Sets and r.e. Orderings.
Ann. Pure Appl. Log., 1993

Recursion Theoretic Properties of Frequency Computation and Bounded Queries (Extended Abstract).
Proceedings of the Computational Logic and Proof Theory, Third Kurt Gödel Colloquium, 1993


  Loading...