**publications**of the Laboratory for Algorithmics, listed in reverse chronological order.

## 2021

### Journals

Sanjay Jain, Frank Stephan, and Thomas Zeugmann.
On the amount of
nonconstructivity in learning formal languages from text.
*Information and Computation*, **xx**, 2021.
Available on-line 23 November 2020.

### Technical Reports

David Avis and Charles Jordan. lrsarith: a small fixed/hybrid arithmetic C library. arXiv:2101.12425 [cs.MS], January 2021.

## 2020

### Journals

David Avis and Charles Jordan.
mts: a light
framework for parallelizing tree search codes.
*Optimization Methods and Software*, **xx**, 2020.
published on-line November 2019.

### International Conferences

Thomas Zeugmann.
On the interplay
between inductive inference of recursive functions, complexity theory and
recursive numberings.
In Marcella Anselmo, Gianluca Della Vedova, Florin Manea, and Arno Pauly,
editors, *Beyond the Horizon of Computability, 16th Conference on
Computability in Europe, CiE 2020, Fisciano, Italy, June 29-July 3, 2020,
Proceedings*, volume 12098 of *Lecture Notes in Computer Science*,
pages 124-136. Springer International Publishing, Cham, Switzerland, 2020.

## 2019

### Technical Reports

Thomas Zeugmann.
Taking discrete roots in the field *Z _{p}* and in the
ring

*Z*. Technical Report TCS-TR-A-19-83, Division of Computer Science, Hokkaido University, 2019.

_{pe}## 2018

### Journals

David Avis and Charles Jordan.
mplrs: A scalable
parallel vertex/facet enumeration code.
*Mathematical Programming Computation*, **10** no. 2 pp. 267-302,
2018.

Charles Jordan, Michael Joswig, and Lars Kastner.
Parallel enumeration of
triangulations.
*The Electronic Journal of Combinatorics*, **25** no. 3 pp. P3.6,
2018.

### International Conferences

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann.
On the help of
bounded shot verifiers, comparators, and standardisers for learnability in
inductive inference.
In Firdaus Janoos, Mehryar Mohri, and Karthik Sridharan, editors,
*Proceedings of Algorithmic Learning Theory*, volume 83 of
*Proceedings of Machine Learning Research*, pages 413-437, Lanzarote,
Spain, 7-9 April 2018. PMLR.

### Local Conferences and Workshops

Shosuke Oba and Thomas Zeugmann.
Lattice reduction attack on the knapsack type cryptosystem.
In *第17回情報科学技術フォーラム (Forum on Information
Technology), 福岡工業大学,September 19-21, 2018*, FIT, pages
77-78, 2018.

### Editorial Work

Thomas Zeugmann.
(Guest Editor), Learning Theory and Complexity.
Special Issue in *Theoretical Computer Science* 733, 2018.

Thomas Zeugmann.
Guest Editor's
Foreword.
*Theoretical Computer Science*, **733** pp. 1-3, 2018.
Special Issue on Learning Theory and Complexity.

## 2017

### Book Chapters

Thomas Zeugmann.
Epsilon cover.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning and Data Mining*, pages 408-409. Springer US, New York, first
edition, 2017.
Invited contribution.

Thomas Zeugmann.
Epsilon nets.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning and Data Mining*, pages 409-410. Springer US, New York, first
edition, 2017.
Invited contribution.

Thomas Zeugmann.
VC
dimension.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning and Data Mining*, pages 1323-1327. Springer US, New York, first
edition, 2017.
Invited contribution.

Thomas Zeugmann.
Stochastic finite
learning.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning and Data Mining*, pages 1187-1191. Springer US, New York, first
edition, 2017.
Invited contribution.

Thomas Zeugmann.
PAC
learning.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning and Data Mining*, pages 949-959. Springer US, New York, first
edition, 2017.
Invited contribution.

### Technical Reports

David Avis and Charles Jordan. mts: a light framework for parallelizing tree search codes. arXiv:1709.07605 [cs.DC], September 2017.

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann. On the help of bounded shot verifiers, comparers, and standardisers in inductive inference. Technical Report TCS-TR-A-17-82, Division of Computer Science, Hokkaido University, 2017.

Charles Jordan, Michael Joswig, and Lars Kastner. Parallel enumeration of triangulations. arXiv:1709.04746 [math.CO], September 2017.

## 2016

### Books

Werner Römisch and Thomas Zeugmann.
*Mathematical
Analysis and the Mathematics of Computation*.
Springer International Publishing AG, Cham, Switzerland, 2016.

### Journals

Mikoláš Janota, Charles Jordan, Will Klieber, Florian Lonsing,
Martina Seidl, and Allen Van Gelder.
QBF
Gallery 2014: The QBF competition at the FLoC 2014 Olympic
Games..
*Journal on Satisfiability, Boolean Modeling and Computation*,
**9** pp. 187-206, 2016.

Charles Jordan and Thomas Zeugmann.
The
Kahr-Moore-Wang class contains untestable properties.
*Baltic Journal of Modern Computing*, **4** no. 4 pp. 736-752,
2016.
Special Issue in memory of Rūsiņš Freivalds.

Thomas Zeugmann.
Obituary Rūsiņš Mārtiņš Freivalds
(1942-2016).
*Bulletin of the EATCS*, **118** pp. 17-20, 2016.

### International Conferences

Charles Jordan, Will Klieber, and Martina Seidl.
Non-CNF QBF
solving with QCIR.
In *Beyond NP, Papers from the 2016 AAAI Workshop, Phoenix, Arizona,
USA, February 12, 2016*, volume WS-16-05 of *AAAI Workshops*,
pages 320-326. AAAI Press, 2016.

### Editorial Work

Peter Auer, Alexander Clark, and Thomas Zeugmann. (Guest Editors), Algorithmic Learning Theory. Special Issue in \emphTheoretical Computer Science 650, 2016.

Peter Auer, Alexander Clark, and Thomas Zeugmann.
Guest Editors'
Foreword.
*Theoretical Computer Science*, **650** pp. 1-3, 2016.
Special Issue: Algorithmic Learning Theory.

Sanjay Jain, Rémi Munos, Frank Stephan, and Thomas Zeugmann. (Guest Editors), Algorithmic Learning Theory. Special Issue in \emphTheoretical Computer Science 620, 2016.

Sanjay Jain, Rémi Munos, Frank Stephan, and Thomas Zeugmann.
Guest Editors' Foreword.
*Theoretical Computer Science*, **620** pp. 1-3, 2016.
Special Issue: Algorithmic Learning Theory.

### Technical Reports

David Avis and Charles Jordan. A parallel framework for reverse search using mts. arXiv:1610.07735 [cs.DC], October 2016.

Charles Jordan and Łukasz Kaiser. Machine learning with guarantees using descriptive complexity and smt solvers. arXiv:1609.02664 [cs.LG], September 2016.

## 2015

### International Conferences

Yu Zhu and Thomas Zeugmann.
Image analysis in a
parameter-free setting.
In Omer H. Abdelrahman, Erol Gelenbe, Gokce Gorbil, and Ricardo Lent,
editors, *Information Sciences and Systems 2015, 30th International
Symposium on Computer and Information Sciences (ISCIS 2015)*, volume 363
of *Lecture Notes in Electrical Engineering*, pages 285-294, Cham,
Heidelberg, New York, Dordrecht, London, 2015. Springer International
Publishing.

### Local Conferences and Workshops

Diptarama, Yuya Ishiguro, Kazuyuki Narisawa, Ayumi Shinohara, and Charles Jordan. Solving generalized tic-tac-toe by using qbf solver. In The 20th Game Programming Workshop 2015 (GPW-15), in Japanese, 2015.

### Technical Reports

David Avis and Charles Jordan. Comparative computational results for some vertex and facet enumeration codes. arXiv:1510.02545 [cs.MS], October 2015.

## 2014

### Journals

Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka,
Akihiro Kishimoto, Koji Tsuda, and Shin-ichi Minato.
Distribution loss
minimization with guaranteed error bound.
*IEEE Transactions on Smart Grid*, **5** no. 1 pp. 102-111, 2014.

Yuma Inoue, Takahisa Toda, and Shin-ichi Minato.
Implicit
generation of pattern-avoiding permutations by using permutation decision
diagrams.
*IEICE Transactions*, **97-A** no. 6 pp. 1171-1179, 2014.

Ilja Kucevalovs, Ojārs Krasts, Rūsiņš Freivalds, and Thomas
Zeugmann.
On the influence of
technology on learning processes.
*Parallel Processing Letters*, **24** no. 2 pp. 63-79, 2014.

### Editorial Work

Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, editors.
*Algorithmic
Learning Theory, 25th International Conference, ALT 2014, Bled, Slovenia,
October 8-10, 2014, Proceedings*, volume 8776 of *Lecture Notes in
Artificial Intelligence*, Berlin, Heidelberg, New York, October 2014.
Springer.

Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles.
Editors'
introduction.
In Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, editors,
*Algorithmic Learning Theory, 25th International Conference, ALT 2014,
Bled, Slovenia, October 8-10, 2014, Proceedings*, volume 8776 of
*Lecture Notes in Artificial Intelligence*, pages 1-7, Berlin,
Heidelberg, New York, 2014. Springer.

Nader H. Bshouty, Gilles Stoltz, Nicolas Vayatis, and Thomas Zeugmann.
Guest Editors' foreword.
*Theoretical Computer Science*, **558** pp. 1-4, 2014.

Jyrki Kivinen, Csaba Szepesvári, and Thomas Zeugmann.
Guest Editors' introduction.
*Theoret. Comput. Sci.*, **519** pp. 1-3, 2014.
Special Issue: Algorithmic Learning Theory.

Shigeru Yamashita and Shin-ichi Minato, editors.
*Reversible
Computation, 6th International Conference, RC 2014, Kyoto, Japan, July 10-11,
2014. Proceedings*, volume 8507 of *Lecture Notes in Computer
Science*. Springer International Publishing, 2014.

### International Conferences

Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi
Minato, and Kunihiko Sadakane.
DenseZDD: A
compact and fast index for families of sets.
In Joachim Gudmundsson and Jyrki Katajainen, editors, *Experimental
Algorithms, 13th International Symposium, SEA 2014, Copenhagen, Denmark, June
29-July 1, 2014. Proceedings*, pages 187-198, 2014.

Rūsiņš Freivalds and Thomas Zeugmann.
Active learning of
recursive functions by ultrametric algorithms.
In Viliam Geffert, Bart Preneel, Branislav Rovan, Július Štuller,
and A Min Tjoa, editors, *SOFSEM 2014: Theory and Practice of Computer
Science, 40th International Conference on Current Trends in Theory and
Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29,
2014, Proceedings*, volume 8327 of *Lecture Notes in Computer
Science*, pages 246-257, Cham, Heidelberg, New York, Dordrecht, London,
2014. Springer International Publishing Switzerland.

Charles Jordan, Lukasz Kaiser, Florian Lonsing, and Martina Seidl.
MPIDepQBF:
Towards parallel QBF solving without knowledge sharing.
In Carsten Sinz and Uwe Egly, editors, *Theory and Applications of
Satisfiability Testing - SAT 2014, 17th International Conference, Held as
Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17,
2014, Proceedings*, volume 8561 of *Lecture Notes in Computer
Science*, pages 430-437, Cham, Heidelberg, New York, Dordrecht, London,
2014. Springer International Publishing.

Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese.
A fast method of
statistical assessment for combinatorial hypotheses based on frequent itemset
enumeration.
In Toon Calders, Floriana Esposito, Eyke Hüllermeier, and Rosa Meo,
editors, *Machine Learning and Knowledge Discovery in Databases, European
Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014.
Proceedings, Part II*, volume 8725 of *Lecture Notes in Computer
Science*, pages 422-436. Springer International Publishing, 2014.

Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, and Masaaki Nagata.
Accelerating graph
adjacency matrix multiplications with adjacency forest.
In *2014 SIAM International Conference on Data Mining, April 24-26, 2014,
Sheraton Society Hill Hotel, Philadelphia, Pennsylvania, USA*, pages
1073-1081. SIAM Publications, 2014.

