Frank Stephan

According to our database1, Frank Stephan authored at least 221 papers between 1992 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space.
STTT, 2019

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

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

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

Randomness and Solovay degrees.
J. Logic & Analysis, 2018

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

Equivalences between learning of data and probability distributions, and their applications.
Inf. 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

Learners Based on Transducers.
Proceedings of the Language and Automata Theory and Applications, 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

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

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

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

On Martin's pointed tree theorem.
Computability, 2016

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

Finitely Generated Semiautomatic Groups.
Proceedings of the Pursuit of the Universal - 12th Conference on Computability in Europe, 2016

Learning Pattern Languages over Groups.
Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

2015
Deterministic Frequency Pushdown Automata.
J. UCS, 2015

Partial functions and domination.
Logical Methods in Computer Science, 2015

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

Inductive Inference and Reverse Mathematics.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Depth, Highness and DNR Degrees.
Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

Covering the Recursive Sets.
Proceedings of the Evolving Computability - 11th Conference on Computability in Europe, 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
Things that can be made into themselves.
Inf. Comput., 2014

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

Algorithmic Aspects of Lipschitz Functions.
Computability, 2014

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

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

Finite State Incompressible Infinite Sequences.
Proceedings of the Theory and Applications of Models of Computation, 2014

Semiautomatic Structures.
Proceedings of the Computer Science - Theory and Applications, 2014

On the Role of Update Constraints and Text-Types in Iterative Learning.
Proceedings of the Algorithmic Learning Theory - 25th International Conference, 2014

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

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

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

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

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

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

Effectivity Questions for Kleene's Recursion Theorem.
Proceedings of the Logical Foundations of Computer Science, International Symposium, 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

Partial Learning of Recursively Enumerable Languages.
Proceedings of the Algorithmic Learning Theory - 24th International Conference, 2013

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

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

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

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

The Complexity of Verbal Languages over Groups.
Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

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

Automatic Functions, Linear Time and Learning.
Proceedings of the How the World Computes, 2012

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

Enlarging Learnable Classes.
Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

Confident and Consistent Partial Learning of Recursive Functions.
Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

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

2011
Van Lambalgen's Theorem and High Degrees.
Notre Dame Journal of Formal Logic, 2011

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

Closed Left-R.E. Sets.
Proceedings of the Theory and Applications of Models of Computation, 2011

Automatic Learning of Subclasses of Pattern Languages.
Proceedings of the Language and Automata Theory and Applications, 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

Automatic Learners with Feedback Queries.
Proceedings of the Models of Computation in Context, 2011

Learning and Classifying.
Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

Robust Learning of Automatic Classes of Languages.
Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 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

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

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

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

Learnability of Automatic Classes.
Proceedings of the Language and Automata Theory and Applications, 2010

Initial Segment Complexities of Randomness Notions.
Proceedings of the Theoretical Computer Science, 2010

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

How Powerful Are Integer-Valued Martingales?
Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

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

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

Consistent Partial Identification.
Proceedings of the COLT 2009, 2009

Index Sets and Universal Numberings.
Proceedings of the Mathematical Theory and Computational Practice, 2009

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

Uncountable Automatic Classes and Learning.
Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009

2008
Preface.
Theor. Comput. Sci., 2008

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

Immunity and Hyperimmunity for Sets of Minimal Indices.
Notre Dame Journal of Formal Logic, 2008

When unlearning helps.
Inf. Comput., 2008

Prescribed Learning of Indexed Families.
Fundam. Inform., 2008

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

Lowness properties and approximations of the jump.
Ann. Pure Appl. Logic, 2008

I classes, LR degrees and Turing degrees.
Ann. Pure Appl. Logic, 2008

Universal Recursively Enumerable Sets of Strings.
Proceedings of the Developments in Language Theory, 12th International Conference, 2008

Numberings Optimal for Learning.
Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

Iterative Learning of Simple External Contextual Languages.
Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

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

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

Applications of Kolmogorov complexity to computable model theory.
J. Symb. Log., 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

Input-Dependence in Function-Learning.
Proceedings of the Computation and Logic in the Real World, 2007

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

Prescribed Learning of R.E. Classes.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

Learning in Friedberg Numberings.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

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

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

Lowness Properties and Approximations of the Jump.
Electr. Notes Theor. Comput. Sci., 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

Invertible Classes.
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

