Frank Stephan

According to our database, Frank Stephan authored at least 248 papers between 1990 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Word automatic groups of nilpotency class 2.

André Nies, Frank Stephan

Inf. Process. Lett., January, 2024

A Bisection Approach to Subcubic Maximum Induced Matching.

Gordon Hoi, Sanjay Jain, Ammar Fathin Sabili, Frank Stephan

Proceedings of the WALCOM: Algorithms and Computation, 2024

Quasi-Isometric Reductions Between Infinite Strings.

Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ryan Lou, Frank Stephan, Guohua Wu

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Randomness Versus Superspeedability.

Rupert Hölzl, Philip Janicki, Wolfgang Merkle, Frank Stephan

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023

Learnability and positive equivalence relations.

David R. Bélanger, Ziyuan Gao, Sanjay Jain, Wei Li, Frank Stephan

Inf. Comput., December, 2023

String compression in FA-presentable structures.

Dmitry Berdinsky, Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan

Theor. Comput. Sci., February, 2023

Addition machines, automatic functions and open problems of Floyd and Knuth.

Sanjay Jain, Xiaodong Jia, Ammar Fathin Sabili, Frank Stephan

J. Comput. Syst. Sci., 2023

Languages given by Finite Automata over the Unary Alphabet.

Gordon Hoi, Sanjay Jain, Frank Stephan, Christopher Tan

CoRR, 2023

Languages Given by Finite Automata over the Unary Alphabet.

Wojciech Czerwinski, Maciej Debski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michal Skrzypczak, Frank Stephan, Christopher Tan

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

Randomness and initial segment complexity for measures.

André Nies, Frank Stephan

Theor. Comput. Sci., 2022

A computation model with automatic functions and relations as primitive operations.

Ziyuan Gao, Sanjay Jain, Zeyong Li, Ammar Fathin Sabili, Frank Stephan

Theor. Comput. Sci., 2022

Deciding Parity Games in Quasi-polynomial Time.

Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan

SIAM J. Comput., 2022

Learners based on transducers.

Sanjay Jain, Shao Ning Kuek, Eric Martin, Frank Stephan

Inf. Comput., 2022

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

Gordon Hoi, Ammar Fathin Sabili, Frank Stephan

CoRR, 2022

Lamplighter groups and automata.

Sanjay Jain, Birzhan Moldagaliyev, Frank Stephan, Tien Dat Tran

Acta Informatica, 2022

Alternating Automatic Register Machines.

Ziyuan Gao, Sanjay Jain, Zeyong Li, Ammar Fathin Sabili, Frank Stephan

Proceedings of the Theoretical Aspects of Computing - ICTAC 2022, 2022

On Trees Without Hyperimmune Branches.

Keng Meng Ng, Frank Stephan, Yue Yang, Liang Yu

Proceedings of the Revolutions and Revelations in Computability, 2022

2021

Improved algorithms for the general exact satisfiability problem.

Gordon Hoi, Frank Stephan

Theor. Comput. Sci., 2021

Bi-immunity over different size alphabets.

Cristian S. Calude, Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ludwig Staiger, Frank Stephan

Theor. Comput. Sci., 2021

On the amount of nonconstructivity in learning formal languages from text.

Sanjay Jain, Frank Stephan, Thomas Zeugmann

Inf. Comput., 2021

Computable irrational numbers with representations of surprising complexity.

Ivan Georgiev, Lars Kristiansen, Frank Stephan

Ann. Pure Appl. Log., 2021

2020

Searching for shortest and least programs.

Cristian S. Calude, Sanjay Jain, Wolfgang Merkle, Frank Stephan

Theor. Comput. Sci., 2020

Chaitin's ω as a continuous function.

Rupert Hölzl, Wolfgang Merkle, Joseph S. Miller, Frank Stephan, Liang Yu

J. Symb. Log., 2020

Randomness and Initial Segment Complexity for Probability Measures.

André Nies, Frank Stephan

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Ordered Semiautomatic Rings with Applications to Geometry.

Ziyuan Gao, Sanjay Jain, Ji Qi, Philipp Schlicht, Frank Stephan, Jacob Tarr

Proceedings of the Language and Automata Theory and Applications, 2020

A Faster Exact Algorithm to Count X3SAT Solutions.

Gordon Hoi, Sanjay Jain, Frank Stephan

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.