### Technical Reports

Takeru Inoue, Norihito Yasuda, Shunsuke Kawano, Yuji Takenobu, Shin-ichi Minato, and Yasuhiro Hayashi. Verifying distribution networks for secure restoration by enumerating all critical failures. Technical Report TCS-TR-A-14-70, Division of Computer Science, Hokkaido University, 2014.

Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato, and Kunihiko Sadakane. A compact and fast index structure for families of sets. Technical Report TCS-TR-A-14-71, Division of Computer Science, Hokkaido University, 2014.

Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese. Fast statistical assessment for combinatorial hypotheses based on frequent itemset mining. Technical Report TCS-TR-A-14-72, Division of Computer Science, Hokkaido University, 2014.

Ryutaro Kurai, Norihito Yasuda, Hiroki Arimura, Shinobu Nagayama, and Shin-ichi Minato. Fast regular expression matching using dual glushkov NFA. Technical Report TCS-TR-A-14-73, Division of Computer Science, Hokkaido University, 2014.

Takeru Inoue, Toru Mano, Kimihiro Mizutani, Shin-ichi Minato, and Osamu Akashi. Packet classification for global network view of software-defined networking. Technical Report TCS-TR-A-14-74, Division of Computer Science, Hokkaido University, 2014.

Yuma Inoue and Shin-ichi Minato. An efficient method of indexing all topological orders for a given DAG. Technical Report TCS-TR-A-14-75, Division of Computer Science, Hokkaido University, 2014.

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. Technical Report TCS-TR-A-14-76, Division of Computer Science, Hokkaido University, 2014.

Muhammad Kholilurrohman and Shin-ichi Minato. An efficient algorithm for enumerating eulerian paths. Technical Report TCS-TR-A-14-77, Division of Computer Science, Hokkaido University, 2014.

Yuma Inoue, Takahisa Toda, and Shin-ichi Minato. Generating sets of permutations with pattern occurrence counts using πDDs. Technical Report TCS-TR-A-14-78, Division of Computer Science, Hokkaido University, 2014.

Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi, and Shin-ichi Minato. Enumerating eulerian trails based on line graph conversion. Technical Report TCS-TR-A-14-79, Division of Computer Science, Hokkaido University, 2014.

## 2013

### Journals

Shin-ichi Minato.
Techniques of
BDD/ZDD: Brief history and recent activity.
*IEICE Transactions on Information and Systems*, **E96D** no. 7 pp.
1419-1429, 2013.

### Editorial Work

Marcus Hutter, Frank Stephan, Vladimir Vovk, and Thomas Zeugmann.
Guest Editors' foreword.
*Theoret. Comput. Sci.*, **473** pp. 1-3, 2013.
Special Issue on Algorithmic Learning Theory.

Sanjay Jain, Rémi Munos, Frank Stephan, and Thomas Zeugmann, editors.
*Algorithmic
Learning Theory, 24th International Conference, ALT 2013, Singapore,
October 6-9, 2013, Proceedings*, volume 8139 of *Lecture Notes in
Artificial Intelligence*, Berlin, Heidelberg, New York, October 2013.
Springer.

Sanjay Jain, Rémi Munos, Frank Stephan, and Thomas Zeugmann.
Editors'
introduction.
In Sanjay Jain, Rémi Munos, Frank Stephan, and Thomas Zeugmann, editors,
*Algorithmic Learning Theory, 24th International Conference, ALT 2013,
Singapore, October 6-9, 2013, Proceedings*, volume 8139 of *Lecture
Notes in Artificial Intelligence*, pages 1-12, Berlin, Heidelberg, New
York, 2013. Springer.

### International Conferences

Shuhei Denzumi, Koji Tsuda, Hiroki Arimura, and Shin-ichi Minato.
Compact complete
inverted files for texts and directed acyclic graphs based on sequence binary
decision diagrams.
In Jan Holub and Jan Žďárek, editors, *Proceedings of the
Prague Stringology Conference 2013*, pages 157-167, Czech Technical
University in Prague, Czech Republic, 2013.

Rūsiņš Freivalds, Thomas Zeugmann, and Grant R. Pogosyan.
On the size
complexity of deterministic frequency automata.
In Adrian-Horia Dediu, Carlos Martín-Vide, and Bianca Truthe, editors,
*Language and Automata Theory and Applications, 7th International
Conference, LATA 2013, Bilbao, Spain, April 2013, Proceedings*, volume
7810 of *Lecture Notes in Computer Science*, pages 287-298. Springer,
2013.

Charles Jordan and Łukasz Kaiser.
Experiments with
reduction finding.
In Matti Järvisalo and Allen Van Gelder, editors, *Theory and
Applications of Satisfiability Testing, 16th International Conference, SAT
2013, Helsinki, Finland, July 2013, Proceedings*, volume 7962 of
*Lecture Notes in Computer Science*, pages 192-207. Springer, 2013.

Charles Jordan and Łukasz Kaiser.
Learning programs as logical queries.
In *ICALP 2013 Satellite Workshop on Learning Theory and Complexity
(LTC)*, 2013.

Charles Jordan and Łukasz Kaiser.
Benchmarks from reduction finding.
In Florian Lonsing and Martina Seidl, editors, *International Workshop on
Quantified Boolean Formulas 2013, Informal Workshop Report*, pages
40-43, 2013.

Shin-ichi Minato.
*Z*-skip-links for
fast traversal of ZDDs representing large-scale sparse datasets.
In Hans L. Bodlaender and Giuseppe F. Italiano, editors, *Algorithms -
ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France,
September 2-4, 2013. Proceedings*, volume 8125 of *Lecture Notes in
Computer Science*, pages 731-742. Springer, 2013.

Laura Tague, Mathias Soeken, Shin-ichi Minato, and Rolf Drechsler.
Debugging of reversible
circuits using πDDs.
In *43rd IEEE International Symposium on Multiple-Valued Logic, ISMVL
2013, Toyama, Japan, May 22-24, 2013*, pages 316-321. IEEE, 2013.

Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto, and Shin-ichi Minato.
Shared-memory
parallel frontier-based search.
In Subir Kumar Ghosh and Takeshi Tokuyama, editors, *WALCOM: Algorithms
and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India,
February 14-16, 2013, Proceedings*, volume 7748 of *Lecture Notes in
Computer Science*, pages 170-181. Springer, 2013.

Atsushi Takizawa, Yasufumi Takechi, Akio Ohta, Naoki Katoh, Takeru Inoue,
Takashi Horiyama, Jun Kawahara, and Shin-ichi Minato.
Enumeration of region partitioning for evacuation planning based on
ZDD.
In Xiang-Sun Zhang, Degang Liu, Ling-Yun Wu, and Yong Wang, editors, *2013
International Symposium on Operations Research and its Applications (ISORA),
Huangshan, China, August 23-25, 2013*, pages 64-71. Institution of
Engineering and Technology, 2013.

### Technical Reports

Shin-ichi Minato.
*Z*-skip-links for fast ZDD traversal in handling large-scale sparse
datasets.
Technical Report TCS-TR-A-13-63, Division of Computer Science, Hokkaido
University, 2013.

Hiroaki Iwashita, Yoshio Nakazawa, Jun Kawahara, Takeaki Uno, and Shin-ichi Minato. Efficient computation of the number of paths in a grid graph with minimal perfect hash functions. Technical Report TCS-TR-A-13-64, Division of Computer Science, Hokkaido University, 2013.

Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato. Graphillion: Software library designed for very large sets of graphs in python. Technical Report TCS-TR-A-13-65, Division of Computer Science, Hokkaido University, 2013.

Shin-ichi Minato.
*Z*-skip-links for fast ZDD traversal in handling large-scale sparse
datasets (revised ed.).
Technical Report TCS-TR-A-13-66, Division of Computer Science, Hokkaido
University, 2013.

Yuma Inoue, Takahisa Toda, and Shin-ichi Minato. Implicit generation of pattern-avoiding permutations based on πDD. Technical Report TCS-TR-A-13-67, Division of Computer Science, Hokkaido University, 2013.

Rūsiņš Freivalds and Thomas Zeugmann. Active learning of classes of recursive functions by ultrametric algorithms. Technical Report TCS-TR-A-13-68, Division of Computer Science, Hokkaido University, 2013.

## 2012

### Journals

Takeru Inoue and Shin-ichi Minato.
On tackling flash
crowds with url shorteners and examining user behavior after great east japan
earthquake.
*IEICE Transactions on Communications*, **E95B** no. 7 pp.
2210-2221, 2012.

Charles Jordan and Thomas Zeugmann.
Testable and
untestable classes of first-order formulae.
*Journal of Computer and System Sciences*, **78** no. 5 pp.
1557-1578, 2012.

Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, and
Yoshikazu Miyanaga.
A dynamically
reconfigurable fpga-based pattern matching hardware for subclasses of regular
expressions.
*IEICE Transactions*, **95-D** no. 7 pp. 1847-1857, 2012.

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller.
Synthesis of semi-classical quantum circuits.
*Journal of Multiple-Valued Logic and Soft Computing*, **18** no. 1
pp. 99-114, 2012.

Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura, and Shin-ichi
Minato.
Counterexamples to the
long-standing conjecture on the complexity of BDD binary operations.
*Information Processing Letters*, **112** no. 16 pp. 636-640,
2012.

Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita,
and Shin-ichi Minato.
Finding all solutions and
instances of numberlink and slitherlink by ZDDs.
*Algorithms*, **5** no. 2 pp. 176-213, 2012.

### Editorial Work

Nader H. Bshouty, Gilles Stoltz, Nicolas Vayatis, and Thomas Zeugmann,
editors.
*Algorithmic
Learning Theory, 23rd International Conference, ALT 2012, Lyon, France,
October 29-31, 2012, Proceedings*, volume 7568 of *Lecture Notes
in Artificial Intelligence*, Berlin, Heidelberg, New York, October 2012.
Springer.

Nader H. Bshouty, Gilles Stoltz, Nicolas Vayatis, and Thomas Zeugmann.
Editors'
introduction.
In Nader H. Bshouty, Gilles Stoltz, Nicolas Vayatis, and Thomas Zeugmann,
editors, *Algorithmic Learning Theory, 23rd International Conference,
ALT 2012, Lyon, France, October 29-31, 2012, Proceedings*, volume 7568
of *Lecture Notes in Artificial Intelligence*, pages 1-11, Berlin,
Heidelberg, New York, 2012. Springer.

### International Conferences

Marco Carmosino, Neil Immerman, and Charles Jordan.
Experimental descriptive complexity.
In *Logic and Program Semantics - Essays Dedicated to Dexter Kozen on the
Occasion of His 60th Birthday*, volume 7230 of *Lecture Notes in
Computer Science*, pages 24-34. Springer, 2012.

Sanjay Jain, Frank Stephan, and Thomas Zeugmann.
On the amount of
nonconstructivity in learning formal languages from positive data.
In Manindra Agrawal, S. Barry Cooper, and Ansheng Li, editors, *Theory and
Applications of Models of Computation, 9th Annual Conference, TAMC 2012,
Beijing, China, May 16-21, 2012, Proceedings*, volume 7287 of *Lecture
Notes in Computer Science*, pages 423-434. Springer, 2012.

