Publications

Conference Papers / Journal Papers / Book


Conference Papers

Top / Journal Papers / Book

Tight Bounds for Cut-Operations on Deterministic Finite Automata

F. Drewes, M. Holzer, S. Jakobi, B. van der Merwe
In J. Durand-Lose, B. Nagy (eds.): Proceedings 7th International Conference on Machines, Computations, and Universality (MCU 2015),
volume 9288 of LNCS, pages 45-60, Famagusta, Cyprus, September 2015. Springer.


More on Deterministic and Nondeterministic Finite Cover Automata

H. Gruber, M. Holzer, S. Jakobi
In F. Drewes (ed.): Proceedings 20th International Conference on Implementation and Application of Automata (CIAA 2015),
volume 9223 of LNCS, pages 114-126, Umeå, Sweden, August 2015. Springer.


Minimal Reversible Deterministic Finite Automata

M. Holzer, S. Jakobi, M. Kutrib
In I. Potapov (ed.): Proceedings 19th International Conference on Developments in Language Theory (DLT 2015),
volume 9168 of LNCS, pages 276-287, Liverpool, United Kingdom, July 2015. Springer.


A Hierarchy of Fast Reversible Turing Machines

H. B. Axelsen, S. Jakobi, M. Kutrib, A. Malcher
In J. Krivine, J.-B. Stefani (eds.): Proceedings 7th International Conference on Reversible Computation (RC 2015),
volume 9138 of LNCS, pages 29-44, Grenoble, France, July 2015. Springer.


On the Computational Complexity of Problems Related to Distinguishability Sets

M. Holzer, S. Jakobi
In J. Shallit, A. Okhotin (eds.): Proceedings 17th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2015),
volume 9118 of LNCS, pages 117-128, Waterloo, Ontario, Canada, June 2015. Springer.


Minimal and Hyper-Minimal Biautomata

M. Holzer, S. Jakobi
In A. M. Shur, M. V. Volkov (eds.): Proceedings 18th International Conference on Developments in Language Theory (DLT 2014),
volume 8633 of LNCS, pages 291-302, Ekaterinburg, Russia, August 2014. Springer.


Boundary Sets of Regular and Context-Free Languages

M. Holzer, S. Jakobi
In H. Jürgensen, J. Karhumäki, A. Okhotin (eds.): Proceedings 16th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2014),
volume 8614 of LNCS, pages 162-173, Turku, Finland, August 2014. Springer.


On the Computational Complexity of Partial Word Automata Problems

M. Holzer, S. Jakobi, M. Wendlandt
In S. Bensch, R. Freund, F. Otto (eds.): Proceedings 6th Workshop on Non-Classical Models of Automata and Applications (NCMA 2014),
volume 304 of books@ocg.at, Austrian Computer Society, pages 131-146, Kassel, Germany, July 2014.


More Structural Characterizations of Some Subregular Language Families by Biautomata

M. Holzer, S. Jakobi
In Z. Ésik, Z. Fülöp (eds.): Proceedings 14th International Conference on Automata and Formal Languages (AFL 2014),
volume 151 of EPTCS, pages 171-285, Szeged, Hungary, May 2014.


Minimization and Characterizations for Biautomata

M. Holzer, S. Jakobi
In S. Bensch, F. Drewes, R. Freund, F. Otto (eds.): Proceedings 5th Workshop on Non-Classical Models of Automata and Applications (NCMA 2013),
volume 294 of books@ocg.at, Austrian Computer Society, pages 179-193, Umeå, Sweden, August 2013.


Nondeterministic Biautomata and Their Descriptional Complexity

M. Holzer, S. Jakobi
In H. Jürgensen, R. Reis (eds.): Proceedings 15th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2013),
volume 8031 of LNCS, pages 112-123, London, Ontario, Canada, July 2013. Springer.


Queue Automata of Constant Length

S. Jakobi, K. Meckel, C. Mereghetti, B. Palano
In H. Jürgensen, R. Reis (eds.): Proceedings 15th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2013),
volume 8031 of LNCS, pages 124-135, London, Ontario, Canada, July 2013. Springer.


Brzozowski's Minimization Algorithm---More Robust than Expected (Extended Abstract)

M. Holzer, S. Jakobi
In S. Konstantinidis (ed.): Proceedings 18th International Conference on Implementation and Application of Automata (CIAA 2013),
volume 7982 of LNCS, pages 181-192, Halifax, Nova Scotia, Canada, July 2013. Springer.


Generalized Derivations with Synchronized Context-Free Grammars