John Fearnley, Sanjay Jain, Bart de Keijzer, Sven Schewe, Frank Stephan, Dominik Wojtczak

Int. J. Softw. Tools Technol. Transf., 2019

The complexity of verbal languages over groups.

Sanjay Jain, Alexei Miasnikov, Frank Stephan

J. Comput. Syst. Sci., 2019

The isomorphism problem for tree-automatic ordinals with addition.

Sanjay Jain, Bakhadyr Khoussainov, Philipp Schlicht, Frank Stephan

Inf. Process. Lett., 2019

Reductions between types of numberings.

Ian Herbert, Sanjay Jain, Steffen Lempp, Manat Mustafa, Frank Stephan

Ann. Pure Appl. Log., 2019

Exact Satisfiabitity with Jokers.

Gordon Hoi, Sanjay Jain, Sibylle Schwarz, Frank Stephan

Proceedings of the Theory and Applications of Models of Computation, 2019

Random Subgroups of Rationals.

Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander G. Melnikov, Karen Seidel, Frank Stephan

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Measure and Conquer for Max Hamming Distance XSAT.

Gordon Hoi, Frank Stephan

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT.

Gordon Hoi, Sanjay Jain, Frank Stephan

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Pumping, with or Without Choice.

Aquinas Hobor, Elaine Li, Frank Stephan

Proceedings of the Programming Languages and Systems - 17th Asian Symposium, 2019

2018

Learning pattern languages over groups.

Rupert Hölzl, Sanjay Jain, Frank Stephan

Theor. Comput. Sci., 2018

Effectivity questions for Kleene's recursion theorem.

John Case, Sanjay Jain, Frank Stephan

Theor. Comput. Sci., 2018

Implementing fragments of ZFC within an r.e. Universe.

Eric Martin, Frank Stephan

J. Log. Comput., 2018

Randomness and Solovay degrees.

Kenshi Miyabe, André Nies, Frank Stephan

J. Log. Anal., 2018

Limit-depth and DNR degrees.

Philippe Moser, Frank Stephan

Inf. Process. Lett., 2018

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

George Barmpalias, Nan Fang, Frank Stephan

Inf. Comput., 2018

Finitely generated semiautomatic groups.

Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan

Comput., 2018

On the Values for Factor Complexity.

Birzhan Moldagaliyev, Ludwig Staiger, Frank Stephan

Proceedings of the Implementation and Application of Automata, 2018

Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations.

André Nies, Frank Stephan

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

On General Sum Approximations of Irrational Numbers.

Ivan Georgiev, Lars Kristiansen, Frank Stephan

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.

Ziyuan Gao, Sanjay Jain, Frank Stephan, Thomas Zeugmann

Proceedings of the Algorithmic Learning Theory, 2018

2017

Query-Based Learning.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Inductive Inference.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Computational Complexity of Learning.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Complexity of Inductive Inference.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Semiautomatic Structures.

Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan, Dan Teng, Siyuan Zou

Theory Comput. Syst., 2017

Automatic learning from positive data and negative counterexamples.

Sanjay Jain, Efim B. Kinber, Frank Stephan

Inf. Comput., 2017

Special issue on the conference Theory and Applications of Models of Computation.

Rahul Jain, Sanjay Jain, Frank Stephan

Inf. Comput., 2017

Depth, Highness and DNR degrees.

Philippe Moser, Frank Stephan

Discret. Math. Theor. Comput. Sci., 2017

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

George Barmpalias, Frank Stephan

CoRR, 2017

Closed left-r.e. sets.

Sanjay Jain, Frank Stephan, Jason Teutsch

Comput., 2017

Covering the recursive sets.

Bjørn Kjos-Hanssen, Frank Stephan, Sebastiaan A. Terwijn

Ann. Pure Appl. Log., 2017

Deciding parity games in quasipolynomial time.

Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan

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.

John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak

Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software, 2017

Weakly Represented Families in Reverse Mathematics.

Rupert Hölzl, Dilip Raghavan, Frank Stephan, Jing Zhang

Proceedings of the Computability and Complexity, 2017

Automatic Learning from Repetitive Texts.

Rupert Hölzl, Sanjay Jain, Philipp Schlicht, Karen Seidel, Frank Stephan

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016

Guest Editors' foreword.

Sanjay Jain, Rémi Munos, Frank Stephan, Thomas Zeugmann