Yasuyuki Shirai, Koji Tsuruma, Yuko Sakurai, Satoshi Oyama, and Shin-ichi
Minato.
Incremental set
recommendation based on class differences.
In Pang-Ning Tan, Sanjay Chawla, Chin Kuan Ho, and James Bailey, editors,
*Advances in Knowledge Discovery and Data Mining, 16th Pacific-Asia
Conference, PAKDD 2012, Kuala Lumpur, Malaysia, May 29-June 1, 2012,
Proceedings, Part I*, volume 7301 of *Lecture Notes in Artificial
Intelligence*, pages 183-194. Springer, 2012.

### Technical Reports

Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi. Loss minimization of power distribution networks with guaranteed error bound. Technical Report TCS-TR-A-12-59, Division of Computer Science, Hokkaido University, 2012.

Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato. ZDD-based computation of the number of paths in a graph. Technical Report TCS-TR-A-12-60, Division of Computer Science, Hokkaido University, 2012.

Sanjay Jain, Frank Stephan, and Thomas Zeugmann. On the amount of nonconstructivity in learning formal languages from text. Technical Report TCS-TR-A-12-55, Division of Computer Science, Hokkaido University, 2012.

Norihiro Yamada and Shin-ichi Minato. A πDD-based method for generating conjugacy classes of permutation groups. Technical Report TCS-TR-A-12-56, Division of Computer Science, Hokkaido University, 2012.

Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto, and Shin-ichi Minato. Shared-memory parallel algorithms for frontier-based search. Technical Report TCS-TR-A-12-57, Division of Computer Science, Hokkaido University, 2012.

## 2011

### Journals

Frank J. Balbach and Thomas Zeugmann.
Teaching randomized
learners with feedback.
*Information and Computation*, **209** no. 3 pp. 296-319, 2011.
(LATA 2009), Special Issue.

Shin-ichi Minato.
Overview of ERATO
Minato Project: The art of discrete structure manipulation between
science and engineering.
*New Generation Computing*, **29** no. 2 pp. 223-238, 2011.
Invited Paper.

### Book Chapters

Shin-ichi Minato and Nicolas Spyratos.
BDD-based
combinatorial keyword query processing under a taxonomy model.
In Gunther Kreuzberger, Aran Lunzer, and Roland Kaschek, editors,
*Interdisciplinary Advances in Adaptive and Intelligent Assistant Systems:
Concepts, Techniques, Applications, and Use*, pages 26-39. IGI Global,
Hershey, Pennsylvania, 2011.

### Editorial Work

Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann,
editors.
*Algorithmic
Learning Theory, 22nd International Conference, ALT 2011, Espoo, Finland,
October 5-7, 2011, Proceedings*, volume 6925 of *Lecture Notes in
Artificial Intelligence*, Berlin, Heidelberg, New York, October 2011.
Springer.

Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann.
Editors'
introduction.
In Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann,
editors, *Algorithmic Learning Theory, 22nd International Conference,
ALT 2011, Espoo, Finland, October 5-7, 2011, Proceedings*, volume 6925
of *Lecture Notes in Artificial Intelligence*, pages 1-13, Berlin,
Heidelberg, New York, 2011. Springer.

### International Conferences

Hiroshi Aoki, Shigeru Yamashita, and Shin-ichi Minato.
An efficient algorithm
for constructing a sequence binary decision diagram representing a set of
reversed sequences.
In Tzung-Pei Hong, Yasuo Kudo, Mineichi Kudo, Tsau-Young Lin, Been-Chian
Chien, Shyue-Liang Wang, Masahiro Inuiguchi, and GuiLong Liu, editors,
*Proceedings, 2011 IEEE International Conference on Granular Computing,
GrC 2011*, pages 54-59. IEEE, 2011.

Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, and Shin-ichi Minato.
Notes on sequence
binary decision diagrams: Relationship to acyclic automata and complexities
of binary set operations.
In Jan Holub and Jan Žďárek, editors, *Proceedings of
the Prague Stringology Conference 2011*, pages 147-161, Czech Technical
University in Prague, Czech Republic, 2011.

Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato.
Implementation of
sequence BDDs in Erlang.
In *Erlang '11, Proceedings of the 10th ACM SIGPLAN Workshop on
Erlang*, pages 90-91, 2011.

Masakazu Ishihata, Taisuke Sato, and Shin-ichi Minato.
Compiling
Bayesian networks for parameter learning based on shared BDDs.
In Dianhui Wang and Mark Reynolds, editors, *AI 2011: Advances in
Artificial Intelligence, 24th Australasian Joint Conference, Perth,
Australia, December 5-8, 2011. Proceedings*, volume 7106 of *Lecture
Notes in Artificial Intelligence*, pages 203-212. Springer, 2011.

Charles Jordan and Thomas Zeugmann.
Untestable
properties in the Kahr-Moore-Wang class.
In Lev D. Beklemishev and Ruy de Queiroz, editors, *Logic, Language,
Information and Computation, 18th International Workshop, WoLLIC 2011,
Philadelphia, PA, USA, May 18-21, 2011, Proceedings*, volume 6642 of
*Lecture Notes in Artificial Intelligence*, pages 176-186. Springer,
2011.

Rūsiņš Freivalds and Thomas Zeugmann.
On the amount of
nonconstructivity in learning recursive functions.
In Mitsunori Ogihara and Jun Tarui, editors, *Theory and Applications of
Models of Computation, 8th Annual Conference, TAMC 2011, Tokyo, Japan, May
23-25, 2011, Proceedings*, volume 6648 of *Lecture Notes in Computer
Science*, pages 332-343. Springer, 2011.

Shin-ichi Minato.
πDD: A new
decision diagram for efficient problem solving in permutation space.
In Karem A. Sakallah and Laurent Simon, editors, *Theory and Applications
of Satisfiability Testing - SAT 2011, 14th International Conference, SAT
2011, Ann Arbor, MI, USA, June 19-22, 2011, Proceedings*, volume 6695 of
*Lecture Notes in Computer Science*, pages 90-104. Springer, 2011.

Yuko Sakurai, Suguru Ueda, Atsushi Iwasaki, Shin-ichi Minato, and Makoto
Yokoo.
A compact
representation scheme of coalitional games based on multi-terminal
zero-suppressed binary decision diagrams.
In David Kinny, Jane Yung jen Hsu, Guido Governatori, and Aditya K. Ghose,
editors, *Agents in Principle, Agents in Practice, 14th International
Conference, PRIMA 2011, Wollongong, Australia, November 16-18, 2011.
Proceedings*, volume 7074 of *Lecture Notes in Artificial
Intelligence*, pages 4-18. Springer, 2011.

Frank Stephan, Ryo Yoshinaka, and Thomas Zeugmann.
On the
parameterised complexity of learning patterns.
In Erol Gelenbe, Ricardo Lent, and Georgia Sakellari, editors, *Computer
and Information Sciences II, 26th International Symposium on Computer and
Information Sciences*, pages 277-281. Springer, 2011.

### Technical Reports

Shin-ichi Minato. πDD: A new decision diagram for manipulating sets of permutations. Technical Report TCS-TR-A-11-50, Division of Computer Science, Hokkaido University, 2011.

Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato. Counter examples to the conjecture on the complexity of BDD binary operations. Technical Report TCS-TR-A-11-52, Division of Computer Science, Hokkaido University, 2011.

Shuhei Denzumi, Ryo Yoshinaka, Shin-ichi Minato, and Hiroki Arimura. Efficient algorithms on sequence binary decision diagrams for manipulating sets of strings. Technical Report TCS-TR-A-11-53, Division of Computer Science, Hokkaido University, 2011.

Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka, and Shin-ichi Minato. Counting primitive sorting networks by πDDs. Technical Report TCS-TR-A-11-54, Division of Computer Science, Hokkaido University, 2011.

## 2010

### Book Chapters

Kimihito Ito, Thomas Zeugmann, and Yu Zhu.
Clustering the
normalized compression distance for influenza virus data.
In Tapio Elomaa, Heikki Mannila, and Pekka Orponen, editors, *Algorithms
and Applications, Essays Dedicated to Esko Ukkonen on the Occasion of His
60th Birthday*, volume 6060 of *Lecture Notes in Computer
Science*, pages 130-146. Springer, Heidelberg, 2010.

Thomas Zeugmann.
PAC
learning.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning*, pages 745-753. Springer, New York, 2010.
Invited contribution.

Thomas Zeugmann.
Stochastic finite
learning.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning*, pages 925-928. Springer, New York, 2010.
Invited contribution.

Thomas Zeugmann.
VC
dimension.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning*, pages 1021-1024. Springer, New York, 2010.
Invited contribution.

Thomas Zeugmann.
Epsilon nets.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning*, pages 326-327. Springer, New York, 2010.
Invited contribution.

Thomas Zeugmann.
Epsilon
covers.
In Claude Sammut and Geoffrey I. Webb, editors, *Encyclopedia of Machine
Learning*, page 326. Springer, New York, 2010.
Invited contribution.

### Editorial Work

László Győrfi, Győrgy Turán, and Thomas Zeugmann.
Guest editors' foreword.
*Theoret. Comput. Sci.*, **411** no. 29-30 pp. 2629-2631, 2010.
Algorithmic Learning Theory (ALT 2008), Special Issue.

Marcus Hutter, Frank Stephan, Vladimir Vovk, and Thomas Zeugmann, editors.
*Algorithmic
Learning Theory, 21st International Conference, ALT 2010, Canberra,
Australia, October 6-8, 2010, Proceedings*, volume 6331 of
*Lecture Notes in Artificial Intelligence*, Berlin, Heidelberg, New
York, October 2010. Springer.

Marcus Hutter, Frank Stephan, Vladimir Vovk, and Thomas Zeugmann.
Editors'
introduction.
In Marcus Hutter, Frank Stephan, Vladimir Vovk, and Thomas Zeugmann, editors,
*Algorithmic Learning Theory, 21th International Conference, ALT 2010,
Canberra, Australia, October 6-8, 2010, Proceedings*, volume 6331 of
*Lecture Notes in Artificial Intelligence*, pages 1-10, Berlin,
Heidelberg, New York, 2010. Springer.

### International Conferences

Masakazu Ishihata, Yoshitaka Kameya, Taisuke Sato, and Shin-ichi Minato.
An EM algorithm on BDDs with order encoding for logic-based
probabilistic models.
In Masashi Sugiyama and Qiang Yang, editors, *2nd Asian Conference on
Machine Learning (ACML2010), Tokyo, Japan, Nov. 8-10, 2010*, volume 13
of *JMLR Workshop and Conference Proceedings*, pages 161-176. JMLR:
Workshop and Conference Proceedings, 2010.

Kimihito Ito, Thomas Zeugmann, and Yu Zhu.
Recent experiences
in parameter-free data mining.
In Erol Gelenbe, Ricardo Lent, Georgia Sakellari, Ahmet Sacan, Hakki Toroslu,
and Adnan Yazici, editors, *Computer and Information Science, Proceedings
of the 25th International Symposium on Computer and Information
Sciences*, volume 62 of *Lecture Notes in Electrical Engineering*,
pages 365-371, Heidelberg, 2010. Springer.
Invited Paper.

Charles Jordan and Thomas Zeugmann.
Untestable
properties expressible with four first-order quantifiers.
In Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide,
editors, *Language and Automata Theory and Applications, 4th International
Conference, LATA 2010, Trier, Germany, May 2010, Proceedings*, volume
6031 of *Lecture Notes in Computer Science*, pages 333-343. Springer,
2010.

Charles Jordan and Thomas Zeugmann.
A note on the
testability of Ramsey's class.
In Jan Kratochvíl, Angsheng Li, Jiří Fiala, and Petr
Kolman, editors, *Theory and Applications of Models of Computation, 7th
Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010,
Proceedings*, volume 6108 of *Lecture Notes in Computer Science*,
pages 296-307. Springer, 2010.

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura.
Fast bit-parallel
matching for network and regular expressions.
In Edgar Chávez and Stefano Lonardi, editors, *String Processing and
Information Retrieval - 17th International Symposium, SPIRE 2010, Los Cabos,
Mexico, October 11-13, 2010. Proceedings*, volume 6393 of *Lecture
Notes in Computer Science*, pages 372-384. Springer, 2010.

