Joost Engelfriet

(retired)

Contact information

address:
Leiden Institute of Advanced Computer Science (LIACS)
Leiden University, P.O. Box 9512
2300 RA Leiden, The Netherlands

my oldest son: Joeri Engelfriet (his company and his publications)
my youngest son: Tako Engelfriet
my granddaughter: Laura
my grandson: Sam

Research: Former member of the Theory group
Onderwijs: Geen. Vroeger wel, bijvoorbeeld:: Logica voor Informatici; Formele Talen en Automaten 1

papers on pebbles

2021:

J. Engelfriet; Computability by monadic second-order logic, Information Processing Letters 167 (2021), 106074 online (open access)
J. Engelfriet, K. Inaba, S. Maneth; Linear bounded composition of tree-walking tree transducers: linear size increase and complexity, Acta Informatica 58 (2021), 95-152 online authorcopy
J. Engelfriet, H. J. Hoogeboom, B. Samwel; XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles, Theoretical Computer Science 850 (2021), 40-97 online authorcopy

2020:

J. Engelfriet; Computability by monadic second-order logic. Technical Report arXiv:2008.12151.
J. Engelfriet, H. Vogler; A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage. Discrete Mathematics and Theoretical Computer Science 22:4 (2020), #3 online (open access)

2019:

J. Engelfriet; Corrigendum to "Iterated stack automata and complexity classes", Information and Computation 267 (2019), 164-167 online authorcopy
J. Engelfriet, H. Vogler; A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage. Technical Report arXiv:1905.00559.
J. Engelfriet, K. Inaba, S. Maneth; Linear bounded composition of tree-walking tree transducers: linear size increase and complexity. Technical Report arXiv:1904.09203.

2018:

J. Engelfriet, H. J. Hoogeboom, B. Samwel; XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles. Technical Report arXiv:1809.05730.
J. Engelfriet, A. Maletti, S. Maneth; Multiple context-free tree grammars: lexicalization and characterization, Theoretical Computer Science 728 (2018), 29-99 online authorcopy

2017:

J. Engelfriet; The Trees of Hanoi arXiv:1710.04551. Revised version of Memorandum Nr. 325, Department of Applied Mathematics, Twente University of Technology, January 1981
J. Engelfriet, A. Maletti; Multiple context-free tree grammars and multi-component tree adjoining grammars, in: FCT 2017 (R. Klasing and M. Zeitoun, editors), Lecture Notes in Computer Science 10472, Springer-Verlag, 2017, pp.217-229 online authorcopy
J. Engelfriet, A. Maletti, S. Maneth; Multiple context-free tree grammars: lexicalization and characterization. Technical Report arXiv:1707.03457.
M. Benedikt, J.Engelfriet, S. Maneth; Determinacy and rewriting of functional top-down and MSO tree transformations, Journal of Computer and System Sciences 85 (2017), 57-73 online authorcopy
J. Engelfriet, Z. Fülöp, A. Maletti; Composition closure of linear extended top-down tree transducers, Theory of Computing Systems 60 (2017), 129-171 online authorcopy sharedcopy

2016:

J. Engelfriet, S. Maneth, H. Seidl; Look-ahead removal for total deterministic top-down tree transducers, Theoretical Computer Science 616 (2016), 18-58 online authorcopy
J. Engelfriet; Erratum to: "Top-down Tree Transducers with Regular Look-ahead", Theory of Computing Systems 58 (2016), 377-397 online authorcopy
H. Seidl, S. Maneth, G. Kemper, J. Engelfriet; Equivalence - Combinatorics, algebra, proofs, in: Dependable Software Systems Engineering (J. Esparza, O. Grumberg, and S. Sickert, editors), Volume 45 of NATO Science for Peace and Security Series - D: Information and Communication Security, IOS Press, 2016, pages 202-243 online

2015:

J. Engelfriet; Two-way pebble transducers for partial functions and their composition, Acta Informatica 52 (2015), 559-571 online (open access)
F. Drewes, J. Engelfriet; The generative power of delegation networks, Information and Computation 245 (2015), 213-258 online authorcopy
F. Drewes, J. Engelfriet; Context-free tree grammars are as powerful as context-free jungle grammars, Acta Cybernetica 22 (2015), 373-392 online (open access)
J. Engelfriet; Tree automata and tree grammars arXiv:1510.02036. Revised version of Lecture Notes DAIMI FN-10, Department of Computer Science, Aarhus University, Denmark, April 1975

2014:

J. Engelfriet; Context-free grammars with storage arXiv:1408.0683. Revised version of Report 86-11, Department of Computer Science, University of Leiden, July 1986
J. Engelfriet, S. Maneth, H. Seidl; How to remove the look-ahead of top-down tree transducers, in: DLT 2014 (A.M. Shur and M.V. Volkov, editors), Lecture Notes in Computer Science 8633, Springer-Verlag, 2014, pp.103-115 online authorcopy

2013:

M. Benedikt, J. Engelfriet, S. Maneth; Determinacy and rewriting of top-down and MSO tree transformations, in: MFCS 2013 (K. Chatterjee and J. Sgall, editors), Lecture Notes in Computer Science 8087, Springer-Verlag, 2013, pp.146-158 online authorcopy

2012:

Book:
B. Courcelle, J. Engelfriet; Graph Structure and Monadic Second-Order Logic, a Language-Theoretic Approach;
Encyclopedia of Mathematics and its Applications, vol. 138, Cambridge University Press, June 2012 (728 pages)
book-website
A. Maletti, J. Engelfriet; Strong lexicalization of tree adjoining grammars, Proc. 50th Annual Meeting Association for Computational Linguistics (ACL 2012), pages 506-515, 2012 online, slides
F. Drewes, J. Engelfriet; The generative power of delegation networks, Report UMINF 12.15, Umeå University, 2012 pdf-file.