Theor. Comput. Sci., 2016

Tree-automatic scattered linear orders.

Sanjay Jain, Bakhadyr Khoussainov, Philipp Schlicht, Frank Stephan

Theor. Comput. Sci., 2016

Reducibilities among equivalence relations induced by recursively enumerable structures.

Alex Gavryushkin, Bakhadyr Khoussainov, Frank Stephan

Theor. Comput. Sci., 2016

Partial learning of recursively enumerable languages.

Ziyuan Gao, Frank Stephan, Sandra Zilles

Theor. Comput. Sci., 2016

On block pumpable languages.

Christopher Hanrui Chak, Rusins Freivalds, Frank Stephan, Henrietta Tan Wan Yik

Theor. Comput. Sci., 2016

Enlarging learnable classes.

Sanjay Jain, Timo Kötzing, Frank Stephan

Inf. Comput., 2016

On the role of update constraints and text-types in iterative learning.

Sanjay Jain, Timo Kötzing, Junqi Ma, Frank Stephan

Inf. Comput., 2016

Finite state incompressible infinite sequences.

Cristian S. Calude, Ludwig Staiger, Frank Stephan

Inf. Comput., 2016

How to verify computation with a rational network.

Sanjay Jain, Prateek Saxena, Frank Stephan, Jason Teutsch

CoRR, 2016

On Martin's pointed tree theorem.

Rupert Hölzl, Frank Stephan, Liang Yu

Comput., 2016

Inductive inference and reverse mathematics.

Rupert Hölzl, Sanjay Jain, Frank Stephan

Ann. Pure Appl. Log., 2016

Learning Automatic Families of Languages.

Sanjay Jain, Frank Stephan

Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

2015

Deterministic Frequency Pushdown Automata.

Cristian S. Calude, Rusins Freivalds, Sanjay Jain, Frank Stephan

J. Univers. Comput. Sci., 2015

Partial functions and domination.

C. T. Chong, Gordon Hoi, Frank Stephan, Daniel Turetsky

Log. Methods Comput. Sci., 2015

Cone avoidance and randomness preservation.

Stephen G. Simpson, Frank Stephan

Ann. Pure Appl. Log., 2015

Priced Learning.

Sanjay Jain, Junqi Ma, Frank Stephan

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

Combining Models of Approximation with Partial Learning.

Ziyuan Gao, Frank Stephan, Sandra Zilles

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

2014

Confident and consistent partial learning of recursive functions.

Ziyuan Gao, Frank Stephan

Theor. Comput. Sci., 2014

Robust learning of automatic classes of languages.

Sanjay Jain, Eric Martin, Frank Stephan

J. Comput. Syst. Sci., 2014

Automatic learners with feedback queries.

John Case, Sanjay Jain, Yuh Shin Ong, Pavel Semukhin, Frank Stephan

J. Comput. Syst. Sci., 2014

Things that can be made into themselves.

Frank Stephan, Jason Teutsch

Inf. Comput., 2014

Initial segment complexities of randomness notions.

Rupert Hölzl, Thorsten Kräling, Frank Stephan, Guohua Wu

Inf. Comput., 2014

The Complexity of Recursive Splittings of Random Sets.

Keng Meng Ng, André Nies, Frank Stephan

Comput., 2014

Algorithmic Aspects of Lipschitz Functions.

Cameron E. Freer, Bjørn Kjos-Hanssen, André Nies, Frank Stephan

Comput., 2014

A reducibility related to being hyperimmune-free.

Frank Stephan, Liang Yu

Ann. Pure Appl. Log., 2014

Graphs realised by r.e. equivalence relations.

Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan

Ann. Pure Appl. Log., 2014

2013

Learning and classifying.

Sanjay Jain, Eric Martin, Frank Stephan

Theor. Comput. Sci., 2013

Guest Editors' foreword.

Marcus Hutter, Frank Stephan, Vladimir Vovk, Thomas Zeugmann

Theor. Comput. Sci., 2013

Anti-complex sets and reducibilities with tiny use.

Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan, Guohua Wu

J. Symb. Log., 2013

Automatic functions, linear time and learning.

John Case, Sanjay Jain, Samuel Seah, Frank Stephan

Log. Methods Comput. Sci., 2013

Highness, locally noncappability and nonboundings.

Frank Stephan, Guohua Wu