Shin-ichi Minato.
Discrete structure
manipulation for discovery science problems.
In Erol Gelenbe, Ricardo Lent, Georgia Sakellari, Ahmet Sacan, Hakki Toroslu,
and Adnan Yazici, editors, *Computer and Information Science, Proceedings
of the 25th International Symposium on Computer and Information
Sciences*, volume 62 of *Lecture Notes in Electrical Engineering*,
pages 359-364, Heidelberg, 2010. Springer.
Invited Paper.

Shin-ichi Minato and Takeaki Uno.
Frequentness-transition queries for distinctive pattern mining from
time-segmented databases.
In Srinivasan Parthasarathy, Bing Liu, and Chandrika Kamath, editors,
*Proceedings of the Tenth SIAM International Conference on Data
Mining*, pages 339-349. SIAM, 2010.

Ryo Yoshinaka, Yuichi Kaji, and Hiroyuki Seki.
Chomsky-Schützenberger-type characterization of multiple context-free
languages.
In Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide,
editors, *Language and Automata Theory and Applications, 4th International
Conference, LATA 2010, Trier, Germany, May 2010, Proceedings*, volume
6031 of *Lecture Notes in Computer Science*, pages 596-607. Springer,
2010.

### Technical Reports

Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato. Substring indices based on sequence BDDs. Technical Report TCS-TR-A-10-42, Division of Computer Science, Hokkaido University, 2010.

Rūsiņš Freivalds and Thomas Zeugmann. On the amount of nonconstructivity in the inductive inference of recursive functions. Technical Report TCS-TR-A-10-49, Division of Computer Science, Hokkaido University, 2010.

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura. An efficient matching algorithm for acyclic regular expressions with bounded depth. Technical Report TCS-TR-A-10-40, Division of Computer Science, Hokkaido University, 2010.

Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, and Yoshikazu Miyanaga. Dynamic reconfigurable bit-parallel architecture for large-scale regular expression matching. Technical Report TCS-TR-A-10-45, Division of Computer Science, Hokkaido University, 2010.

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimuta. Fast bit-parallel matching for network and regular expressions. Technical Report TCS-TR-A-10-47, Division of Computer Science, Hokkaido University, 2010.

Shin-ichi Minato. Recent and future work on decision diagrams and discrete structure manipulation. Technical Report TCS-TR-B-10-7, Division of Computer Science, Hokkaido University, 2010.

## 2009

### Books

Thomas Zeugmann, Shin-ichi Minato, and Yoshiaki Okubo.
*Theory
of Computation*.
Corona Publishing Co., LTD, 2009.

### Journals

Ryo Yoshinaka.
Learning efficiency of
very simple grammars from positive data.
*Theoret. Comput. Sci.*, **410** no. 19 pp. 1807-1825, 2009.
Special issue for ALT 2007.

Ryo Yoshinaka.
An elementary proof of
a generalization of double Greibach normal form.
*Information Processing Letters*, **109** no. 10 pp. 490-492,
2009.

### Editorial Work

Sanjay Chawla, Takashi Washio, Shin-ichi Minato, Shusaku Tsumoto, Takashi
Onoda, Seiji Yamada, and Akihiro Inokuchi, editors.
*New Frontiers in
Applied Data Mining, PAKDD 2008 International Workshops, Osaka, Japan, May
20-23, 2008. Revised Selected Papers*, volume 5433 of *Lecture
Notes in Artificial Intelligence*, Berlin/Heidelberg, February 2009.
Springer.

Ricard Gavaldà, Gábor Lugosi, Thomas Zeugmann, and Sandra
Zilles, editors.
*Algorithmic
Learning Theory, 20th International Conference, ALT 2009, Porto, Portugal,
October 2009, Proceedings*, volume 5809 of *Lecture Notes in
Artificial Intelligence*, Berlin/Heidelberg, October 2009. Springer.

Osamu Watanabe and Thomas Zeugmann, editors.
*Stochastic
Algorithms: Foundations and Applications, 5th International Symposium, SAGA
2009, Sapporo, Japan, October 2009, Proceedings*, volume 5792 of
*Lecture Notes in Computer Science*, Berlin/Heidelberg, October 2009.
Springer.

### International Conferences

Frank J. Balbach and Thomas Zeugmann.
Recent developments
in algorithmic teaching.
In Adrian Horia Dediu, Armand Mihai Ionescu, and Carlos Martín-Vide,
editors, *Language and Automata Theory and Applications, Third
International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009,
Proceedings*, volume 5457 of *Lecture Notes in Computer Science*,
pages 1-18. Springer, 2009.
Invited Paper.

Kimihito Ito, Thomas Zeugmann, and Yu Zhu.
Clustering the normalized compression distance for virus data.
In *Proceedings of the Sixth Workshop on Learning with Logics and Logics
for Learning (LLLL 2009), Kyodai Kaikan, Kyoto, Japan, June 6-7, 2009*,
pages 56-67, 2009.

Charles Jordan and Thomas Zeugmann.
Relational
properties expressible with one universal quantifier are testable.
In Osamu Watanabe and Thomas Zeugmann, editors, *Stochastic Algorithms:
Foundations and Applications, 5th International Symposium, SAGA 2009,
Sapporo, Japan, October 2009, Proceedings*, volume 5792 of *Lecture
Notes in Computer Science*, pages 141-155. Springer, 2009.

Ryo Yoshinaka.
Learning mildly
context-sensitive languages with multidimensional substitutability from
positive data.
In Ricard Gavaldà, Gábor Lugosi, Thomas Zeugmann, and Sandra
Zilles, editors, *Algorithmic Learning Theory, 20th International
Conference, ALT 2009, Porto, Portugal, October 2009, Proceedings*,
volume 5809 of *Lecture Notes in Artificial Intelligence*, pages
278-292. Springer, 2009.

### Technical Reports

Charles Harold Jordan. Master's thesis: The classification problem in relational property testing. Technical Report TCS-TR-B-09-6, Division of Computer Science, Hokkaido University, 2009.

Charles Jordan and Thomas Zeugmann. Contributions to the classification for testability: Four universal and one existential quantifier. Technical Report TCS-TR-A-09-39, Division of Computer Science, Hokkaido University, 2009.

Shin-ichi Minato and Takeaki Uno. Distinctive frequent itemset mining from time segmented databases using ZDD-based symbolic processing. Technical Report TCS-TR-A-09-37, Division of Computer Science, Hokkaido University, 2009.

## 2008

### Journals

Yohji Akama and Thomas Zeugmann.
Consistent and coherent
learning with δ-delay.
*Information and Computation*, **206** no. 11 pp. 1362-1374, 2008.

Haruya Iwasaki, Shin-ichi Minato, and Thomas Zeugmann.
A method of ZBDD variable ordering for frequent pattern mining.
*The IEICE Transactions on Information and Systems (Japanese
Edition)*, **J91-D** no. 3 pp. 608-618, 2008.
in Japanese.

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller.
DDMF: An
efficient decision diagram structure for design verification of quantum
circuits under a practical restriction.
*IEICE Transactions on Fundamentals of Electronics, Communications and
Computer Science*, **E91-A** no. 12 pp. 3793-3802, 2008.

Thomas Zeugmann and Sandra Zilles.
Learning recursive
functions: A survey.
*Theoret. Comput. Sci.*, **397** no. 1-3 pp. 4-56, 2008.
Special issue Forty Years of Inductive Inference: Dedicated to the 60th
Birthday of Rolf Wiehagen.

Steffen Lange, Thomas Zeugmann, and Sandra Zilles.
Learning indexed
families of recursive languages from positive data: A survey.
*Theoret. Comput. Sci.*, **397** no. 1-3 pp. 194-232, 2008.
Special issue Forty Years of Inductive Inference: Dedicated to the 60th
Birthday of Rolf Wiehagen.

### Editorial Work

John Case, Takeshi Shinohara, Thomas Zeugmann, and Sandra Zilles.
Foreword.
*Theoret. Comput. Sci.*, **397** no. 1-3 pp. 1-3, 2008.
Special issue Forty Years of Inductive Inference: Dedicated to the 60th
Birthday of Rolf Wiehagen.

Yoav Freund, László Györfi, György Turán, and Thomas
Zeugmann, editors.
*Algorithmic
Learning Theory, 19th International Conference, ALT 2008, Budapest,
Hungary, October 13-16, 2008, Proceedings*, volume 5254 of
*Lecture Notes in Artificial Intelligence*, Berlin/Heidelberg, October
2008. Springer.

### International Conferences

Skip Jordan and Thomas Zeugmann.
Indistinguishability
and first-order logic.
In Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, editors,
*Theory and Applications of Models of Computation, 5th International
Conference, TAMC 2008, Xi'an, China, April 2008, Proceedings*, volume
4978 of *Lecture Notes in Computer Science*, pages 94-104. Springer,
2008.

Shin-ichi Minato, Takeaki Uno, and Hiroki Arimura.
LCM over ZBDDs:
Fast generation of very large-scale frequent itemsets using a compact
graph-based representation.
In Takashi Washio, Einoshin Suzuki, Kai Ming Ting, and Akihiro Inokuchi,
editors, *Advances in Knowledge Discovery and Data Mining, 12th
Pacific-Asia Conference, PAKDD 2008, Osaka, Japan, May 20-23, 2008,
Proceedings*, volume 5012 of *Lecture Notes in Artificial
Intelligence*, pages 234-246. Springer, 2008.

S. Minato.
A fast algorithm for
cofactor implication checking and its application for knowledge
discovery.
In *8th IEEE International Conference on Computer and Information
Technology (CIT 2008)*, pages 53-58. IEEE Computer Society, 2008.

S. Yamashita, S. Minato, and D. M. Miller.
An efficient
verification of quantum circuits under a practical restriction.
In *8th IEEE International Conference on Computer and Information
Technology (CIT 2008)*, pages 873-879. IEEE Computer Society, 2008.

Ryo Yoshinaka.
An efficient
algorithm for the inclusion problem of a subclass of DPDAs.
In Carlos Martín-Vide, Friedrich Otto, and Henning Fernau, editors,
*Language and Automata Theory and Applications, Second International
Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised
Papers*, volume 5196 of *Lecture Notes in Artificial
Intelligence*, pages 487-498. Springer, 2008.

Ryo Yoshinaka.
Identification in
the limit of *k,l*-substitutable context-free languages.
In Alexander Clark, François Coste, and Laurent Miclet, editors,
*Grammatical Inference: Algorithms and Applications, 9th International
Colloquium, ICGI 2008 Saint-Malo, France, September 22-24, 2008
Proceedings*, volume 5278 of *Lecture Notes in Artificial
Intelligence*, pages 266-279. Springer, 2008.

### Local Conferences and Workshops

Takao Saitoh, Shin-ichi Minato, and Thomas Zeugmann (齋藤高央,
湊真一, ツォイクマントーマス).
コルモゴロフ複雑性に基づく画像圧縮と分類に関する実験と考察 (Image compression and clustering based on Kolmogorov
complexity).
In *FIT-2008 IEICE/IPSJ 第7回情報科学技術フォーラム,
F-020*, pages 355-357, 2008.

### Technical Reports

Masakazu Ishihata, Yoshitaka Kameya, Taisuke Sato, and Shin-ichi Minato. Propositionalizing the EM algorithm by BDDs. Technical Report TR08-0004, Department of Computer Science, Tokyo Institute of Technology, jun 2008.

