Universität Tübingen, Wilhelm-Schickard Institut für Informatik

Henning Fernau

Publications

The copyright of the following papers is mostly with the publishing instances, which are indicated in all cases, and are made available only for personal use. Confirming with an IEEE guideline, we want to stress that:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

1991

H. Fernau. On function-limited Lindenmayer systems. EIK 27 (1991), pages 21-53.
H. Fernau. Ersetzungssysteme mit eingeschränkter Parallelität. IN: TU Clausthal: Informatik-Bericht 91/1; Workshop über Parallelverarbeitung ICL, pages 41-58.

1992

H. Fernau. Unendliche iterierte Funktionensysteme (IIFS). IN: TU Clausthal: Informatik-Bericht 92/1; Workshop über Parallelverarbeitung ICL, pages 39-61.
H. Fernau. MRFS-Fraktale aus dem Blickwinkel der regulären omega-Sprachen. IN: Universität Kiel: Technische Berichte 9220; 2. Theorietag `Automaten und Formale Sprachen', pages 46-50.

1993

H. Fernau. Adult Languages of Propagating Systems with Restricted Parallelism. EIK 29 (1993), pages 249-267.
H. Fernau. IIFS and Codes (Extended version). Universität Karlsruhe, Fakultät für Informatik, No. 23/93.

1994

H. Fernau. Bewertungen regulärer Ausdrücke, Zusammenhänge mit strenger Eindeutigkeit regulärer Ausdrücke sowie Anwendungen bei der Berechnung der Hausdorff-Dimension von Fraktalen, die mit regulären Ausdrücken beschrieben werden. IN: Universität Stuttgart, Fakultät Informatik: Bericht 1/1994; 3. Theorietag `Automaten und Formale Sprachen' in Dagstuhl, pages 18-19.
H. Fernau. Remarks on adult languages of propagating systems with restricted parallelism. IN: Developments in Language Theory, World Scientific, Singapore, 1994, pages 90-101.
H. Fernau. Iterierte Funktionen, Sprachen und Fraktale. Mannheim: BI-Verlag, 1994. (first 20 pages on www) This book basically contains my PhD thesis. An English summary of my PhD appeared in EATCS Bulletin in 1994.
H. Fernau. Infinite iterated function systems. Mathematische Nachrichten 169 (1994), pages 79-91.
H. Fernau. Observations on Grammar and Language Families. Universität Karlsruhe, Fakultät für Informatik, No. 22/94. Most of the material has appeared in Fundamenta Informaticae (1996)
H. Fernau. Membership for Limited ET0L Languages Is Not Decidable. Universität Karlsruhe, Fakultät für Informatik, No. 34/94. An enhanced version of the material appeared in EIK
H. Fernau. IIFS and codes. IN: Developments In Theoretical Computer Science, Proceedings of the 7th International Meeting of Young Computer Scientists, pages 141-152. Gordon and Breach Science Publishers, Switzerland, 1994.
H. Fernau and L. Staiger. Valuations and unambiguity of languages, with applications to fractal geometry. IN: Automata, Languages and Programming, 21st International Colloquium, ICALP 94; LNCS vol. 820, pages 11-22.
H. Fernau and L. Staiger. Valuations and unambiguity of languages, with applications to fractal geometry. RWTH Aachen, TR No. 94-22.
H. Fernau. Membership for 1-limited ET0L languages is not decidable. EIK 30 (1994), pages 191-211.
H. Bordihn and H. Fernau. Accepting Grammars and Systems. Universität Karlsruhe, Fakultät für Informatik, No. 22/94.
H. Bordihn and H. Fernau. Accepting Grammars with Regulation. IJCM 53 (1994), pages 1-18. The material is also contained in our report.

1995