Ann. Pure Appl. Log., 2013

Automatic models of first order theories.

Pavel Semukhin, Frank Stephan

Ann. Pure Appl. Log., 2013

Automata on ordinals and automaticity of linear orders.

Philipp Schlicht, Frank Stephan

Ann. Pure Appl. Log., 2013

Selection by Recursively Enumerable Sets.

Wolfgang Merkle, Frank Stephan, Jason Teutsch, Wei Wang, Yue Yang

Proceedings of the Theory and Applications of Models of Computation, 2013

On Conservative Learning of Recursively Enumerable Languages.

Ziyuan Gao, Sanjay Jain, Frank Stephan

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

Editors' Introduction.

Sanjay Jain, Rémi Munos, Frank Stephan, Thomas Zeugmann

Proceedings of the Algorithmic Learning Theory - 24th International Conference, 2013

2012

Arithmetic complexity via effective names for random sequences.

Bjørn Kjos-Hanssen, Frank Stephan, Jason Teutsch

ACM Trans. Comput. Log., 2012

How Powerful Are Integer-Valued Martingales?

Laurent Bienvenu, Frank Stephan, Jason Teutsch

Theory Comput. Syst., 2012

An incomplete set of shortest descriptions.

Frank Stephan, Jason Teutsch

J. Symb. Log., 2012

Learnability of automatic classes.

Sanjay Jain, Qinglong Luo, Frank Stephan

J. Comput. Syst. Sci., 2012

Learning with ordinal-bounded memory from positive data.

Lorenzo Carlucci, Sanjay Jain, Frank Stephan

J. Comput. Syst. Sci., 2012

Automatic learning of subclasses of pattern languages.

John Case, Sanjay Jain, Trong Dao Le, Yuh Shin Ong, Pavel Semukhin, Frank Stephan

Inf. Comput., 2012

On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data.

Sanjay Jain, Frank Stephan, Thomas Zeugmann

Proceedings of the Theory and Applications of Models of Computation, 2012

Learnability of Co-r.e. Classes.

Ziyuan Gao, Frank Stephan

Proceedings of the Language and Automata Theory and Applications, 2012

Learning Families of Closed Sets in Matroids.

Ziyuan Gao, Frank Stephan, Guohua Wu, Akihiro Yamamoto

Proceedings of the Computation, Physics and Beyond, 2012

The Discrete Time Behaviour of Restricted Linear Hybrid Automata.

Manindra Agrawal, Frank Stephan, P. S. Thiagarajan, Shaofa Yang

Proceedings of the Modern Applications of Automata Theory., 2012

2011

Uncountable automatic classes and learning.

Sanjay Jain, Qinglong Luo, Pavel Semukhin, Frank Stephan

Theor. Comput. Sci., 2011

Universal recursively enumerable sets of strings.

Cristian S. Calude, André Nies, Ludwig Staiger, Frank Stephan

Theor. Comput. Sci., 2011

Van Lambalgen's Theorem and High Degrees.

Johanna N. Y. Franklin, Frank Stephan

Notre Dame J. Formal Log., 2011

Index sets and universal numberings.

Sanjay Jain, Frank Stephan, Jason Teutsch

J. Comput. Syst. Sci., 2011

Representation of left-computable ε-random reals.

Cristian S. Calude, Nicholas J. Hay, Frank Stephan

J. Comput. Syst. Sci., 2011

On the Parameterised Complexity of Learning Patterns.

Frank Stephan, Ryo Yoshinaka, Thomas Zeugmann

Proceedings of the Computer and Information Sciences II, 2011

Automata on Ordinals and Linear Orders.

Philipp Schlicht, Frank Stephan

Proceedings of the Models of Computation in Context, 2011

2010

Query-Based Learning.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning, 2010

Inductive Inference.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning, 2010

Computational Complexity of Learning.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning, 2010

Complexity of Inductive Inference.

Sanjay Jain, Frank Stephan

Proceedings of the Encyclopedia of Machine Learning, 2010

Iterative learning of simple external contextual languages.

Leonor Becerra-Bonache, John Case, Sanjay Jain, Frank Stephan

Theor. Comput. Sci., 2010

Schnorr trivial sets and truth-table reducibility.

Johanna N. Y. Franklin, Frank Stephan

J. Symb. Log., 2010

Numberings optimal for learning.