Haruya Iwasaki. Master thesis: Studies on variable ordering of zero-suppressed binary decision diagrams for database analysis. Technical Report TCS-TR-B-08-3, Department of Computer Science, Tokyo Institute of Technology, 2008. in Japanese.

Shane Legg, Jan Poland, and Thomas Zeugmann. On the limits of learning with computational models. Technical Report TCS-TR-A-08-34, Division of Computer Science, Hokkaido University, jan 2008.

Thomas Zeugmann. Course notes on complexity and cryptography. Technical Report TCS-TR-B-08-4, Division of Computer Science, Hokkaido University, 2008.

## 2007

### Journals

Shin-ichi Minato and Hiroki Arimura.
Frequent closed item set mining based on zero-suppressed BDDs.
*Transactions of the Japanese Society for Artificial Intelligence*,
**22** no. 2 pp. 165-172, 2007.
Special Issue: Data Mining and Statistical Science.

Shin-ichi Minato and Kimihito Ito.
Symmetric item set mining method using zero-suppressed BDDs and
application to biological data.
*Transactions of the Japanese Society for Artificial Intelligence*,
**22** no. 2 pp. 156-164, 2007.
Special Issue: Data Mining and Statistical Science.

### Editorial Work

Shai Ben-David, John Case, and Thomas Zeugmann.
Foreword.
*Theoret. Comput. Sci.*, **382** no. 3 pp. 167-169, 2007.
Special issue for ALT 2004.

### International Conferences

Yohji Akama and Thomas Zeugmann.
Consistency
conditions for inductive inference of recursive functions.
In Takashi Washio, Ken Satoh, Hideaki Takeda, and Akihiro Inokuchi, editors,
*New Frontiers in Artificial Intelligence, JSAI 2006 Conference and
Workshops, Tokyo, Japan, June 2006, Revised Selected Papers*, volume 4384
of *Lecture Notes in Artificial Intelligence*, pages 251-264, Berlin,
2007. Springer.

Philippe de Groote, Sarah Maarek, and Ryo Yoshinaka.
On two extensions
of abstract categorial grammars.
In *Logic for Programming, Artificial Intelligence, and Reasoning, 14th
International Conference, LPAR 2007. Yerevan, Armenia, October 2007.
Proceedings*, volume 4790 of *Lecture Notes in Artificial
Intelligence*, pages 273-287. Springer, 2007.

Ryutaro Kurai, Shin-ichi Minato, and Thomas Zeugmann.
N-gram analysis
based on zero-suppressed BDDs.
In Takashi Washio, Ken Satoh, Hideaki Takeda, and Akihiro Inokuchi, editors,
*New Frontiers in Artificial Intelligence, JSAI 2006 Conference and
Workshops, Tokyo, Japan, June 2006, Revised Selected Papers*, volume 4384
of *Lecture Notes in Artificial Intelligence*, pages 289-300, Berlin,
2007. Springer.

Haruya Iwasaki, Shin-ichi Minato, and Thomas Zeugmann.
A method of variable
ordering for zero-suppressed binary decision diagrams in data mining
applications.
In *Proc. of The Third IEEE International Workshop on Databases for
Next-Generation Researchers, SWOD 2007*, pages 85-90. IEEE, 2007.

Ryutaro Kurai, Shin-ichi Minato, and Thomas Zeugmann.
Unordered N-gram representation based on zero-suppressed BDDs for
text mining and classification.
In Akihiro Yamamoto and Kouichi Hirata, editors, *Proceedings of the 5th
Workshop on Learning with Logics and Logics for Learning (LLLL 2007), The
World Convention Center Summit, Miyazaki, Japan, June 18-19, 2007*, pages
32-38. JSAI, 2007.

Shin-ichi Minato.
A theoretical study
on variable ordering of zero-suppressed BDDs for representing frequent
itemsets.
In *Discovery Science, 10th International Conference, DS 2007 Sendai,
Japan, October 1-4, 2007, Proceedings*, volume 4755 of *Lecture Notes
in Artificial Intelligence*, pages 139-150, Berlin, 2007. Springer.

Shin-ichi Minato, Ken Satoh, and Taisuke Sato.
Compiling
bayesian networks by symbolic probability calculation based on
zero-suppressed bdds.
In *Proceedings of 20th International Joint Conference of Artificial
Intelligence (IJCAI-2007)*, pages 2550-2555, 2007.

Ryo Yoshinaka.
Learning efficiency
of very simple grammars from positive data.
In Marcus Hutter, Rocco A. Servedio, and Eiji Takimoto, editors,
*Algorithmic Learning Theory, 18th International Conference, ALT 2007,
Sendai, Japan, October 2007, Proceedings*, volume 4754 of *Lecture
Notes in Artificial Intelligence*, pages 227-241, Berlin, oct 2007.
Springer.

### Local Conferences and Workshops

### Technical Reports

Yohji Akama and Thomas Zeugmann. Consistent and coherent learning with δ-delay. Technical Report TCS-TR-A-07-29, Division of Computer Science, Hokkaido University, 2007.

Steffen Lange, Thomas Zeugmann, and Sandra Zilles. Learning indexed families of recursive languages from positive data. Technical Report TCS-TR-A-07-31, Division of Computer Science, Hokkaido University, 2007.

Shin-ichi Minato. A theoretical study on variable ordering of zbdds for representing frequent itemsets. Technical Report TCS-TR-A-07-27, Division of Computer Science, Hokkaido University, 2007.

Shin-ichi Minato and Nicolas Spyratos. Keyword query processing using binary decision diagrams under a taxonomy model. Technical Report TCS-TR-A-07-28, Division of Computer Science, Hokkaido University, 2007.

Shin-ichi Minato, Takeaki Uno, and Hiroki Arimura. Fast generation of very large-scale frequent itemsets using a compact graph-based representation. Technical Report TCS-TR-A-07-30, Division of Computer Science, Hokkaido University, 2007.

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller. An efficient decision diagram structure for design verification of quantum circuits under a practical restriction. Technical Report TCS-TR-A-07-33, Division of Computer Science, Hokkaido University, dec 2007.

Thomas Zeugmann. Course notes on theory of computation. Technical Report TCS-TR-B-07-2, Division of Computer Science, Hokkaido University, 2007.

Thomas Zeugmann and Sandra Zilles. Learning recursive functions. Technical Report TCS-TR-A-07-32, Division of Computer Science, Hokkaido University, nov 2007.

## 2006

### Journals

Jan Poland and Marcus Hutter.
MDL convergence
speed for Bernoulli sequences.
*Statistics and Computing*, **16** no. 2 pp. 161-175, 2006.

Thomas Zeugmann.
From learning in the
limit to stochastic finite learning.
*Theoret. Comput. Sci.*, **364** no. 1 pp. 77-97, 2006.
Special issue for ALT 2003.

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, and Thomas
Zeugmann.
Learning a subclass of
regular patterns in polynomial time.
*Theoret. Comput. Sci.*, **364** no. 1 pp. 115-131, 2006.
Special issue for ALT 2003.

### Editorial Work

Nicolò Cesa-Bianchi, Rüdiger Reischuk, and Thomas Zeugmann.
Foreword.
*Theoret. Comput. Sci.*, **350** no. 1 pp. 1-2, 2006.
Special issue for ALT 2002.

### International Conferences

Frank J. Balbach and Thomas Zeugmann.
Teaching randomized
learners.
In Gabor Lugosi and Hans Ulrich Simon, editors, *Learning Theory: 19th
Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June
2006, Proceedings*, volume 4005 of *Lecture Notes in Artificial
Intelligence*, pages 229-243, Berlin, 2006. Springer.

Frank J. Balbach and Thomas Zeugmann.
Teaching memoryless
randomized learners without feedback.
In José L. Balcázar, Philip M. Long, and Frank Stephan, editors,
*Algorithmic Learning Theory, 17th International Conference, ALT 2006,
Barcelona, Spain, October 2006, Proceedings*, volume 4264 of *Lecture
Notes in Artificial Intelligence*, pages 93-108. Springer, October 2006.

Björn Hoffmeister and Thomas Zeugmann.
Text mining using markov
chains of variable length.
In Klaus P. Jantke, Aran Lunzer, Nicolas Spyratos, and Yuzuru Tanaka,
editors, *Federation over the Web: International Workshop, Dagstuhl
Castle, Germany, May 1-6, 2005. Revised Selected Papers*, volume 3847 of
*Lecture Notes in Artificial Intelligence*, pages 1-24, Berlin, 2006.
Springer.

Jan Poland.
The missing consistency
theorem for Bayesian learning: Stochastic model selection.
In José L. Balcázar, Philip M. Long, and Frank Stephan, editors,
*Algorithmic Learning Theory, 17th International Conference, ALT 2006,
Barcelona, Spain, October 2006, Proceedings*, volume 4264 of *Lecture
Notes in Artificial Intelligence*, pages 259-273. Springer, October 2006.

Shin-ichi Minato.
Symmetric item set mining
based on zero-suppressed BDDs.
In Ljupčo Todorovski, Nada Lavrač, and Klaus P. Jantke, editors,
*Discovery Science, 9th International Conference, DS 2006, Barcelona,
Spain, October 2006, Proceedings*, volume 4265 of *Lecture Notes in
Artificial Intelligence*, pages 321-326. Springer, October 2006.

Jan Poland and Thomas Zeugmann.
Clustering pairwise
distances with missing data: Maximum cuts versus normalized cuts.
In Ljupčo Todorovski, Nada Lavrač, and Klaus P. Jantke, editors,
*Discovery Science, 9th International Conference, DS 2006, Barcelona,
Spain, October 2006, Proceedings*, volume 4265 of *Lecture Notes in
Artificial Intelligence*, pages 197-208. Springer, October 2006.

Takeshi Shibata, Ryo Yoshinaka, and Takashi Chikayama.
Probabilistic generalization of
simple grammars and its application to reinforcement learning.
In José L. Balcázar, Philip M. Long, and Frank Stephan, editors,
*Algorithmic Learning Theory, 17th International Conference, ALT 2006,
Barcelona, Spain, October 2006, Proceedings*, volume 4264 of *Lecture
Notes in Artificial Intelligence*, pages 348-362. Springer, October
2006.

Ryo Yoshinaka.
Linearization of affine abstract categorial grammars.
In Shuly Wintner, editor, *Proceedings of FG 2006: The 11th Conference on
Formal Grammar, Malaga, Spain, July 29-30, 2006*, pages 185-199,
Stanford, CA, USA, February 2007. CSLI Publications.

Ryo Yoshinaka.
Polynomial-time identification
of an extension of very simple grammars from positive data.
In *Grammatical Inference: Algorithms and Applications, 8th International
Colloquium, ICGI 2006, Tokyo, Japan, September 20-22, 2006.
Proceedings*, volume 4201 of *Lecture Notes in Artificial
Intelligence*, pages 45-58. Springer, September 2006.

Thomas Zeugmann.
Inductive inference and
language learning.
In Jin-Yi Cai, S. Barry Cooper, and Angsheng Li, editors, *Theory and
Applications of Models of Computation, Third International Conference, TAMC
2006, Beijing, China, May 2006, Proceedings*, volume 3959 of *Lecture
Notes in Computer Science*, pages 464-473. Springer, may 2006.
Invited Paper.

### Local Conferences and Workshops

岩崎 玄弥, 湊 真一, and ツォイクマン トーマス.
データベース解析のためのゼロサプレス型二分決定グラフの簡単化に関する考察.
In *人工知能学会 第63回 人工知能基本問題研究会*,
SIG-FPAI-A601, pages 65-70, 2006.

Jan Poland and Thomas Zeugmann.
Clustering based on graph cuts.
In *人工知能学会 第63回 人工知能基本問題研究会*,
SIG-FPAI-A601, pages 77-82, 2006.

