2024
A Bisection Approach to Subcubic Maximum Induced Matching.
Proceedings of the WALCOM: Algorithms and Computation, 2024
2023
String compression in FA-presentable structures.
Theor. Comput. Sci., February, 2023
Addition machines, automatic functions and open problems of Floyd and Knuth.
J. Comput. Syst. Sci., 2023
Languages given by Finite Automata over the Unary Alphabet.
CoRR, 2023
Languages Given by Finite Automata over the Unary Alphabet.
Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023
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
Lamplighter groups and automata.
Acta Informatica, 2022
Alternating Automatic Register Machines.
Proceedings of the Theoretical Aspects of Computing - ICTAC 2022, 2022
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
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
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
Intrinsic complexity of partial learning.
Theor. Comput. Sci., 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
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
2018
Learning pattern languages over groups.
Theor. Comput. Sci., 2018
Effectivity questions for Kleene's recursion theorem.
Theor. Comput. Sci., 2018
Finitely generated semiautomatic groups.
Comput., 2018
On the Help of Bounded Shot Verifiers, Comparators and Standardisers for Learnability in Inductive Inference.
Proceedings of the Algorithmic Learning Theory, 2018
2017
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017
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
Connections Between Inductive Inference and Machine Learning.
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017
Enumerations including laconic enumerators.
Theor. Comput. Sci., 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
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
Automatic Learning from Repetitive Texts.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017
2016
Theor. Comput. Sci., 2016
Tree-automatic scattered linear orders.
Theor. Comput. Sci., 2016
Parallel learning of automatic classes of 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
How to verify computation with a rational network.
CoRR, 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
When Cryptocurrencies Mine Their Own Business.
Proceedings of the Financial Cryptography and Data Security, 2016
2015
Deterministic Frequency Pushdown Automata.
J. Univers. Comput. Sci., 2015
Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015
2014
Robust learning of automatic classes of languages.
J. Comput. Syst. Sci., 2014
Automatic learners with feedback queries.
J. Comput. Syst. Sci., 2014
Graphs realised by r.e. equivalence relations.
Ann. Pure Appl. Log., 2014
Learning from Positive Data and Negative Counterexamples: A Survey.
Proceedings of the Computing with New Resources, 2014
2013
Theor. Comput. Sci., 2013
Mind change speed-up for learning languages from positive data.
Theor. Comput. Sci., 2013
Learning and classifying.
Theor. Comput. Sci., 2013
Automatic functions, linear time and learning.
Log. Methods Comput. Sci., 2013
On Conservative Learning of Recursively Enumerable Languages.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013
Proceedings of the Algorithmic Learning Theory - 24th International Conference, 2013
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
Automatic Learning from Positive Data and Negative Counterexamples.
Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012
2011
Uncountable automatic classes and learning.
Theor. Comput. Sci., 2011
Rice and Rice-Shapiro Theorems for transfinite correction grammars.
Math. Log. Q., 2011
Iterative learning from texts and counterexamples using additional information.
Mach. Learn., 2011
Index sets and universal numberings.
J. Comput. Syst. Sci., 2011
Hypothesis spaces for learning.
Inf. Comput., 2011
2010
Proceedings of the Encyclopedia of Machine Learning, 2010
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
Connections Between Inductive Inference and Machine Learning.
Proceedings of the Encyclopedia of Machine Learning, 2010
Incremental learning with temporary memory.
Theor. Comput. Sci., 2010
Iterative learning of simple external contextual languages.
Theor. Comput. Sci., 2010
Numberings optimal for learning.
J. Comput. Syst. Sci., 2010
Regular patterns, regular languages and context-free languages.
Inf. Process. Lett., 2010
Inductive Inference of Languages from Samplings.
Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010
2009
Prescribed learning of r.e. classes.
Theor. Comput. Sci., 2009
One-shot learners using negative counterexamples and nearest positive examples.
Theor. Comput. Sci., 2009
Input-Dependence in Function-Learning.
Theory Comput. Syst., 2009
Learning correction grammars.
J. Symb. Log., 2009
On some open problems in monotonic and conservative learning.
Inf. Process. Lett., 2009
On some open problems in reflective inductive inference.
Inf. Process. Lett., 2009
Consistent Partial Identification.
Proceedings of the COLT 2009, 2009
Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009
2008
Absolute versus probabilistic classification in a logical setting.
Theor. Comput. Sci., 2008
Learning and extending sublanguages.
Theor. Comput. Sci., 2008
Mitotic Classes in Inductive Inference.
SIAM J. Comput., 2008
Learning languages from positive data and negative counterexamples.
J. Comput. Syst. Sci., 2008
Non-U-shaped vacillatory and team learning.
J. Comput. Syst. Sci., 2008
Learning in Friedberg numberings.
Inf. Comput., 2008
Prescribed Learning of Indexed Families.
Fundam. Informaticae, 2008
2007
Theor. Comput. Sci., 2007
A general comparison of language learning from examples and from queries.
Theor. Comput. Sci., 2007
Learning languages from positive data and a limited number of short counterexamples.
Theor. Comput. Sci., 2007
Learning multiple languages in groups.
Theor. Comput. Sci., 2007
Learning languages in a union.
J. Comput. Syst. Sci., 2007
Some natural conditions on incremental learning.
Inf. Comput., 2007
Iterative learning from positive data and negative counterexamples.
Inf. Comput., 2007
Results on memory-limited U-shaped learning.
Inf. Comput., 2007
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007
2006
Learning a subclass of regular patterns in polynomial time.
Theor. Comput. Sci., 2006
Learning languages from positive data and a finite number of queries.
Inf. Comput., 2006
Variations on U-shaped learning.
Inf. Comput., 2006
Generality's price: Inescapable deficiencies in machine-learned programs.
Ann. Pure Appl. Log., 2006
Some Recent Results in U-Shaped Learning.
Proceedings of the Theory and Applications of Models of Computation, 2006
Memory-Limited U-Shaped Learning.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006
Towards a Better Understanding of Incremental Learning.
Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006
2005
Theor. Comput. Sci., 2005
On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms.
J. Comput. Syst. Sci., 2005
Proceedings of the Algorithmic Learning Theory, 16th International Conference, 2005
Gold-Style and Query Learning Under Various Constraints on the Target Class.
Proceedings of the Algorithmic Learning Theory, 16th International Conference, 2005
2004
Learning how to separate.
Theor. Comput. Sci., 2004
Parsimony hierarchies for inductive inference.
J. Symb. Log., 2004
Robust learning--rich and poor.
J. Comput. Syst. Sci., 2004
Counting extensional differences in BC-learning.
Inf. Comput., 2004
Classes with easily learnable subclasses.
Inf. Comput., 2004
Learning all subfunctions of a function.
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
2003
On learning of functions refutably.
Theor. Comput. Sci., 2003
Intrinsic complexity of learning geometrical concepts from positive data.
J. Comput. Syst. Sci., 2003
Learning by switching type of information.
Inf. Comput., 2003
On the intrinsic complexity of learning recursive functions.
Inf. Comput., 2003
The Intrinsic Complexity of Learning: A Survey.
Fundam. Informaticae, 2003
2002
Mind change complexity of learning logic programs.
Theor. Comput. Sci., 2002
Control structures in hypothesis spaces: the influence on learning.
Theor. Comput. Sci., 2002
2001
On the learnability of recursively enumerable languages from good examples.
Theor. Comput. Sci., 2001
Branch and bound on the network model.
Theor. Comput. Sci., 2001
Synthesizing noise-tolerant language learners.
Theor. Comput. Sci., 2001
Predictive learning models for concept drift.
Theor. Comput. Sci., 2001
Costs of general purpose learning.
Theor. Comput. Sci., 2001
Some Independence Results for Control Structures in Complete Numberings.
J. Symb. Log., 2001
On an open problem in classification of languages.
J. Exp. Theor. Artif. Intell., 2001
J. Comput. Syst. Sci., 2001
Language Learning from Texts: Degrees of Intrinsic Complexity and Their Characterizations.
J. Comput. Syst. Sci., 2001
Synthesizing Learners Tolerating Computable Noisy Data.
J. Comput. Syst. Sci., 2001
On a Generalized Notion of Mistake Bounds.
Inf. Comput., 2001
Learning Recursive Functions Refutably.
Proceedings of the Algorithmic Learning Theory, 12th International Conference, 2001
2000
Learning languages and functions by erasing.
Theor. Comput. Sci., 2000
Vacillatory and BC learning on noisy data.
Theor. Comput. Sci., 2000
Team Learning of Computable Languages.
Theory Comput. Syst., 2000
Robust Learning Aided by Context.
J. Comput. Syst. Sci., 2000
Language Learning From Texts: Degrees of Instrinsic Complexity and Their Characterizations.
Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000
1999
Ordinal Mind Change Complexity of Language Identification.
Theor. Comput. Sci., 1999
On a Question of Nearly Minimal Identification of Functions.
Inf. Process. Lett., 1999
Robust Behaviorally Correct Learning.
Inf. Comput., 1999
Incremental Concept Learning for Bounded Data Mining.
Inf. Comput., 1999
The Synthesis of Language Learners.
Inf. Comput., 1999
1998
Learning with Refutation.
J. Comput. Syst. Sci., 1998
Minimal Concept Identification and Reliability.
Int. J. Found. Comput. Sci., 1998
Dynamics of individual specialization and global diversification in communities.
Complex., 1998
Generalization and Specialization Strategies for Learning r.e. Languages.
Ann. Math. Artif. Intell., 1998
Generalized Replicator Dynamics as a Model of Specialization and Diversity in Societies.
Adv. Complex Syst., 1998
On the Power of Learning Robustly.
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998
1997
Kolmogorov Numberings and Minimal Identification.
Theor. Comput. Sci., 1997
Learning from Multiple Sources of Inaccurate Data.
SIAM J. Comput., 1997
The Structure of Intrinsic Complexity of Learning.
J. Symb. Log., 1997
Strong monotonic and set-driven inductive inference.
J. Exp. Theor. Artif. Intell., 1997
Elementary Formal Systems, Intrinsic Complexity, and Procrastination.
Inf. Comput., 1997
Characterizing Language Identification in Terms of Computable Numberings.
Ann. Pure Appl. Log., 1997
Learning of R.E. Languages from Good Examples.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997
1996
Learning in the Presence of Inaccurate Information.
Theor. Comput. Sci., 1996
Anomalous Learning Helps Succinctness.
Theor. Comput. Sci., 1996
The Intrinsic Complexity of Language Identification.
J. Comput. Syst. Sci., 1996
Program Synthesis in the Presence of Infinite Number of Inaccuracies.
J. Comput. Syst. Sci., 1996
Computational Limits on Team Identification of Languages.
Inf. Comput., 1996
Machine Induction Without Revolutionary Changes in Hypothesis Size.
Inf. Comput., 1996
Team Learning of Recursive Languages.
Proceedings of the PRICAI'96: Topics in Artificial Intelligence, 1996
Synthesizing Enumeration Techniques for Language Learning.
Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996
On Learning and Co-learning of Minimal Programs.
Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996
1995
Finite Identification of Functions by Teams with Success Ratio 1\over2 and Above
Inf. Comput., September, 1995
Complexity Issues for Vacillatory Function Identification
Inf. Comput., February, 1995
On Aggregating Teams of Learning Machines.
Theor. Comput. Sci., 1995
Prudence in Vacillatory Language Identification.
Math. Syst. Theory, 1995
Language Learning with Some Negative Information.
J. Comput. Syst. Sci., 1995
On a Question About Learning Nearly Minimal Programs.
Inf. Process. Lett., 1995
An Infinite Class of Functions Identifiable Using Minimal Programs in all Kolmogorov Numberings.
Int. J. Found. Comput. Sci., 1995
On Identification by Teams and Probabilistic Machines.
Proceedings of the Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, 1995
Not-So-Nearly-Minimal-Size Program Inference.
Proceedings of the Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, 1995
Machine Induction Without Revolutionary Paradigm Shifts.
Proceedings of the Algorithmic Learning Theory, 6th International Conference, 1995
1994
Approximate Inference and Scientific Method
Inf. Comput., November, 1994
Program Size Restrictions in Computational Learning.
Theor. Comput. Sci., 1994
Refinements of inductive inference by Popperian and reliable machines.
Kybernetika, 1994
Machine Learning of Higher-Order Programs.
J. Symb. Log., 1994
Characterizing Language Identification by Standardizing Operations.
J. Comput. Syst. Sci., 1994
Open Problems in "Systems That Learn".
J. Comput. Syst. Sci., 1994
Vacillatory Learning of Nearly Minimal Size Grammars.
J. Comput. Syst. Sci., 1994
Extremes in the Degrees of Inferability.
Ann. Pure Appl. Log., 1994
On Monotonic Strategies for Learning r.e. Languages.
Proceedings of the Algorithmic Learning Theory, 1994
1993
Learning with the Knowledge of an Upper Bound on Program Size
Inf. Comput., January, 1993
On the Non-Existence of Maximal Inference Degrees for Language Identification.
Inf. Process. Lett., 1993
Banishing Robust Turing Completeness.
Int. J. Found. Comput. Sci., 1993
Probability is More Powerful Than Team for Language Identification from Positive Data.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993
1992
Strong separation of learning classes.
J. Exp. Theor. Artif. Intell., 1992
On Learning Limiting Programs.
Int. J. Found. Comput. Sci., 1992
Prudence in Vacillatory Language Identification (Extended Abstract).
Proceedings of the Algorithmic Learning Theory, Third Workshop, 1992
1991
Learning in the Presence of Partial Explanations
Inf. Comput., December, 1991
On the Limitations of Locally Robust Positive Reductions.
Int. J. Found. Comput. Sci., 1991
1990
Hypothesis Formation and Language Acquisition with an Infinitely-Often Correct Teacher.
Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge, 1990
Language Learning by a "Team" (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990
Finite Learning by a "Team".
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990
Anomalous Learning Helps Succinctness (Extended Abstract).
Proceedings of the Algorithmic Learning Theory, First International Workshop, 1990
1989
Convergence to Nearly Minimal Size Grammars by Vacillating Learning Machines.
Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989