Sanjay Jain, Frank Stephan

J. Comput. Syst. Sci., 2010

Regular patterns, regular languages and context-free languages.

Sanjay Jain, Yuh Shin Ong, Frank Stephan

Inf. Process. Lett., 2010

Enumerating randoms

Bjørn Kjos-Hanssen, Frank Stephan, Jason Teutsch

CoRR, 2010

Higher Kurtz randomness.

Bjørn Kjos-Hanssen, André Nies, Frank Stephan, Liang Yu

Ann. Pure Appl. Log., 2010

Splitting of Learnable Classes.

Hongyang Li, Frank Stephan

Proceedings of the Grammatical Inference: Theoretical Results and Applications, 2010

Editors' Introduction.

Marcus Hutter, Frank Stephan, Vladimir Vovk, Thomas Zeugmann

Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010

2009

Prescribed learning of r.e. classes.

Sanjay Jain, Frank Stephan, Nan Ye

Theor. Comput. Sci., 2009

Input-Dependence in Function-Learning.

Sanjay Jain, Eric Martin, Frank Stephan

Theory Comput. Syst., 2009

Constructive Dimension and Turing Degrees.

Laurent Bienvenu, David Doty, Frank Stephan

Theory Comput. Syst., 2009

Consistent Partial Identification.

Sanjay Jain, Frank Stephan

Proceedings of the COLT 2009, 2009

Learning from Streams.

Sanjay Jain, Frank Stephan, Nan Ye

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

2008

Preface.

Philip M. Long, Frank Stephan

Theor. Comput. Sci., 2008

Absolute versus probabilistic classification in a logical setting.

Sanjay Jain, Eric Martin, Frank Stephan

Theor. Comput. Sci., 2008

Mitotic Classes in Inductive Inference.

Sanjay Jain, Frank Stephan

SIAM J. Comput., 2008

Immunity and Hyperimmunity for Sets of Minimal Indices.

Frank Stephan, Jason Teutsch

Notre Dame J. Formal Log., 2008

Non-U-shaped vacillatory and team learning.

Lorenzo Carlucci, John Case, Sanjay Jain, Frank Stephan

J. Comput. Syst. Sci., 2008

Learning in Friedberg numberings.

Sanjay Jain, Frank Stephan

Inf. Comput., 2008

When unlearning helps.

Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan, Rolf Wiehagen

Inf. Comput., 2008

Prescribed Learning of Indexed Families.

Sanjay Jain, Frank Stephan, Nan Ye

Fundam. Informaticae, 2008

Computable categoricity and the Ershov hierarchy.

Bakhadyr Khoussainov, Frank Stephan, Yue Yang

Ann. Pure Appl. Log., 2008

<i>I</i> classes, LR degrees and Turing degrees.

George Barmpalias, Andrew E. M. Lewis, Frank Stephan

Ann. Pure Appl. Log., 2008

2007

Deduction, Induction, and beyond in Parametric Logic.

Eric Martin, Arun Sharma, Frank Stephan

Proceedings of the Induction, Algorithmic Learning Theory, and Philosophy, 2007

On the data consumption benefits of accepting increased uncertainty.

Eric Martin, Arun Sharma, Frank Stephan

Theor. Comput. Sci., 2007

Invertible classes.

Sanjay Jain, Jochen Nessel, Frank Stephan

Theor. Comput. Sci., 2007

Post's Programme for the Ershov Hierarchy.

Bahareh Afshari, George Barmpalias, S. Barry Cooper, Frank Stephan

J. Log. Comput., 2007

Automatic Structures: Richness and Limitations.

Bakhadyr Khoussainov, André Nies, Sasha Rubin, Frank Stephan

Log. Methods Comput. Sci., 2007

Applications of Kolmogorov complexity to computable model theory.

Bakhadyr Khoussainov, Pavel Semukhin, Frank Stephan

J. Symb. Log., 2007

On the learnability of vector spaces.

Valentina S. Harizanov, Frank Stephan

J. Comput. Syst. Sci., 2007

Results on memory-limited U-shaped learning.

Lorenzo Carlucci, John Case, Sanjay Jain, Frank Stephan

Inf. Comput., 2007

Mitotic Classes.

Sanjay Jain, Frank Stephan

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

On C-Degrees, H-Degrees and T-Degrees.

Wolfgang Merkle, Frank Stephan

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