Jan Poland and Thomas Zeugmann.
Clustering the google distance with eigenvectors and semidefinite
programming.
In *Knowledge Media Technologies, First International Core-to-Core
Workshop*, volume 21 of *Diskussionsbeiträge, Institut für
Medien und Kommunikationswissenschaft*, pages 61-69. Technische
Universität Ilmenau, 2006.

### Technical Reports

Frank J. Balbach and Thomas Zeugmann. On the teachability of randomized learners. Technical Report TCS-TR-A-06-13, Division of Computer Science, Hokkaido University, April 2006.

Ryutaro Kurai, Shin-ichi Minato, and Thomas Zeugmann. N-gram analysis based on zero-suppressed BDDs. Technical Report TCS-TR-A-06-16, Division of Computer Science, Hokkaido University, 2006.

Shin-ichi Minato. Symmetric item set mining using zero-suppressed BDDs. Technical Report TCS-TR-A-06-14, Division of Computer Science, Hokkaido University, 2006.

Shin-ichi Minato. Generating frequent closed item sets based on zero-suppressed BDDs. Technical Report TCS-TR-A-06-17, Division of Computer Science, Hokkaido University, 2006.

Shin-ichi Minato and Kimihito Ito. Symmetric item set mining method using ZBDDs and application to biological data. Technical Report TCS-TR-A-06-22, Division of Computer Science, Hokkaido University, 2006.

Shin-ichi Minato, Ken Satoh, and Taisuke Sato. Compiling bayesian networks by symbolic probability calculation using zero-suppressed BDDs. Technical Report TCS-TR-A-06-18, Division of Computer Science, Hokkaido University, 2006.

Shin-ichi Minato, Hirokazu Takahashi, Takeru Inoue, Hiroshi Tohjo, and Kan Toyoshima. A framework of programmable multicast applications using flexcast and java applet. Technical Report TCS-TR-A-06-10, Division of Computer Science, Hokkaido University, 2006.

Shin-ichi Minato and Hiroki Arimura. ZBDD-growth: An efficient method for frequent pattern mining and knowledge indexing. Technical Report TCS-TR-A-06-12, Division of Computer Science, Hokkaido University, 2006.

Jan Poland. Potential functions for stochastic model selection. Technical Report TCS-TR-A-06-11, Division of Computer Science, Hokkaido University, 2006.

## 2005

### Journals

Steffen Lange, Gunter Grieser, and Thomas Zeugmann.
Inductive inference of
approximations for recursive concepts.
*Theoret. Comput. Sci.*, **348** no. 1 pp. 15-40, 2005.
Special issue for ALT 2000.

Jan Poland and Marcus Hutter.
Asymptotics of discrete
MDL for online prediction.
*IEEE Transactions on Information Theory*, **51** no. 11 pp.
3780-3795, 2005.

Marcus Hutter and Jan Poland.
Adaptive online
prediction by following the perturbed leader.
*Journal of Machine Learning Research*, **6** pp. 639-660, 2005.

### International Conferences

Frank J. Balbach and Thomas Zeugmann.
Teaching learners with
restricted mind changes.
In Sanjay Jain, Hans Ulrich Simon, and Etsuji Tomita, editors,
*Algorithmic Learning Theory, 16th International Conference, ALT 2005,
Singapore, October 2005, Proceedings*, volume 3734 of *Lecture Notes
in Artificial Intelligence*, pages 474-489. Springer, October 2005.

Jan Poland.
FPL analysis for adaptive
bandits.
In *Stochastic Algorithms: Foundations and Applications, Third
International Symposium, SAGA 2005, Moscow, Russia, October 20-22, 2005.
Proceedings*, volume 3777 of *Lecture Notes in Computer Science*,
pages 58-69. Springer, 2005.

Jan Poland and Marcus Hutter.
Defensive universal learning
with experts.
In Sanjay Jain, Hans Ulrich Simon, and Etsuji Tomita, editors,
*Algorithmic Learning Theory, 16th International Conference, ALT 2005,
Singapore, October 2005, Proceedings*, volume 3734 of *Lecture Notes
in Artificial Intelligence*, pages 356-370, Berlin, 2005. Springer.
Technical Report Version.

### Local Conferences and Workshops

J. Poland and M. Hutter. Master algorithms for active experts problems based on increasing loss values, 2005. Presented at the Annual Machine Learning Conference of Belgium and the Netherlands (Benelearn).

J. Poland and M. Hutter. Strong asymptotic assertions for discrete MDL in regression and classification, 2005. Presented at the Annual Machine Learning Conference of Belgium and the Netherlands (Benelearn).

I. Fischer and J. Poland. Amplifying the block matrix structure for spectral clustering, 2005. Presented at the Annual Machine Learning Conference of Belgium and the Netherlands (Benelearn).

### Technical Reports

Frank J. Balbach and Thomas Zeugmann. Teaching learners that can only perform restricted mind changes. Technical Report TCS-TR-A-05-5, Division of Computer Science, Hokkaido University, 2005.

Shin-ichi Minato. VSOP (valued-sum-of-products) calculator based on zero-suppressed BDDs. Technical Report TCS-TR-A-05-3, Division of Computer Science, Hokkaido University, 2005.

Shin-ichi Minato. Finding all simple disjoint decompositions in frequent itemset data. Technical Report TCS-TR-A-05-9, Division of Computer Science, Hokkaido University, 2005.

Jan Poland. FPL analysis for adaptive bandits. Technical Report TCS-TR-A-05-7, Division of Computer Science, Hokkaido University, 2005.

Jan Poland and Marcus Hutter. Defensive universal learning with experts. Technical Report TCS-TR-A-05-4, Division of Computer Science, Hokkaido University, 2005.

Thomas Zeugmann. From learning in the limit to stochastic finite learning. Technical Report TCS-TR-A-05-8, Division of Computer Science, Hokkaido University, August 2005.

## 2004

### Journals

Jan Poland.
A coding theorem for
enumerable output machines.
*Information Processing Letters*, **91** no. 4 pp. 157-161, 2004.

### International Conferences

### Technical Reports

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, and Thomas Zeugmann. A polynomial time learner for a subclass of regular patterns. Technical Report Report TR04-038, Electronic Colloquium on Computational Complexity, April 2004.

Shin-ichi Minato and Hiroki Arimura. Combinatorial item set analysis based on zero-suppressed BDDs. Technical Report TCS-TR-A-04-1, Division of Computer Science, Hokkaido University, 2004.

## 2003

### Journals

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann.
On learning of
functions refutably.
*Theoret. Comput. Sci.*, **298** no. 1 pp. 111-143, 2003.

Seiichiro Tani, Takeru Inoue, Shin-ichi Minato, Hirokazu Takahashi, Satoshi
Kotabe, and Toshiaki Miyazaki.
Global
multi-point streaming experiments based on the flexcast protocol.
*NTT Technical Review*, **1** no. 5 pp. 24-30, 2003.

### Editorial Work

Takeshi Shinohara, Carl H. Smith, and Thomas Zeugmann.
Foreword.
*Theoret. Comput. Sci.*, **298** no. 1 pp. 1-4, 2003.

### International Conferences

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, and Thomas
Zeugmann.
Learning a subclass of regular patterns in polynomial time.
In Ricard Gavaldà, Klaus P. Jantke, and Eiji Takimoto, editors,
*Algorithmic Learning Theory, 14th International Conference, ALT 2003,
Sapporo, Japan, October 2003, Proceedings*, volume 2842 of *Lecture
Notes in Artificial Intelligence*, pages 234-246. Springer, 2003.

Thomas Zeugmann.
Can learning in the limit be done efficiently?.
In Ricard Gavaldà, Klaus P. Jantke, and Eiji Takimoto, editors,
*Algorithmic Learning Theory, 14th International Conference, ALT 2003,
Sapporo, Japan, October 2003, Proceedings*, volume 2842 of *Lecture
Notes in Artificial Intelligence*, pages 17-38. Springer, 2003.
Invited Paper.

### Technical Reports

## 2002

### Journals

Shin-ichi Minato.
Streaming BDD
manipulation.
*IEEE Transactions on Computers*, **51** no. 5 pp. 474-485, 2002.

Frank Stephan and Thomas Zeugmann.
Learning classes
of approximations to non-recursive functions.
*Theoret. Comput. Sci.*, **288** no. 2 pp. 309-341, 2002.
Special issue for ALT '99.

### International Conferences

### Technical Reports

## 2001

### Journals

Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and
Thomas Zeugmann.
Learning
one-variable pattern languages very efficiently on average, in parallel, and
by asking queries.
*Theoret. Comput. Sci.*, **261** no. 1 pp. 119-156, 2001.
Special issue for ALT '97.

Shin-ichi Minato.
Zero-suppressed BDDs and
their applications.
*International Journal on Software Tools for Technology Transfer*,
**3** no. 2 pp. 156-170, 2001.

Peter Rossmanith and Thomas Zeugmann.
Stochastic finite
learning of the pattern languages.
*Machine Learning*, **44** no. 1/2 pp. 67-91, 2001.

Rolf Wiehagen and Thomas Zeugmann.
Foreword.
*Theoret. Comput. Sci.*, **268** no. 2 pp. 175-177, 2001.
Special issue for ALT '98.

### International Conferences

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann.
Learning recursive functions refutably.
In Naoki Abe, Roni Khardon, and Thomas Zeugmann, editors, *Algorithmic
Learning Theory, 12th International Conference, ALT 2001, Washington, DC,
USA, November 25-28, 2001, Proceedings*, volume 2225 of *Lecture
Notes in Artificial Intelligence*, pages 283-298. Springer, 2001.

Thomas Zeugmann.
Stochastic finite learning.
In Kathleen Steinhöfel, editor, *Stochastic Algorithms: Foundations
and Applications, International Symposium, SAGA 2001, Berlin, Germany,
December 13-14, 2001, Proceedings*, volume 2264 of *Lecture Notes in
Computer Science*, pages 155-171. Springer, 2001.
Invited Paper.

### Editorial Work

Naoki Abe, Roni Khardon, and Thomas Zeugmann, editors.
*Algorithmic Learning Theory, 12th International Conference, ALT 2001,
Washington, DC, USA, November 25-28, 2001, Proceedings*, volume
2225 of *Lecture Notes in Artificial Intelligence*, Berlin, November
2001. Springer.

Naoki Abe, Roni Khardon, and Thomas Zeugmann.
Editors' introduction.
In *Algorithmic Learning Theory, 12th International Conference, ALT 2001,
Washington, DC, USA, November 25-28, 2001, Proceedings*, volume 2225 of
*Lecture Notes in Artificial Intelligence*, pages 1-7. Springer,
2001.

Rolf Wiehagen and Thomas Zeugmann.
Foreword.
*Theoret. Comput. Sci.*, **268** no. 2 pp. 175-177, 2001.
Special issue for ALT '98.

### Technical Reports

S. Lange, G. Grieser, and T. Zeugmann. Learning approximations of recursive concepts. Technical Report SIIM-TR-A-01-03, Schriftenreihe der Institute für Informatik/Mathematik, Medizinische Universität zu Lübeck, 2001.

S. Jain, E. Kinber, R. Wiehagen, and T. Zeugmann. Refutable inductive inference of recursive functions. Technical Report SIIM-TR-A-01-06, Schriftenreihe der Institute für Informatik/Mathematik, Medizinische Universität zu Lübeck, 2001.

## 2000

### Journals

Sanjay Jain, Efim Kinber, Steffen Lange, Rolf Wiehagen, and Thomas Zeugmann.
Learning languages
and functions by erasing.
*Theoret. Comput. Sci.*, **241** no. 1-2 pp. 143-189, 2000.
Special issue for ALT '96.