H. Fernau and H. Bordihn. Remarks on Accepting Parallel Systems. IJCM 56 (1995), pages 51-67. The material is also contained in our report.
H. Fernau. Valuations of languages, with applications to fractal geometry. TCS 137 (1995), pages 177-217.
H. Fernau. A note on uniformly limited ET0L systems with unique interpretation. IPL 54 (1995), pages 199-204. The material is also contained in our report.
H. Fernau und H. Bordihn. Programmierte Grammatiken und limitierte L Systeme als Sprachakzeptoren IN: Universität Tübingen, Wilhelm-Schickard-Institut: Bericht WSI 95-10; 4. Theorietag `Automaten und Formale Sprachen' in Herrsching bei München, pages 21-24.
H. Fernau. A predicate for separating language classes. EATCS Bulletin 56 (1995), pages 96-97.
H. Bordihn und H. Fernau. Accepting programmed grammars without nonterminals IN: Universität Giessen, Arbeitsgruppe Informatik: Bericht 9503; 5. Theorietag `Automaten und Formale Sprachen' in Rauischolzhausen, pages 4-16.
H. Fernau. Programmierte Grammatiken mit unbedingtem Übergang und verwandte Mechanismen IN: Universität Giessen, Arbeitsgruppe Informatik: Bericht 9503; 5. Theorietag `Automaten und Formale Sprachen' in Rauischolzhausen, pages 47-57.

1996

H. Fernau. Valuations, regular expressions, and fractal geometry pp.1-13, page 14 pp. 15-16. AAECC (Applicable Algebra in Engineering, Communication and Computing) 7 (1996), pages 59-75.
H. Fernau. Closure properties of ordered languages. EATCS Bulletin 58 (1996), pages 159-162.
H. Fernau and M. Holzer. Bidirectional cooperating distributed grammar systems. Technical Report WSI-96-01, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, February 1996. The material has been presented at AFL conference at Salgotarjan, Hungary, and is published in Publ.Math., Debrecen, see below.
H. Fernau. On unconditional transfer. Proceedings of MFCS'96 (LNCS 1113), pages 348-359. Springer, 1996.
H. Fernau and R. Freund. Bounded parallelism in array grammars used for character recognition. Proceedings of SSPR'96 (LNCS 1121), pages 40-49. Springer, 1996.
H. Fernau and M. Holzer. Regulated finite index language families collapse. Technical Report WSI-96-16, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, May 1996.
H. Fernau and D. Wätjen. Remarks on regulated limited ET0L systems and regulated context-free grammars . Technical Report WSI-96-19, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, May 1996. (Revised version published in TCS 1998)
H. Fernau and M. Holzer and H. Bordihn. Accepting multi-agent systems: The case of cooperating distributed grammar systems. Journal of Computers and Artificial Intelligence, 15(2-3) (1996), pages 123-139.
H. Fernau. Unconditional transfer in regulated rewriting . Technical Report WSI-96-21, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, July 1996. One part of this report has appeared in Acta informatica, another on in Journal of Automata, Languages and Combinatorics.
H. Bordihn and H. Fernau. Accepting grammars and systems: an overview. (extended version) IN: J. Dassow, G. Rozenberg, A. Salomaa: Developments in Language Theory II. World Scientific, Singapore, 1996, pages 199-208. A journal version appeared in Journal of Automata, Languages and Combinatorics.
H. Fernau, K.-J. Lange and K. Reinhardt. Advocating Ownership. IN: Proceedings of FST & TCS'96 (LNCS 1180), pages 286-297. Springer, 1996.
H. Bordihn and H. Fernau. Accepting grammars and systems via context condition grammars. Journal of Automata, Languages and Combinatorics, 1(2) (1996), pages 97-112.
H. Fernau. Remarks on propagating partition-limited ET0L systems. Journal of Universal Computer Science at Springer's 2(11) (1996), pages 745-755.
H. Fernau. Scattered context grammars with regulation. Ann. Univ. Bucharest, Math.-Informatics Series 45(1) (1996), pages 41-49.
H. Fernau. On grammar and language families. Fundamenta Informaticae 25(1) (1996), pages 17-34.
H. Fernau and M. Holzer and R. Freund. Bounding Resources in Multi-Agent Systems. IN: Universität Dresden, Arbeitsgruppe Informatik; 6. Theorietag `Automaten und Formale Sprachen' in Cunnersdorf. 1996
H. Fernau. Membership for k-limited ET0L languages is not decidable. Journal of Automata, Languages and Combinatorics, 1(4) (1996), pages 243-245.
H. Fernau and M. Holzer. Accepting multi-agent systems II. Acta Cybernetica 12 (1996), pages 361-379. ( see also ) The material has been presented at a Workshop on Grammar Systems in Budapest.
H. Fernau and M. Holzer and R. Freund. External versus internal hybridization in cooperating distributed grammar systems. Technical Report TR 185-2/FR-1/96, Technische Universität Wien, 1996. A revision of the first two parts of this work has been accepted for publication in Theoretical Computer Science. An extended abstract has been presented in the proceedings of the 3rd Int. Conf. Developments in Language Theory, edited by S. Bozapalidis, published by Aristotle University of Thessaloniki, pages 261-272.
1997
H. Fernau and M. Holzer. Conditional context-free languages of finite index. IN: Gh. Paun, A. Salomaa: New Trends in Formal Languages (LNCS 1218), pages 10-26. Springer, 1997.
H. Fernau and R. Freund. Accepting array grammars with control mechanisms. IN: Gh. Paun, A. Salomaa: New Trends in Formal Languages (LNCS 1218), pages 95-118. Springer, 1997.
H. Fernau. Unconditional transfer in regulated rewriting. Acta Informatica 34 (1997), pages 837-857.
H. Fernau. Graph-controlled grammars as language acceptors. Journal of Automata, Languages and Combinatorics, 2 (1997), pages 79-91.
H. Fernau and F. Stephan. How Powerful is Unconditional Transfer? ---When UT meets AC.--- Technical Report WSI-97-07, Universit�t T�bingen, Wilhelm-Schickard-Institut f�r Informatik, Sand 13, D-72076 Tübingen, Germany, July 1997. The DLT'97 conference version appeared in the proceedings of the 3rd Int. Conf. Developments in Language Theory, edited by S. Bozapalidis, published by Aristotle University of Thessaloniki, pages 249-260. An extended journal version is published in Journal of Automata, Languages and Combinatorics, see below.
H. Fernau and R. Stiebe. Regulation by valences. IN: B. Rovan: Proceedings of MFCS'97 (LNCS 1295), pages 239-248. Springer, 1997. An extended report version is available.
J. Dassow, H. Fernau, Gh. Paun and F. Stephan. Linksableitungen bei programmierten Grammatiken. IN: Universität Bremen, Arbeitsgruppe Informatik; 7. Theorietag `Automaten und Formale Sprachen' in Barnstorf. 1997
1998
H. Fernau and D. Wätjen. Remarks on regulated limited ET0L systems and regulated context-free grammars. also see Technical Report WSI-96-19. Theoretical Computer Science 194(1-2) (1998), pages 35-55.
H. Fernau. On Graph-Controlled Grammars with Leftmost Derivation. Universität Stuttgart: Workshop on Formal Languages, Automata and Petri-Nets IFI Report No. 1998/01, page 7. An extended version is presented at SOFSEM'98.
H. Fernau, R. Freund, and M. Holzer. The Generative Power of d-Dimensional #-Context-Free Array Grammars, Proceedings of MCU'98, Volume 2, pages 43-56. Metz, France, 1998.
H. Fernau, R. Freund, and M. Holzer. Character Recognition with k-Head Finite Array Automata, Proceedings of SSPR'98 ( LNCS 1451), pages 282-291, 1998.
H. Fernau and R. Niedermeier. Zur Rekonfigurierung von VLSI-Chips. IN: 35. Theorietag `Datenstrukturen, effiziente Algorithmen und Komplexitätstheorie' (Universität Paderborn ), page 7, 1998.
H. Fernau and L. Staiger. IFS and Control Languages , Proceedings of MFCS'98 ( LNCS 1450), pages 740-750, 1998. An extended version appeared as Technical Report No. 16 (1999), Fachbereich Mathematik und Informatik Informatik, Universität Halle-Wittenberg. A slightly corrected version will appear in Information and Computation.
H. Fernau, R. Freund, and M. Holzer. Representations of recursively enumerable array languages by d-dimensional contextual array grammars. , to appear in the special issue "Frontiers between Decidability and Undecidability" (Satellite Workshop of MFCS'98) of RAIRO-Informatique theorique et Applications.
H. Fernau. Regulated Grammars with Leftmost Derivation , © Springer-Verlag, Proceedings of SOFSEM'98 ( LNCS 1521), pages 322-331, 1998. Full version accepted for publication in GRAMMARS.
H. Fernau and R. Stiebe. Regulation by valences. Technical Report No. 36, Fachbereich Mathematik und Informatik Informatik, Universität Halle-Wittenberg, 1998.

1999

H. Fernau, R. Freund, and M. Holzer. Regulated array grammars of finite index. IN: Gh. Paun, A. Salomaa (ed.) Grammatical Models of Multi-Agent Systems, Gordon and Breach, pages 157-181 (Part I) and 284-296 (Part II), 1999.
H. Bordihn, H. Fernau, and M. Holzer. Accepting pure grammars and systems. Technical Report 1, Fakultät für Informatik, Universität Magdeburg, 1999. The first part of this paper has been presented at AFL conference at Szombathely, Hungary, and will hence be published in Publ.Math., Debrecen. The last part appeared in Fundamenta Informaticae, see below.
H. Fernau. Efficient learning of some linear matrix languages , © Springer-Verlag, Proceedings of COCOON'99 ( LNCS 1627), pages 221-230, 1999. A long version is available as Technical Report WSI-2000-9. An updated version of this report is accepted for publication in Theoretical Computer Science under the title Even linear simple matrix languages: formal language properties and grammatical inference and can be retrieved from Elsevier.
H. Fernau and R. Niedermeier. An efficient exact algorithm for constraint bipartite vertex cover. Technical Report Charles University, Praha, Faculty of Mathematics and Physics, KAM-DIMATIA Series 99-424, March 1999. Extended Abstract appeared in the Proceedings of MFCS'99 (© Springer-Verlag, LNCS 1672), pages 387-398, 1999. Confer also 38. Theorietag `Datenstrukturen, effiziente Algorithmen und Komplexitätstheorie' (Universität Heidelberg), page 8, 1999. Full version submitted.
H. Fernau and M. Holzer. Bidirectional cooperating distributed grammar systems. also see Technical Report WSI-96-01. Publ. Math. Debrecen, 54 Supplement (1999), pages 787-806.
H. Fernau and F. Stephan. Characterizations of recursively enumerable languages by programmed grammars with unconditional transfer. also see Technical Report WSI-97-07. Journal of Automata, Languages and Combinatorics, 4 (1999), pages 117-142.
J. Dassow, H. Fernau, and Gh. Paun. On the leftmost derivation in matrix grammars. International Journal of Foundations of Computer Science, 10 (1999), pages 61-80.
H. Fernau, K. Reinhardt, and L. Staiger. Decidability of code properties, Proceedings of the Conference DLT'99 held at Aachen, Germany. Published by World Scientific, 2000, pages 153-163. A longer version appeared as Technical Report and is submitted to a journal.
H. Bordihn, H. Fernau, and M. Holzer. On Accepting Pure Lindenmayer Systems. Fundamenta Informaticae, 38 (1999), pages 365-375. This paper is basically a part of our report. (Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, No. 1, 1999)
H. Fernau. Learning of terminal distinguishable languages. Technical Report WSI-99-23, Universit�t T�bingen, Wilhelm-Schickard-Institut f�r Informatik, Sand 13, D-72076 Tübingen, Germany, Dec. 1999. The material has been presented at the Sixth International Symposium on Artificial Intelligence and Mathematics (AMAI), Fort Lauderdale, Florida, Jan. 5th till Jan. 7th, 2000.

2000

J. Alber, H.L. Bodlaender, H. Fernau, and R. Niedermeier. Fixed parameter algorithms for planar dominating set and related problems, IN: Scandinavian Workshop on Algorithms SWAT 2000. © Springer-Verlag, LNCS 1851, pages 97-110. Confer also 40. Theorietag `Datenstrukturen, effiziente Algorithmen und Komplexitätstheorie' (Technische Universität Ilmenau), page 4, 2000. An enhanced submitted journal version is available as Technical Report UU-CS-2000-28, Institute for Information and Computing Sciences, Utrecht University (2000).
H. Fernau. k-gram extensions of terminal distinguishable languages, IN: Proceedings of the International Conference on Pattern Recognition ICPR 2000, vol. 2, pages 125-128. © IEEE Press, 2000.
H. Fernau. PC grammar systems with terminal transmission, IN: R. Freund and A. Kelemenova (eds.), Proceedings of the International Workshop Grammar Systems 2000, pages 229-252. Extended version is available as Technical Report WSI-2000-15. A slightly modified version has been published in Acta Informatica.
H. Fernau and R. Freund and M. Holzer. Cooperating distributed grammar systems with exhausting resources , IN: R. Freund and A. Kelemenova (eds.), Proceedings of the International Workshop Grammar Systems 2000, pages 113-125.
H. Fernau and J. M. Sempere. Permutations and control sets for learning non-regular language families, IN: A.L. Oliveira (ed.), Proceedings of the 5th International Conference on Grammatical Inference (ICGI 2000), © Springer-Verlag, LNCS 1891, pages 75-88.
H. Fernau. Technical Report WSI-2000-13. On Learning Function Distinguishable Languages.
H. Fernau and R. Stiebe. Valences in Parallel Systems. Technical Report No. 18, Fachbereich Mathematik und Informatik Informatik, Universität Halle-Wittenberg, 2000.
H. Fernau. Regulated grammars with leftmost derivation. Grammars 3 (2000), pages 37-62.
H. Fernau and M. Holzer. External Contextual and Conditional Languages. IN: C. Martin-Vide and Gh. Paun (eds.), Recent Topics in Mathematical and Computational Linguistics, pages 104-120. Bucharest: The Publishing House of the Romanian Academy, 2000.
H. Fernau and W. Kuich. Regularly controlled formal power series. IN: C. Martin-Vide and V. Mitrana (ed.), Where Mathematics, Computer Science, Linguistics and Biology Meet, pages 253-265. Dordrecht: Kluwer, 2000.
H. Fernau. Identification of function distinguishable languages, IN: H. Arimura, S. Jain and A. Sharma (ed.), Proceedings of the 11th International Conference on Algorithmic Learning Theory (ALT 2000), © Springer-Verlag, LNCS 1968, pages 116-130. A preliminary version appeared as Technical Report.
H. Fernau and R. Stiebe. Technical Report WSI-2000-25. Sequential Grammars and Automata with Valences.
H. Fernau. Technical Report WSI-2000-26. Nonterminal complexity of programmed grammars.

2001

H. Fernau. Technical Report WSI-2001-1. Learning XML grammars. An extended version appeared in P. Perner (editor), Machine Learning and Data Mining in Pattern Recognition MLDM'01, © Springer-Verlag, LNCS 2123, pages 73-87.
J. Alber, H. Fernau and R. Niedermeier. Technical Report ECCC TR01-023. Parameterized complexity: exponential speedup for planar graph problems.
H. Fernau and R. Niedermeier. An efficient exact algorithm for constraint bipartite vertex cover. Journal of Algorithms, 38 (2001), pages 374-410.
H. Fernau. Parallel communicating grammar systems with terminal transmission. Acta Informatica, 37 (2001), pages 511-540.
H. Fernau and R. Stiebe. Valences in Lindenmayer systems. Fundamenta Informaticae, 45 (2001), pages 329-358.
H. Fernau. Nonterminal complexity of programmed grammars. IN: M. Margenstern and Y. Rogozhin (ed.), Machines, Computations, and Universality, Proceedings of the 3rd MCU 2001, © Springer-Verlag, LNCS 2055, pages 202-213.
H. Fernau, R. Freund, and M. Holzer. Hybrid Modes in Cooperating Distributed Grammar Systems: Internal versus External Hybridization. Theoretical Computer Science, 259 (2001), pages 405-426.
H. Fernau. Even linear simple matrix languages: formal language aspects. IN: C.S. Calude, M.J. Dinneen and S. Sburlan (ed.), Discrete Mathematics and Theoretical Computer Science (DMTCS 2001), © Springer-Verlag , pages 81-96.
J. Alber, H. Fernau and R. Niedermeier. Parameterized complexity: exponential speedup for planar graph problems. IN: F. Orejas, P. Spirakis and J. van Leeuwen (ed.), Proceedings ICALP 2001, © Springer-Verlag, LNCS 2076, pages 261-272.
H. Fernau and R. Stiebe. Valuated and valence grammars: an algebraic view. IN: W. Kuich (ed.), Preproceedings DLT 2001, TU Wien, Institut f. Algebra und Computermathematik, pages 290-301.
H. Fernau and L. Staiger. IFS and control languages. Information and Computation, 168 (2001), pages 125-143.
H. Fernau and M. Holzer. Graph controlled cooperating distributed grammar systems with singleton components. IN: J. Dassow and D. Wotschke (eds.), Preproceedings Workshop DCAGRS 2001. Otto-von-Guericke-Universität Magdeburg, Fak. f. Informatik, Preprint Nr. 16, pages 79-90.
H. Fernau. Learning XML grammars. IN: P. Perner (ed.), Proceedings International Workshop on Machine Learning and Data Mining in Pattern Recognition (MLDM 2001). © Springer-Verlag, LNCS 2123, pages 73-87.
J. Alber, H. Fernau and R. Niedermeier. Graph separators: a parameterized view. IN: J. Wang (ed.), Computing and Combinatorics, Proceedings COCOON 2001. © Springer-Verlag, LNCS 2108, pages 318-327.
J. Alber, H. Fan, M. R. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, and U. Stege. Refined search tree techniques for the PLANAR DOMINATING SET problem. IN: J. Sgall, A. Pultr and P. Kolman (ed.), Mathematical Foundations of Computer Science (MFCS 2001). © Springer-Verlag, LNCS 2136, pages 111-122.
F. Hüffner, S. Edelkamp, H. Fernau and R. Niedermeier. Finding optimal solutions to Atomix. IN: F. Baader, G. Brewka and T. Eiter (ed.): KI 2001: Advances in Artificial Intelligence, © Springer-Verlag, LNCS/LNAI 2174, pages 229-243.
H. Fernau. Technical Report WSI-2001-2. Approximative Learning of Regular Languages. An extended abstract appeared IN: L. Pacholski and P. Ruzicka (ed.): SOFSEM'01; Theory and Practice of Informatics, © Springer-Verlag, LNCS 2234, pages 223-232.
H. Fernau. Technical Report WSI-2001-19. Learning tree languages from text.
H. Fernau and R. Stiebe. Valence grammars with target sets.. IN: M. Ito, Gh. Paun and S. Yu (ed.), Words, Semigroups, and Transductions, pages 129-140. Singapore: World Scientific, 2001.
H. Fernau. Technical Report WSI-2001-21. On parameterized enumeration.
H. Fernau. Technical Report WSI-2001-22. Parameterized maximization.

2002

H. Fernau and R. Stiebe. Valuated and valence grammars: an algebraic view. IN: W. Kuich and G. Rozenberg (ed.), Proceedings DLT 2001, © Springer-Verlag, LNCS 2295, pages 281-292, 2002.
H. Fernau and R. Stiebe. Sequential grammars and automata with valences. Theoretical Computer Science, vol. 276 (2002), pp. 377-405.
H. Bordihn, H. Fernau and M. Holzer. Accepting pure grammars. Publicationes Mathematicae, Debrecen, vol. 60 Supplement (2002), pp. 483-510.
J. Alber, H.L. Bodlaender, H. Fernau, T. Kloks and R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, vol. 33 (2002), pp. 461-493.
H. Fernau. Learning tree languages from text. In J. Kivinen and R.H. Sloan (editors): Computational Learning Theory COLT 2002, vol. 2375 of LNCS/LNAI, pp. 153-168. Berlin: © Springer-Verlag, 2002.
H. Fernau and A. Radl. Algorithms for learning function distinguishable regular languages. In T. Caelli, A. Amin, R.P.W. Duin, M. Kamel and D. de Ridder (editors): Structural, Syntactic, and Statistical Pattern Recognition SSPR and SPR 2002, vol. 2396 of LNCS, pp. 64-72. Berlin: © Springer-Verlag, 2002.
H. Fernau. On parameterized enumeration. In O.H. Ibarra and L. Zhang (editors): Computing and Combinatorics, Proceedings COCOON 2002, vol. 2383 of LNCS, pp. 564-573. Berlin: © Springer-Verlag, 2002.
H. Fernau. Parallel Grammars: A Phenomenology
H. Fernau. Fragmentation: enhancing identifiability. In P. Adriaans, H. Fernau and M. van Zaanen (editors): Grammatical Inference: Algorithms and Applications; 6th International Colloquium: ICGI 2002, vol. 2484 of LNCS/LNAI, pp. 92-105. Berlin: © Springer-Verlag, 2002.
H. Fernau. Graph separator algorithms: a refined analysis. In L. Kucera (editor): Graph-Theoretic Concepts in Computer Science WG 2002. vol. 2573 of LNCS, pp. 186-197. Berlin: © Springer-Verlag, 2002.
H. Fernau. Even linear simple matrix languages: formal language properties and grammatical inference. Theoretical Computer Science, vol. 289 (2002), pp. 425-456.
H. Fernau and M. Holzer. Graph controlled cooperating distributed grammar systems with singleton components. Journal of Automata, Languages, and Combinatorics, vol. 7 (2002), pp. 487-503.
2003
H. Fernau. Identification of function distinguishable languages. Theoretical Computer Science, vol. 290 (2003), pp. 1679-1711.
H. Fernau and A. Meduna. On the degree of scattered context-sensitivity. Theoretical Computer Science, vol. 290 (2003), pp. 2121-2124.
H. Bordihn, H. Fernau and M. Holzer. On iterated sequential transducers. In C. Martin-Vide and V. Mitrana (editors): Grammars and Automata for String Processing: from Mathematics and Computer Science to Biology, and Back. London: Taylor and Francis, 2003, pp. 121-130.
H. Fernau. Nonterminal complexity of programmed grammars. Theoretical Computer Science, vol. 296 (2003), pp. 225-251.
H. Fernau, R. Freund and M. Holzer. Hybrid modes in cooperating distributed grammar systems: combining the t-mode with the modes < k and = k. Theoretical Computer Science, vol. 299 (2003), pp. 633-662.
H. Fernau and A. Meduna. A simultaneous reduction of several measures of descriptional complexity in scattered context grammars. Information Processing Letters, vol. 86 (2003), pp. 235-240.
H. Fernau. Parallel grammars: a phenomenology. GRAMMARS, vol. 6 (2003), pp. 25-87.
H. Fernau. Education(al) matters: teaching P versus NP. EATCS Bulletin, vol. 80 (2003), pp. 237-246.
H. Fernau, T. Hagerup, N. Nishimura, P. Ragde, and K. Reinhardt. On the parameterized complexity of a generalized Rush Hour puzzle. In: Canadian Conference on Computational Geometry, CCCG'03, pp. 6-9. The results were also presented at the Dagstuhl workshop on Parameterized Complexity in 2003.
V. Dujmovic, H. Fernau and M. Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited. In G. Liotta (editor): Graph Drawing, GD'03. vol. 2912 of LNCS, pp. 332-344. Berlin: © Springer-Verlag, 2004. The results were also presented at the Dagstuhl workshop on Parameterized Complexity in 2003.
J. Alber, H. Fernau and R. Niedermeier. Graph separators: a parameterized view. Journal of Computer and System Sciences, vol. 67 (2003), pp. 808-832.
2004
H. Fernau. Identifying terminal distinguishable languages. Annals of Mathematics and Artificial Intelligence, vol. 40 (2004), pp. 263-281.
H. Fernau. Complexity of a {0,1}-matrix problem. The Australasian Journal of Combinatorics, vol. 29 (2004), pp. 273-300.
H. Fernau. Parametric Duality: Kernel Sizes and Algorithmics. Electronic Colloquium on Computational Complexity Report TR04-027, 2004.
J. Alber, H. Fernau and R. Niedermeier. Parameterized complexity: exponential speedup for planar graph problems. Journal of Algorithms, vol. 52 (2004), pp. 26-56.
H. Fernau and D. Juedes. A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs. In: Mathematical Foundations of Computer Science MFCS'04. vol. 3153 of LNCS, pp. 488-499. Berlin: © Springer-Verlag, 2004.
H. Fernau. A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set. Electronic Colloquium on Computational Complexity Report TR04-073, 2004.
H. Fernau. Two-Layer Planarization: Improving on Parameterized Algorithmics. Electronic Colloquium on Computational Complexity Report TR04-078, 2004; extended abstract accepted at SOFSEM 2005.
H. Fernau. Extracting minimum length Document Type Definitions is NP-hard (Abstract) In: International Colloquium on Grammatical Inference ICGI'04. vol. 3264 of LNCS/LNAI, pp. 277-278. Berlin: © Springer-Verlag, 2004.
B. Starkie and H. Fernau. The Boisdale Algorithm - an induction method for a subclass of unification grammar from positive data. In: International Colloquium on Grammatical Inference ICGI'04. vol. 3264 of LNCS/LNAI, pp. 235-247. Berlin: © Springer-Verlag, 2004.
2005
H. Fernau. Two-Layer Planarization: Improving on Parameterized Algorithmics. In: SOFSEM 2005, vol. 3381 of LNCS, pp. ??-?? Berlin: © Springer-Verlag, 2005.
J. Chen, H. Fernau, I.A. Kanj and G. Xia. Parametric Duality: Kernel Sizes & Algorithmics. In: STACS 2005, vol. 3??? of LNCS, pp. ??-?? Berlin: © Springer-Verlag, 2005.
Some slides of recent talks
V. Dujmovic, H. Fernau and M. Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited. Given at: Graph Drawing. Perugia, September 2003.
H. Fernau. Formal language aspects of identifiable language classes. In: 13ter GI Theorietag Automaten und Formale Sprachen, pages 27-34. Herrsching, October 2003.
H. Bordihn and H. Fernau. On the degree of parallelism. In: 13ter GI Theorietag Automaten und Formale Sprachen, pages 19-26. Herrsching, October 2003.
H. Fernau (with J. Ryan und K. Sugeng). Graph labelling: a view from Mars. Invited talk at: Australasian Workshop on Graph Labellings (AWOGL). Newcastle, October 2003.
H. Fernau. Learning XML Document Type Descriptors. Given at: Telstra Research Labs, Melbourne, November 2003. A similar talk has been given at the Motrare Workshop on Tree Languages, Lille, December 2003.
H. Fernau. Kleine Kerne und klassische Komplexität OR Parametric Duality: Kernel Sizes & Algorithmics. Given at: 50. Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen, München, March 2004.
H. Fernau. A Top-Down Approach to Search-Trees. Given at: Upper Rhine Algorithms Workshop URAW 2004, Karlsruhe, March 2004.
H. Fernau. Extracting minimum length Document Type Definitions is NP-hard. Given at: 14. Theorietag Automaten und Formale Sprachen 2004, Caputh, September 2004.
Manuscripts
H. Fernau, K.-J. Lange and R. Niedermeier. A remark on parameterized parallel complexity. Unpublished Remark, Universit�t T�bingen, Wilhelm-Schickard-Institut f�r Informatik, March 1997. Refer also to: Parameterized parallel complexity. ECCC TR97-006.

One page back

There seems to be no part of (so-called pure) mathematics that is not in immediate danger of being applied. (Michiel Hazewinkel in the series editor's preface of Bl. Sendov: Hausdorff approximations, Kluwer 1990.)

Henning Fernau

Last modified: Fri Nov 19 10:01:38 MET 2004

external visitors since March 19, 1997