Constructive Dimension and Weak Truth-Table Degrees.

Laurent Bienvenu, David Doty, Frank Stephan

Proceedings of the Computation and Logic in the Real World, 2007

2006

On ordinal VC-dimension and some notions of complexity.

Eric Martin, Arun Sharma, Frank Stephan

Theor. Comput. Sci., 2006

Unifying logic, topology and learning in Parametric logic.

Eric Martin, Arun Sharma, Frank Stephan

Theor. Comput. Sci., 2006

Learning a subclass of regular patterns in polynomial time.

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann

Theor. Comput. Sci., 2006

Identifying Clusters from Positive Data.

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

SIAM J. Comput., 2006

Infinitely-Often Autoreducible Sets.

Richard Beigel, Lance Fortnow, Frank Stephan

SIAM J. Comput., 2006

Enumerations of the Kolmogorov function.

Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

J. Symb. Log., 2006

Randomness and universal machines.

Santiago Figueira, Frank Stephan, Guohua Wu

J. Complex., 2006

Variations on U-shaped learning.

Lorenzo Carlucci, Sanjay Jain, Efim B. Kinber, Frank Stephan

Inf. Comput., 2006

Kolmogorov-Loveland randomness and stochasticity.

Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann, Frank Stephan

Ann. Pure Appl. Log., 2006

Lowness for Weakly 1-generic and Kurtz-Random.

Frank Stephan, Liang Yu

Proceedings of the Theory and Applications of Models of Computation, 2006

Some Recent Results in U-Shaped Learning.

Sanjay Jain, Frank Stephan

Proceedings of the Theory and Applications of Models of Computation, 2006

Kolmogorov Complexity and the Recursion Theorem.

Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan

Proceedings of the STACS 2006, 2006

Behavioural Approximations for Restricted Linear Differential Hybrid Automata.

Manindra Agrawal, Frank Stephan, P. S. Thiagarajan, Shaofa Yang

Proceedings of the Hybrid Systems: Computation and Control, 9th International Workshop, 2006

Memory-Limited U-Shaped Learning.

Lorenzo Carlucci, John Case, Sanjay Jain, Frank Stephan

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

Degrees of Weakly Computable Reals.

Keng Meng Ng, Frank Stephan, Guohua Wu

Proceedings of the Logical Approaches to Computational Barriers, 2006

Editors' Introduction.

José L. Balcázar, Philip M. Long, Frank Stephan

Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005

Automatic linear orders and trees.

Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan

ACM Trans. Comput. Log., 2005

Lowness for the Class of Schnorr Random Reals.

Bjørn Kjos-Hanssen, André Nies, Frank Stephan

SIAM J. Comput., 2005

Randomness, relativization and Turing degrees.

André Nies, Frank Stephan, Sebastiaan Terwijn

J. Symb. Log., 2005

The dot-depth and the polynomial hierarchies correspond on the delta levels.

Bernd Borchert, Klaus-Jörn Lange, Frank Stephan, Pascal Tesson, Denis Thérien

Int. J. Found. Comput. Sci., 2005

Lowness Properties and Approximations of the Jump.

Santiago Figueira, André Nies, Frank Stephan

Proceedings of the 12th Workshop on Logic, Language, Information and Computation, 2005

Presentations of K-Trivial Reals and Kolmogorov Complexity.

Frank Stephan, Guohua Wu

Proceedings of the New Computational Paradigms, 2005

2004

Learning how to separate.

Sanjay Jain, Frank Stephan

Theor. Comput. Sci., 2004

Trees and learning.

Wolfgang Merkle, Frank Stephan

J. Comput. Syst. Sci., 2004

Robust learning--rich and poor.

John Case, Sanjay Jain, Frank Stephan, Rolf Wiehagen

J. Comput. Syst. Sci., 2004

Generalized notions of mind change complexity.

Arun Sharma, Frank Stephan, Yuri Ventsov

Inf. Comput., 2004

Counting extensional differences in BC-learning.

Sanjay Jain, Frank Stephan, Sebastiaan Terwijn

Inf. Comput., 2004

Classes with easily learnable subclasses.

Sanjay Jain, Wolfram Menzel, Frank Stephan

Inf. Comput., 2004

On the classification of recursive languages.

John Case, Efim B. Kinber, Arun Sharma, Frank Stephan

Inf. Comput., 2004