M. Holzer, S. Jakobi, I. McQuillan
In H.-C. Yen, O. H. Ibarra (eds.): Proceedings 16th International Conference on Developments in Language Theory (DLT 2012),
volume 7410 of LNCS, pages 109-120, Taipei, Taiwan, August 2012. Springer.


From Equivalence to Almost-Equivalence, and Beyond---Minimizing Automata with Errors (Extended Abstract)

M. Holzer, S. Jakobi
In H.-C. Yen, O. H. Ibarra (eds.): Proceedings 16th International Conference on Developments in Language Theory (DLT 2012),
volume 7410 of LNCS, pages 190-201, Taipei, Taiwan, August 2012. Springer.


On Inverse Operations and Their Descriptional Complexity

M. P. Bianchi, M. Holzer, S. Jakobi, G. Pighizzini
In M. Kutrib, N. Moreira, R. Reis (eds.): Proceedings 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012),
volume 7386 of LNCS, pages 89-102, Braga, Portugal, July 2012. Springer.


State Complexity of Chop Operations on Unary and Finite Languages

M. Holzer, S. Jakobi
In M. Kutrib, N. Moreira, R. Reis (eds.): Proceedings 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012),
volume 7386 of LNCS, pages 169-182, Braga, Portugal, July 2012. Springer.


Grid Graphs with Diagonal Edges and the Complexity of Xmas Mazes

M. Holzer, S. Jakobi
In E. Kranakis, D. Krizanc, F. Luccio (eds.): Proceedings 6th International Conference on Fun with Algorithms (FUN 2012),
volume 7288 of LNCS, pages 223-234, Venice, Italy, June 2012. Springer.


On the Complexity of Rolling Block and Alice Mazes

M. Holzer, S. Jakobi
In E. Kranakis, D. Krizanc, F. Luccio (eds.): Proceedings 6th International Conference on Fun with Algorithms (FUN 2012),
volume 7288 of LNCS, pages 210-222, Venice, Italy, June 2012. Springer.


The Chop of Languages

M. Holzer, S. Jakobi, M. Kutrib
In P. Dömösi, S. Iván (eds.): Proceedings 13th International Conference on Automata and Formal Languages (AFL 2011),
Institute of Mathematics and Informatics, College of Nyíregyháza, pages 197-210, Debrecen, Hungary, August 2011.


Chop Operations and Expressions: Descriptional Complexity Considerations

M. Holzer, S. Jakobi
In G. Mauri, A. Leporati (eds.): Proceedings 15th International Conference on Developments in Language Theory (DLT 2011),
volume 6795 of LNCS, pages 264-275, Milan, Italy, July 2011. Springer.


The Magic Number Problem for Subregular Language Families

M. Holzer, S. Jakobi, M. Kutrib
In I. McQuillan, G. Pighizzini (eds.): Proceedings 12th Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010),
volume 31 of EPTCS, pages 110-119, Saskatchewan, Saskatoon, Canada, August 2010.




Journal Papers

Top / Conference Papers / Book

Minimization and Characterizations for Biautomata

M. Holzer, S. Jakobi
Fundamenta Informaticae, 136(1-2): 113-137, 2015.


Nondeterministic Biautomata and Their Descriptional Complexity

M. Holzer, S. Jakobi
International Journal of Foundations of Computer Science, 25(7): 837-855, 2014.


From Equivalence to Almost-Equivalence, and Beyond: Minimizing Automata With Errors

M. Holzer, S. Jakobi
International Journal of Foundations of Computer Science, 24(7): 1083-1097, 2013.


On Inverse Operations and Their Descriptional Complexity

M. P. Bianchi, M. Holzer, S. Jakobi, C. Mereghetti, B. Palano, G. Pighizzini
Journal of Automata, Languages and Combinatorics, 17(2-4): 61-81, 2012.


Descriptional Complexity of Chop Operations on Unary and Finite Languages

M. Holzer, S. Jakobi
Journal of Automata, Languages and Combinatorics, 17(2-4): 165-183, 2012.


The Magic Number Problem for Subregular Language Families

M. Holzer, S. Jakobi, M. Kutrib
International Journal of Foundations of Computer Science, 23(1): 115-131, 2012.




Book

Top / Conference Papers / Journal Papers

Modern Aspects of Classical Automata Theory:
Finite Automata, Biautomata, and Lossy Compression

S. Jakobi
Logos Verlag, Berlin, Germany, 2015, ISBN 978-3-8325-3944-3.
Dissertation, Justus-Liebig-Universität Gießen, 2014.


Home