Rüdiger Reischuk and Thomas Zeugmann.
An average-case optimal
one-variable pattern language learner.
*J. Comput. Syst. Sci.*, **60** no. 2 pp. 302-335, 2000.
Special Issue for COLT '98.

### International Conferences

Gunter Grieser, Steffen Lange, and Thomas Zeugmann.
Learning recursive
concepts with anomalies.
In Hiroki Arimura, Sanjay Jain, and Arun Sharma, editors, *Algorithmic
Learning Theory, 11th International Conference, ALT 2000, Sydney, Australia,
December 2000, Proceedings*, volume 1968 of *Lecture Notes in
Artificial Intelligence*, pages 101-115. Springer, 2000.

Frank Stephan and Thomas Zeugmann.
Average-case complexity of learning polynomials.
In Nicolò Cesa-Bianchi and Sally Goldman, editors, *Proc. 13th Annu.
Conference on Comput. Learning Theory*, pages 59-68. Morgan Kaufmann,
San Francisco, 2000.

### Technical Reports

## 1999

### Journals

John Case, Sanjay Jain, Steffen Lange, and Thomas Zeugmann.
Incremental concept
learning for bounded data mining.
*Inform. Comput.*, **152** no. 1 pp. 74-110, 1999.

### International Conferences

Rüdiger Reischuk and Thomas Zeugmann.
A complete and tight average-case analysis of learning monomials.
In Christoph Meinel and Sophie Tison, editors, *STACS 99, 16th Annual
Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March
1999, Proceedings*, volume 1563 of *Lecture Notes in Computer
Science*, pages 414-423. Springer, 1999.

Frank Stephan and Thomas Zeugmann.
On the uniform
learnability of approximations to non-recursive functions.
In Osamu Watanabe and Takashi Yokomori, editors, *Algorithmic Learning
Theory, 10th International Conference, ALT '99, Tokyo, Japan, December
1999, Proceedings*, volume 1720 of *Lecture Notes in Artificial
Intelligence*, pages 276-290. Springer, 1999.

### Technical Reports

Frank Stephan and Thomas Zeugmann. Learning classes of approximations to non-recursive functions. Technical Report DOI-TR-166, Department of Informatics, Kyushu University, 1999.

## 1998

### Journals

Thomas Zeugmann.
Lange and Wiehagen's
pattern language learning algorithm: An average-case analysis with respect to
its total learning time.
*Annals of Mathematics and Artificial Intelligence*, **23** pp.
117-145, 1998.
Special issue for AII '94 and ALT '94.

### International Conferences

Rüdiger Reischuk and Thomas Zeugmann.
Learning one-variable
pattern languages in linear average time.
In *Proc. 11th Annu. Conf. on Comput. Learning Theory*, pages
198-208, New York, NY, 1998. ACM Press.

Peter Rossmanith and Thomas Zeugmann.
Learning *k*-variable pattern
languages efficiently stochastically finite on average from positive
data.
In *Grammatical Inference, 4th International Colloquium, ICGI-98, Ames,
Iowa, USA, July 1998, Proceedings*, volume 1433 of *Lecture Notes in
Artificial Intelligence*, pages 13-24. Springer, 1998.

### Editorial Work

Michael M. Richter, Carl H. Smith, Rolf Wiehagen, and Thomas Zeugmann,
editors.
*Algorithmic Learning
Theory, 9th International Conference, ALT '98, Otzenhausen, Germany,
October 1998, Proceedings*, volume 1501 of *Lecture Notes in
Artificial Intelligence*. Springer-Verlag, October 1998.

Michael M. Richter, Carl H. Smith, Rolf Wiehagen, and Thomas Zeugmann.
Editors' introduction.
In *Algorithmic Learning Theory, 9th International Conference, ALT '98,
Otzenhausen, Germany, October 1998, Proceedings*, volume 1501 of
*Lecture Notes in Artificial Intelligence*, pages 1-10. Springer,
1998.

### Technical Reports

Rüdiger Reischuk and Thomas Zeugmann. Analyzing the average-case behavior of conjunctive learning algorithms. Technical Report DOI-TR-153, Department of Informatics, Kyushu University, 1998.

Peter Rossmanith and Thomas Zeugmann.
Learning *k*-variable pattern languages efficiently stochastically finite
on average from positive data.
Technical Report DOI-TR-145, Department of Informatics, Kyushu University,
1998.

Rüdiger Reischuk and Thomas Zeugmann. An average-case optimal one-variable pattern language learner. Technical Report Report TR98-069, Electronic Colloquium on Computational Complexity, 1998.

## 1997

### Journals

D. Rotter, K. Hamaguchi, S. Minato, and S. Yajima.
Manipulation of large-scale polynomials using BMDs.
*IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and
Computer Sciences*, **E80-A** no. 10 pp. 1774-1781, 1997.

Shin-Ichi Minato.
Arithmetic boolean
expression manipulator using BDDs.
*Formal Methods in System Design*, **10** no. 2/3 pp. 221-242,
1997.

Carl H. Smith, Rolf Wiehagen, and Thomas Zeugmann.
Classifying predicates and languages.
*International Journal of Foundations of Computer Science*, **8**
no. 1 pp. 15-41, 1997.

### Editorial Work

T. Zeugmann.
Foreword.
*Theoret. Comput. Sci.*, **185** no. 1 pp. 1-1, 1997.
Special issue for ALT '95.

### International Conferences

Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and
Thomas Zeugmann.
Learning one-variable
pattern languages very efficiently on average, in parallel, and by asking
queries.
In *Algorithmic Learning Theory, 8th International Workshop, ALT '97,
Sendai, Japan, October 1997, Proceedings*, volume 1316 of *Lecture
Notes in Artificial Intelligence*, pages 260-276. Springer, 1997.

### Technical Reports

John Case, Sanjay Jain, Steffen Lange, and Thomas Zeugmann. Incremental concept learning for bounded data mining. Technical Report DOI-TR-136, Department of Informatics, Kyushu University, 1997.

Rüdiger Reischuk and Thomas Zeugmann. Learning one-variable pattern languages in linear average time. Technical Report DOI-TR-140, Department of Informatics, Kyushu University, 1997.

## 1996

### Journals

Steffen Lange and Thomas Zeugmann.
Incremental learning from
positive data.
*J. of Comput. Syst. Sci.*, **53** no. 1 pp. 88-103, 1996.

S. Lange and T. Zeugmann.
Set-driven and
rearrangement-independent learning of recursive languages.
*Math. Syst. Theory*, **29** no. 6 pp. 599-634, 1996.

Steffen Lange, Thomas Zeugmann, and Shyam Kapur.
Monotonic and dual
monotonic language learning.
*Theoret. Comput. Sci.*, **155** no. 2 pp. 365-410, 1996.

S. Minato.
Fast factorization method for implicit cube set representation.
*IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems*, **15** no. 4 pp. 377-384, 1996.

### International Conferences

Rusins Freivalds and Thomas Zeugmann.
Co-learning of
recursive languages from positive data.
In Dines Bjørner, Manfred Broy, and Igor V. Pottosin, editors,
*Perspectives of System Informatics, Second International Andrei Ershov
Memorial Conference, Akademgorodok, Novosibirsk, Russia, June 1996,
Proceedings*, volume 1181 of *Lecture Notes in Computer Science*,
pages 122-133. Springer, 1996.

Steffen Lange, Rolf Wiehagen, and Thomas Zeugmann.
Learning by
erasing.
In Setsuo Arikawa and Arun K. Sharma, editors, *Algorithmic Learning
Theory, 7th International Workshop, ALT '96, Sydney, Australia, October
1996, Proceedings*, volume 1160 of *Lecture Notes in Artificial
Intelligence*, pages 228-241. Springer, 1996.

### Technical Reports

Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann. Efficient learning of one-variable pattern languages from positive examples. Technical Report DOI-TR-128, Department of Informatics, Kyushu University, 1996.

Rolf Wiehagen, Steffen Lange, and Thomas Zeugmann. Learning by erasing. Technical Report RIFIS-TR-CS-122, RIFIS, Kyushu University 33, 1996.

## 1995

### Journals

William I. Gasarch, Efim B. Kinber, Mark G. Pleszkoch, Carl H. Smith, and
Thomas Zeugmann.
Learning via queries, teams, and anomalies.
*Fundamenta Informaticae*, **23** pp. 67-89, 1995.

Steffen Lange and Thomas Zeugmann.
Trading monotonicity demands versus efficiency.
*Bulletin of Informatics and Cybernetics*, **27** no. 1 pp. 53-83,
1995.

Thomas Zeugmann, Steffen Lange, and Shyam Kapur.
Characterizations of
monotonic and dual monotonic language learning.
*Inform. Comput.*, **120** no. 2 pp. 155-173, 1995.

### International Conferences

Steffen Lange and Thomas Zeugmann.
Refined incremental learning.
In Xin Yao, editor, *Proc. 8th Australian Joint Conference on Artificial
Intelligence - AI'95*, pages 147-154. World Scientific Publ. Co., 1995.

Steffen Lange and Thomas Zeugmann.
Trading monotonicity
demands versus mind changes.
In Paul Vitányi, editor, *Computational Learning Theory, Second
European Conference, EuroCOLT '95, Barcelona, Spain, March 1995,
Proceedings*, volume 904 of *Lecture Notes in Artificial
Intelligence*, pages 125-139. Springer, 1995.

### Editorial Work

Klaus P. Jantke, Takeshi Shinohara, and Thomas Zeugmann, editors.
*Algorithmic Learning Theory, 6th International Workshop, ALT '95,
Fukuoka, Japan, October 18-20, 1995, Proceedings*, volume 997 of
*Lecture Notes in Artificial Intelligence*, Berlin, October 1995.
Springer.

Klaus P. Jantke, Takeshi Shinohara, and T. Zeugmann.
Editors' introduction.
In *Algorithmic Learning Theory, 6th International Workshop, ALT '95,
Fukuoka, Japan, October 18-20, 1995, Proceedings*, volume 997 of
*Lecture Notes in Artificial Intelligence*, pages ix-xv. Springer,
1995.

### Book Chapters

Rolf Wiehagen, Carl H. Smith, and Thomas Zeugmann.
Classifying recursive
predicates and languages.
In *Algorithmic Learning for Knowledge-Based Systems*, volume 961 of
*Lecture Notes in Artificial Intelligence*, pages 174-189. Springer,
1995.

Rolf Wiehagen and Thomas Zeugmann.
Learning and
consistency.
In *Algorithmic Learning for Knowledge-Based Systems*, volume 961 of
*Lecture Notes in Artificial Intelligence*, pages 1-24. Springer,
1995.

Thomas Zeugmann and Steffen Lange.
A guided tour across
the boundaries of learning recursive languages.
In *Algorithmic Learning for Knowledge-Based Systems*, volume 961 of
*Lecture Notes in Artificial Intelligence*, pages 190-258. Springer,
1995.

### Technical Reports

Rusins Freivalds and Thomas Zeugmann. Co-learning of recursive languages from positive data. Technical Report RIFIS-TR-CS-110, RIFIS, Kyushu University 33, 1995.

Steffen Lange and Thomas Zeugmann. Modeling incremental learning from positive data. Technical Report RIFIS-TR-CS-117, RIFIS, Kyushu University 33, 1995.

Takashi Tabe and Thomas Zeugmann. Two variations of inductive inference of languages from positive data. Technical Report RIFIS-TR-CS-105, RIFIS, Kyushu University 33, 1995.

Thomas Zeugmann. Lange and wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time. Technical Report RIFIS-TR-CS-111, RIFIS, Kyushu University 33, 1995.

## 1994

### Journals

Steffen Lange and Thomas Zeugmann.
Characterization of language learning from informant under various
monotonicity constraints.
*J. of Experimental and Theoret. Artif. Intell.*, **6** no. 1 pp.
73-94, 1994.
Special issue for AII '92.