A Polynomial Time Learner for a Subclass of Regular Patterns

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann

Electron. Colloquium Comput. Complex., 2004

Definability and Regularity in Automatic Structures.

Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan

Proceedings of the STACS 2004, 2004

The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels.

Bernd Borchert, Klaus-Jörn Lange, Frank Stephan, Pascal Tesson, Denis Thérien

Proceedings of the Developments in Language Theory, 2004

Finding Isolated Cliques by Queries -- An Approach to Fault Diagnosis with Many Faults.

William I. Gasarch, Frank Stephan

Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

2003

Refuting learning revisited.

Wolfgang Merkle, Frank Stephan

Theor. Comput. Sci., 2003

Learning power and language expressiveness.

Eric Martin, Arun Sharma, Frank Stephan

Theor. Comput. Sci., 2003

Topological aspects of numberings.

Wolfram Menzel, Frank Stephan

Math. Log. Q., 2003

Learning by switching type of information.

Sanjay Jain, Frank Stephan

Inf. Comput., 2003

Strong Reductions and Immunity for Exponential Time.

Marcus Schaefer, Frank Stephan

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

On Automatic Partial Orders.

Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

2002

Learning classes of approximations to non-recursive function.

Frank Stephan, Thomas Zeugmann

Theor. Comput. Sci., 2002

Avoiding coding tricks by hyperrobust learning.

Matthias Ott, Frank Stephan

Theor. Comput. Sci., 2002

Learning to Win Process-Control Games Watching Game-Masters.

John Case, Matthias Ott, Arun Sharma, Frank Stephan

Inf. Comput., 2002

Trivial Reals.

Rodney G. Downey, Denis R. Hirschfeldt, André Nies, Frank Stephan

Proceedings of the Computability and Complexity in Analysis, 2002

Classes bounded by incomplete sets.

Kejia Ho, Frank Stephan

Ann. Pure Appl. Log., 2002

Learning in Logic with RichProlog.

Eric Martin, Phuong Minh Nguyen, Arun Sharma, Frank Stephan

Proceedings of the Logic Programming, 18th International Conference, 2002

Learning, Logic, and Topology in a Common Framework.

Eric Martin, Arun Sharma, Frank Stephan

Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

2001

Learning algebraic structures from text.

Frank Stephan, Yuri Ventsov

Theor. Comput. Sci., 2001

Robust learning with infinite additional information.

Susanne Kaufmann, Frank Stephan

Theor. Comput. Sci., 2001

Predictive learning models for concept drift.

John Case, Sanjay Jain, Susanne Kaufmann, Arun Sharma, Frank Stephan

Theor. Comput. Sci., 2001

On The Structures Inside Truth-Table Degrees.

Frank Stephan

J. Symb. Log., 2001

On one-sided versus two-sided classification.

Frank Stephan

Arch. Math. Log., 2001

A General Theory of Deduction, Induction, and Learning.

Eric Martin, Arun Sharma, Frank Stephan

Proceedings of the Discovery Science, 4th International Conference, DS 2001, Washington, 2001

Hausdorff Dimension in Exponential Time.

Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Structural measures for games and process control in the branch learning model.

Matthias Ott, Frank Stephan

Theor. Comput. Sci., 2000

Vacillatory and BC learning on noisy data.

John Case, Sanjay Jain, Frank Stephan

Theor. Comput. Sci., 2000

Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.

Bernd Borchert, Frank Stephan

Math. Log. Q., 2000

The Comlexity of Odd^A_n.

Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy H. McNicholl, Frank Stephan

J. Symb. Log., 2000

Robust Learning Aided by Context.

John Case, Sanjay Jain, Matthias Ott, Arun Sharma, Frank Stephan

J. Comput. Syst. Sci., 2000

Counting Extensional Differences in BC-Learning.

Frank Stephan, Sebastiaan Terwijn

Proceedings of the Grammatical Inference: Algorithms and Applications, 2000

Unlearning Helps.

Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan

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

Average-Case Complexity of Learning Polynomials.

Frank Stephan, Thomas Zeugmann

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.

Henning Fernau, Frank Stephan

J. Autom. Lang. Comb., 1999

The Complexity of Universal Text-Learners.

Frank Stephan, Sebastiaan Terwijn

Inf. Comput., 1999

On the Uniform Learnability of Approximations to Non-Recursive Functions.