Kolmogorov-Loveland Randomness and Stochasticity.
Proceedings of the STACS 2005, 2005

Variations on U-Shaped Learning.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

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

Randomness and Universal Machines.
Proceedings of the CCA 2005, 2005

Absolute Versus Probabilistic Classification in a Logical Setting.
Proceedings of the Algorithmic Learning Theory, 16th International Conference, 2005

Non U-Shaped Vacillatory and Team Learning.
Proceedings of the Algorithmic Learning Theory, 16th International Conference, 2005

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

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

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

Identifying Clusters from Positive Data
Electronic Colloquium on Computational Complexity (ECCC), 2004

A Polynomial Time Learner for a Subclass of Regular Patterns
Electronic Colloquium on Computational Complexity (ECCC), 2004

Enumerations of the Kolmogorov Function
Electronic Colloquium on Computational Complexity (ECCC), 2004

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

Automatic Structures: Richness and Limitations.
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

Identifying Clusters from Positive Data.
Proceedings of the Grammatical Inference: Algorithms and Applications, 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

On the Data Consumption Benefits of Accepting Increased Uncertainty.
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

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

Topological aspects of numberings.
Math. Log. Q., 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

Infinitely-Often Autoreducible Sets.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

On Ordinal VC-Dimension and Some Notions of Complexity.
Proceedings of the Algorithmic Learning Theory, 14th International Conference, 2003

Learning a Subclass of Regular Patterns in Polynomial Time.
Proceedings of the Algorithmic Learning Theory, 14th International Conference, 2003

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

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

Classes bounded by incomplete sets.
Ann. Pure Appl. Logic, 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

Classes with Easily Learnable Subclasses.
Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

On the Learnability of Vector Spaces.
Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

2001
Learning algebraic structures from text.
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

Robust Learning - Rich and Poor.
Proceedings of the Computational Learning Theory, 2001

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

Refuting Learning Revisited.
Proceedings of the Algorithmic Learning Theory, 12th International Conference, 2001

Learning How to Separate.
Proceedings of the Algorithmic Learning Theory, 12th International Conference, 2001

Learning by Switching Type of Information.
Proceedings of the Algorithmic Learning Theory, 12th International Conference, 2001

2000
The Comlexity of OddAn.
J. Symb. Log., 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.
Journal of Automata, Languages and Combinatorics, 1999

Avoiding Coding Tricks by Hyperrobust Learning.
Proceedings of the Computational Learning Theory, 4th European Conference, 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

On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions.
Theory Comput. Syst., 1998

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

On Existentially First-Order Definable Languages and Their Relation to NP.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Robust Learning Aided by Context.
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

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

Learning to Win Process-Control Games Watching Game-Masters.
Proceedings of the Algorithmic Learning Theory, 9th International Conference, 1998

Predictive Learning Models for Concept Drift.
Proceedings of the Algorithmic Learning Theory, 9th International Conference, 1998

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
Electronic Colloquium on Computational Complexity (ECCC), 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

Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.
Proceedings of the Computational Logic and Proof Theory, 5th Kurt Gödel Colloquium, 1997

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

The Complexity of Universal Text-Learners.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

Structural Measures for Games and Process Control in the Branch Learning Model.
Proceedings of the Computational Learning Theory, Third European Conference, 1997

Robust Learning with Infinite Additional Information.
Proceedings of the Computational Learning Theory, Third European Conference, 1997

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

Generalized Notions of Mind Change Complexity.
Proceedings of the Tenth Annual Conference on Computational Learning 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

Looking for an Analogue of Rice's Theorem in Complexity Theory
Electronic Colloquium on Computational Complexity (ECCC), 1996

On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions
Electronic Colloquium on Computational Complexity (ECCC), 1996

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

Trees and Learning.
Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996

Vacillatory and BC Learning on Noisy Data.
Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 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

Learning via Queries and Oracles.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

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

Noisy Inference and Oracles.
Proceedings of the Algorithmic Learning Theory, 6th International Conference, 1995

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

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

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

Approximable Sets.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

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

Weakly Semirecursive Sets and r.e. Orderings.
Ann. Pure Appl. Logic, 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

On the Structure of Degrees of Inferability.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992
Quantifying the Amount of Verboseness.
Proceedings of the Logical Foundations of Computer Science, 1992


  Loading...