Rolf Wiehagen and Thomas Zeugmann.
Ignoring data may be the only way to learn efficiently.
*J. of Experimental and Theoret. Artif. Intell.*, **6** no. 1 pp.
131-144, 1994.
Special issue for AII '92.

Thomas Zeugmann.
Report on COLT
1994.
*ACM SIGART Bulletin*, **5** no. 4 pp. 25-27, 1994.

Thomas Zeugmann.
Report on COLT
1994.
*ACM SIGACT News*, **25** no. 4 pp. 88-95, 1994.

### International Conferences

Rolf Wiehagen, Carl H. Smith, and Thomas Zeugmann.
Classification of predicates and languages.
In *Computational Learning Theory: EuroColt '93*, volume New Series
Number 53 of *The Institute of Mathematics and its Applications Conference
Series*, pages 171-181, Oxford, 1994. Oxford University Press.

Steffen Lange and Thomas Zeugmann.
Set-driven and
rearrangement-independent learning of recursive languages.
In *Algorithmic Learning Theory, 4th International Workshop on Analogical
and Inductive Inference, AII '94, 5th International Workshop on Algorithmic
Learning Theory, ALT '94, Reinhardsbrunn Castle, Germany, October 1994,
Proceedings*, volume 872 of *Lecture Notes in Artificial
Intelligence*, pages 453-468. Springer-Verlag, 1994.

Thomas Zeugmann.
Average-case analysis of pattern language learning algorithms.
In *Algorithmic Learning Theory, 4th International Workshop on Analogical
and Inductive Inference, AII '94, 5th International Workshop on Algorithmic
Learning Theory, ALT '94, Reinhardsbrunn Castle, Germany, October 1994,
Proceedings*, volume 872 of *Lecture Notes in Artificial
Intelligence*, pages 8-9. Springer-Verlag, 1994.

### Technical Reports

## 1993

### Journals

Steffen Lange and Thomas Zeugmann.
Learning recursive
languages with bounded mind changes.
*International Journal of Foundations of Computer Science*, **4**
no. 2 pp. 157-178, 1993.

S. Minato.
Fast generation of prime-irredundant covers from binary decision diagrams.
*IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and
Computer Sciences*, **E76-A** no. 6 pp. 967-973, 1993.

S. Minato.
BEM-II: An arithmetic Boolean expression manipulator using BDDs.
*IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and
Computer Sciences*, **E76-A** no. 10 pp. 1721-1729, 1993.

### International Conferences

Steffen Lange and Thomas Zeugmann.
Language learning with
a bounded number of mind changes.
In *STACS 93, 10th Annual Symposium on Theoretical Ascpects of Computer
Science, Würzburg, Germany, February 1993, Proceedings*, volume 665
of *Lecture Notes in Computer Science*, pages 682-691.
Springer-Verlag, 1993.

Steffen Lange and Thomas Zeugmann.
Language learning in
dependence on the space of hypotheses.
In *Proceedings of the Sixth Annual ACM Conference on Computational
Learning Theory*, pages 127-136, New York, NY, 1993. ACM Press.

Steffen Lange and Thomas Zeugmann.
Monotonic versus
non-monotonic language learning.
In *Nonmonotonic and Inductive Logic, Second International Workshop,
Reinhardsbrunn Castle, Germany, December 1991*, volume 659 of *Lecture
Notes in Artificial Intelligence*, pages 254-269. Springer-Verlag, 1993.

### Technical Reports

Steffen Lange and Thomas Zeugmann. The learnability of recursive languages in dependence on the hypothesis space. Technical Report 20/93, GOSLER-Report, FB Mathematik und Informatik, TH Leipzig, 1993.

Steffen Lange and Thomas Zeugmann. On the impact of order independence to the learnability of recursive languages. Technical Report Research Report ISIS-RR-93-17E, FUJITSU Laboratories Ltd., Numazu, Japan, 1993.

## 1992

### Journals

Thomas Zeugmann.
Highly parallel
computations modulo a number having only small prime factors.
*Inform. Comput.*, **96** no. 1 pp. 95-114, 1992.

S. Minato.
Minimum-width method of variable ordering for binary decision diagrams.
*IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and
Computer Sciences*, **E75-A** no. 3 pp. 392-399, 1992.

### International Conferences

Steffen Lange and Thomas Zeugmann.
Types of monotonic
language learning and their characterization.
In *Proc. 5th Annual ACM Workshop on Comput. Learning Theory*, pages
377-390, New York, NY, 1992. ACM Press.

Steffen Lange and Thomas Zeugmann.
A unifying approach to
monotonic language learning on informant.
In *Analogical and Inductive Inference, International Workshop AII '92,
Dagstuhl Castle, Germany, October 1992, Proceedings*, volume 642 of
*Lecture Notes in Artificial Intelligence*, pages 244-259.
Springer-Verlag, 1992.

Rolf Wiehagen and Thomas Zeugmann.
Too much information can
be too much for efficient learning.
In *Analogical and Inductive Inference, International Workshop AII '92,
Dagstuhl Castle, Germany, October 1992, Proceedings*, volume 642 of
*Lecture Notes in Artificial Intelligence*, pages 72-86.
Springer-Verlag, 1992.
Invited Paper.

### Technical Reports

Steffen Lange and Thomas Zeugmann. On the power of monotonic language learning. Technical Report 5/92, GOSLER-Report, FB Mathematik und Informatik, TH Leipzig, 1992.

Steffen Lange and Thomas Zeugmann. Learning recursive languages with bounded mind changes. Technical Report 16/92, GOSLER-Report, FB Mathematik und Informatik, TH Leipzig, 1992.

Steffen Lange, Thomas Zeugmann, and Shyam Kapur. Class preserving monotonic and dual monotonic language learning. Technical Report 14/92, GOSLER-Report, FB Mathematik und Informatik, TH Leipzig, 1992.

Rolf Wiehagen and Thomas Zeugmann. Inconsistency can be necessary for learning in polynomial time. Technical Report 13/92, GOSLER-Report, FB Mathematik und Informatik, TH Leipzig, 1992.

Thomas Zeugmann, Steffen Lange, and Shyam Kapur. Characterizations of class preserving monotonic and dual monotonic language learning. Technical Report Technical Report IRCS 92 - 24, Institute for Research in Cognitive Science, University of Pennsylvania, Philadelphia, 1992.

## 1991

### Journals

Efim Kinber and Thomas Zeugmann.
One-sided error
probabilistic inductive inference and reliable frequency identification.
*Inform. Comput.*, **92** no. 2 pp. 253-284, 1991.

### Technical Reports

### International Conferences

Thomas Zeugmann.
Inductive inference of
optimal programs: A survey and open problems.
In *Nonmonotonic and Inductive Logic, 1st International Workshop,
Karlsruhe, Germany, December 1990, Proceedings*, volume 543 of
*Lecture Notes in Artificial Intelligence*, pages 208-222.
Springer-Verlag, 1991.

## 1990

### Journals

### International Conferences

Efim B. Kinber, William I. Gasarch, Thomas Zeugmann, Mark G. Pleszkoch, and
Carl H. Smith.
Learning via
queries with teams and anomalies.
In *Proceedings of the Third Annual Workshop on Computational Learning
Theory*, pages 327-337, San Mateo, CA, 1990. Morgan Kaufmann.

Thomas Zeugmann.
Computing large polynomial
powers very fast in parallel.
In *Mathematical Foundations of Computer Science 1990, Banská
Bystrica, Czechoslovakia, August 1990, Proceedings*, volume 452 of
*Lecture Notes in Computer Science*, pages 538-544. Springer-Verlag,
1990.

### Book Chapters

Thomas Zeugmann.
Parallel algorithms.
In *Encyclopedia of Computer Science and Technology*, volume 21,
Supplement 6, pages 223-244. Marcel Dekker Inc. New York and Basel, 1990.

### Technical Reports

## 1989

### Journals

Thomas Zeugmann.
Improved parallel computations in the ring
*Z _{pα}*.

*Elektronische Informationsverarbeitung und Kybernetik*,

**25**no. 10 pp. 543-547, 1989.

### International Conferences

Efim Kinber and Thomas Zeugmann.
Monte-carlo inference
and its relations to reliable frequency identification.
In *Fundamentals of Computation Theory, International Conference FCT
'89, Szeged, Hungary, August 1989, Proceedings*, volume 380 of
*Lecture Notes in Computer Science*, pages 257-266. Springer-Verlag,
1989.

Efim B. Kinber and Thomas Zeugmann.
Refined query
inference.
In *Analogical and Inductive Inference, International Workshop AII '89,
Reinhardsbrunn Castle, GDR, October 1989, Proceedings*, volume 397 of
*Lecture Notes in Artificial Intelligence*, pages 148-160.
Springer-Verlag, 1989.

### Technical Reports

## 1988

### Journals

Thomas Zeugmann.
On the power of
recursive optimizers.
*Theoret. Comput. Sci.*, **62** no. 3 pp. 289-310, 1988.

### International Conferences

### Technical Reports

Efim Kinber and Thomas Zeugmann. One-sided error probabilistic inductive inference and reliable frequency identification. Technical Report Preprint Nr. 185, Humboldt-Universität zu Berlin, Sektion Mathematik, 1988.

Thomas Zeugmann. Parallel algorithms. Technical Report Preprint Nr. 186, Humboldt-Universität zu Berlin, Sektion Mathematik, 1988.

## 1987

### Journals

### International Conferences

Thomas Zeugmann.
On Barzdin's
conjecture.
In *Analogical and Inductive Inference, International Workshop AII '86.
Wendisch-Rietz, GDR, October 1986, Proceedings*, volume 265 of
*Lecture Notes in Computer Science*, pages 220-227. Springer-Verlag,
1987.

### Technical Reports

## 1986

### Journals

### International Conferences

Thomas Zeugmann.
On recursive
optimizers.
In *Mathematical Methods of Specification and Synthesis of Software
Systems '85, Proceedings of the International Spring School Wendisch-Rietz,
GDR, April 22-26, 1985*, volume 215 of *Lecture Notes in Computer
Science*, pages 240-245. Springer-Verlag, 1986.

### Technical Reports

## 1985

### Journals

Efim B. Kinber and Thomas Zeugmann.
Inductive inference of almost everywhere correct programs by reliably working
strategies.
*Elektronische Informationsverarbeitung und Kybernetik*, **21** no.
3 pp. 91-100, 1985.

### International Conferences

### Technical Reports

## 1984

### Journals

Thomas Zeugmann.
On the nonboundability
of total effective operators.
*Zeitschr. f. math. Logik und Grundlagen d. Math.*, **30** no. 9-11
pp. 169-172, 1984.

### International Conferences

### Technical Reports

## 1983

### Journals

Thomas Zeugmann.
A-posteriori characterizations in inductive inference of recursive functions.
*Elektronische Informationsverarbeitung und Kybernetik*, **19** no.
10/11 pp. 559-594, 1983.

Thomas Zeugmann.
On the synthesis of fastest programs in inductive inference.
*Elektronische Informationsverarbeitung und Kybernetik*, **19** no.
12 pp. 625-642, 1983.

### International Conferences

### Technical Reports

Thomas Zeugmann.
*Zur algorithmischen Synthese von schnellen Programmen*.
PhD thesis, Humboldt-Universität zu Berlin, Sektion Mathematik, 1983.

### International Conferences

Thomas Zeugmann.
On the finite identification of fastest programs.
In Helena Rasiowa and Helmut Thiele, editors, *Symposium on Mathematical
Foundations of Computer Science, December 6-11, 1982, Diedrichshagen*,
pages 151-159, Berlin, Germany, 1983. Seminarbericht Nr. 52, Sektion
Mathematik, Humboldt-Universität zu Berlin.

This list was automatically generated with
Pubhtml.