Frank Stephan, Thomas Zeugmann

Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

The VC-Dimension of Subclasses of Pattern.

Andrew R. Mitchell, Tobias Scheffer, Arun Sharma, Frank Stephan

Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

1998

On the Relative Sizes of Learnable Sets.

Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan

Theor. Comput. Sci., 1998

Learning via Queries and Oracles.

Frank Stephan

Ann. Pure Appl. Log., 1998

Classification Using Information.

William I. Gasarch, Mark G. Pleszkoch, Frank Stephan, Mahendran Velauthapillai

Ann. Math. Artif. Intell., 1998

Learning Algebraic Structures from Text Using Semantical Knowledge.

Frank Stephan, Yuri Ventsov

Proceedings of the Algorithmic Learning Theory, 9th International Conference, 1998

1997

Noisy Inference and Oracles.

Frank Stephan

Theor. Comput. Sci., 1997

Correction to "A Cohesive Set which is not High".

Carl G. Jockusch Jr., Frank Stephan

Math. Log. Q., 1997

On Existentially First-Order Definable Languages and their Relation to NP

Bernd Borchert, Dietrich Kuske, Frank Stephan

Electron. Colloquium Comput. Complex., 1997

On the Classification of Computable Languages.

John Case, Efim B. Kinber, Arun Sharma, Frank Stephan

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.

Matthias Ott, Frank Stephan

Proceedings of the Algorithms and Computation, 8th International Symposium, 1997

How Powerful is Unconditional Transfer? - When UT meets AC.

Henning Fernau, Frank Stephan

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.

Susanne Kaufmann, Frank Stephan

Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996

Inclusion Problems in Parallel Learning and Games.

Martin Kummer, Frank Stephan

J. Comput. Syst. Sci., 1996

On the Structure of Degrees of Inferability.

Martin Kummer, Frank Stephan

J. Comput. Syst. Sci., 1996

Looking for an Analogue of Rice's Theorem in Complexity Theory

Bernd Borchert, Frank Stephan

Electron. Colloquium Comput. Complex., 1996

On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

Bernd Borchert, Desh Ranjan, Frank Stephan

Electron. Colloquium Comput. Complex., 1996

On the Query Complexity of Sets.

Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan

Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

1995

Approximable Sets

Richard Beigel, Martin Kummer, Frank Stephan

Inf. Comput., August, 1995

Recursion Theoretic Properties of Frequency Computation and Bounded Queries

Martin Kummer, Frank Stephan

Inf. Comput., July, 1995

Quantifying the Amount of Verboseness

Richard Beigel, Martin Kummer, Frank Stephan

Inf. Comput., April, 1995

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

Efim B. Kinber, Frank Stephan

Inf. Comput., 1995

Measure, Category and Learning Theory.

Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

The Power of Frequency Computation (Extended Abstract).

Martin Kummer, Frank Stephan

Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

Language Learning from Texts: Mind Changes, Limited Memory and Monotonicity (Extended Abstract).

Efim B. Kinber, Frank Stephan

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

Effective Search Problems.

Frank Stephan, Martin Kummer

Math. Log. Q., 1994

Extremes in the Degrees of Inferability.

Lance Fortnow, William I. Gasarch, Sanjay Jain, Efim B. Kinber, Martin Kummer, Stuart A. Kurtz, Mark Pleszkovich, Theodore A. Slaman, Robert Solovay, Frank Stephan

Ann. Pure Appl. Log., 1994

Inclusion Problems in Parallel Learning and Games (Extended Abstract).

Martin Kummer, Frank Stephan

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

On Optimizing Diameter and Average Distance of Directed Interconnected Networks.

Heinrich Braun, Frank Stephan

IEEE Trans. Computers, 1993

A Cohesive Set which is not High.

Frank Stephan, Carl G. Jockusch Jr.

Math. Log. Q., 1993

Weakly Semirecursive Sets and r.e. Orderings.

Martin Kummer, Frank Stephan

Ann. Pure Appl. Log., 1993

Recursion Theoretic Properties of Frequency Computation and Bounded Queries (Extended Abstract).

Martin Kummer, Frank Stephan

Proceedings of the Computational Logic and Proof Theory, Third Kurt Gödel Colloquium, 1993

1990

X-Raeume als Verallgemeinerung topologischer Raeume

Frank Stephan

PhD thesis, 1990