Joost Engelfriet
Associate professor / guest
- Name
- Dr. J. Engelfriet
- Telephone
- +31 71 527 4799
- j.engelfriet@liacs.leidenuniv.nl
Links
Associate professor / guest
- Science
- Leiden Inst of Advanced Computer Science
- Engelfriet J. (2021), Computability by monadic second-order logic, Information Processing Letters 167: 106074.
- Engelfriet J., Inaba K. & Maneth S. (2021), Linear bounded composition of tree-walking tree transducers: linear size increase and complexity, Acta Informatica 58: 95-152.
- Engelfriet J., Hoogeboom H.J. & Samwel B. (2021), XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles, Theoretical Computer Science 850: 40-97.
- Engelfriet J. Vogler H. (2020), A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage, Discrete Mathematics & Theoretical Computer Science 22(4): 3.
- Engelfriet J. (2019), Corrigendum to "Iterated stack automata and complexity classes" [Inf. Comput. 95 (1) (1991) 21–75], Information and Computation 267: 164-167.
- Engelfriet J., Maletti A. & Maneth S. (2018), Multiple context-free tree grammars: lexicalization and characterization, Theoretical Computer Science 728: 29-99.
- Engelfriet J. (2017), The Trees of Hanoi (revised version). CoRR abs/1710.04551.
- Engelfriet J. & Maletti A. (2017), Multiple context-free tree grammars and multi-component tree adjoining grammars. Klasing R. & Zeitoun M. (Eds.), Fundamentals of Computation Theory. FCT 2017. 21st International Symposium on Fundamentals of Computation Theory (FCT2017) 11 September 2017 - 13 September 2017 no. LNCS 10472. Berlin, Heidelberg: Springer. 217-229.
- Engelfriet J., Fülöp Z. & Maletti A. (2017), Composition closure of linear extended top-down tree transducers, Theory of Computing Systems 60(2): 129-171.
- Benedikt M., Engelfriet J. & Maneth S. (2017), Determinacy and rewriting of functional top–down and MSO tree transformations, Journal of Computer and System Sciences 85: 57-73.
- Engelfriet J., Maneth S. & Seidl H. (2016), Look-ahead removal for total deterministic top-down tree transducers, Theoretical Computer Science 616: 18-58.
- Engelfriet J. (2016), Erratum to: "Top-down Tree Transducers with Regular Look-ahead", Theory of Computing Systems 58(2): 377-379.
- Seidl H., Maneth S., Kemper G. & Engelfriet J. (2016), Equivalence - Combinatorics, Algebra, Proofs. In: Esparza J., Grumberg O. & Sickert S. (Eds.), Dependable Software Systems Engineering. NATO Science for Peace and Security Series - D: Information and Communication Security no. 45. Amsterdam, The Netherlands: IOS Press. 202-243.
- Engelfriet J. (2015), Tree automata and tree grammars (revised version). CoRR abs/1510.02036 no. CoRR abs/1510.02036.
- Drewes F. & Engelfriet J. (2015), Context-free tree grammars are as powerful as context-free jungle grammars, Acta Cybernetica 22: 373-392.
- Engelfriet J. (2015), Two-way pebble transducers for partial functions and their composition, Acta Informatica 52(7-8): 559-571.
- Drewes F. & Engelfriet J. (2015), The generative power of delegation networks, Information and Computation 245: 213-258.
- Engelfriet J., Maneth S. & Seidl H. (2014), How to remove the look-ahead of top-down tree transducers. Shur A.M. & Volkov M.V. (Eds.), Proceedings 18th International Conference on Developments in Language Theory 2014 (DLT 2014). Developments in Language Theory no. Lecture Notes in Computer Science 8633: Springer-Verlag. 103-115.
- Engelfriet J. (2014), Context-free grammars with storage (revised version). CoRR abs/1408.0683.
- Engelfriet J., Maneth S. & Seidl H. (2013), Look-Ahead removal for top-down tree transducers.
- Benedikt M., Engelfriet J. & Maneth S. (2013), Determinacy and Rewriting of Top-Down and MSO Tree Transformations, Proceedings 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013). no. LNCS 8087: Springer-Verlag. 146-158.
- Courcelle B. & Engelfriet J. (2012), Graph Structure and Monadic Second-Order Logic - A language-theoretic approach. Cambridge: Cambridge University Press.
- Maletti A. & Engelfriet J. (2012), Strong lexicalization of tree adjoining grammars, Proceedings 50th annual meeting of the Association for Computational Linguistics (ACL 2012). 506-515.
- Engelfriet J. & Drewes F. (2012), The generative power of delegation networks: Umea University, Sweden.
- Engelfriet J., Lilin E. & Maletti A. (2009), Extended multi bottom-up tree transducers -- Composition and decomposition, Acta Informatica 46: 561-590.
- Engelfriet J., Maneth S. & Seidl H. (2009), Deciding equivalence of top-down XML transformations in polynomial time, Journal of Comp. Syst. Sci. 75: 271-286.
- Engelfriet J. (2009), The time complexity of typechecking tree-walking tree transducers, Acta Informatica 46: 139-154.
- Engelfriet J., Lilin E. & Maletti A. (2008), Extended Multi Bottom-Up Tree Transducers. In: , Developments in Language Theory. Berlin / Heidelberg: Springer. 289-300.
- Engelfriet J. (2008), The complexity of typechecking tree-walking tree transducers, LIACS Technical Report 2008-01: .
- Engelfriet J., Lilin E. & Maletti A. (2008), Extended Multi Bottom-Up Tree Transducers. Ito M. & Toyama M. (Eds.), Developments in Language Theory. 12th International Conference, DLT 2008: Springer Verlag. 289-300.
- Engelfriet J. & Hoogeboom H.J. (2007), Automata with nested pebbles capture first-order logic with transitive closure, Logical Methods in Computer Science 3(2-3): 1-27.
- Engelfriet J. & Hoogeboom H.J. (2007), Finitary Compositions of Two-way Finite-State Transductions, Fundamenta Informaticae 80: 111-113.
- Engelfriet J., Hoogeboom H.J. & Samwel H. (2007), XML Transformation by Tree-Walking Transducers with Invisible Pebbles. Libkin L. (Ed.), Proceedings of the twenty-sixth ACM Symposium on Principles of Database Systems, PODS 2007. : ACM Press. 63-72.
- Engelfriet J. (2007), A Kleene characterization of computability, Information Processing Letters 101: 139-140.
- Engelfriet J. & Gelsema Tj. (2007), An exercise in structural congruence, Information Processing Letters 101: 1-5.
- Engelfriet J. & Hoogeboom H.J. (2006), Nested Pebbles and Transitive Closure. Durand B. & Thomas W. (Eds.), STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science. : Springer Verlag. 477-488.
- Engelfriet J. & Maneth S. (2006), The equivalence problem for deterministic MSO tree transducers is decidable, Information Processing Letters 100: 206-212.
- Brandstädt A., Engelfriet J., Le H.-O. & Lozin V.V. (2006), Clique-width for 4-vertex forbidden subgraphs, Theory of Computing Systems 39: 561-590.
- Brandstädt A., Engelfriet J., Le H.-O. & Lozin V.V. (2005), Clique-width for four-vertex forbidden subgraphs, Fundamentals of Computation Theory, FCT 2005. 185-196.
- Engelfriet J. & Maneth S. (2005), The equivalence problem for deterministic MSO tree tranducers is decidable. Ramanujam R. & Sen S. (Eds.), Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2005). 495-504.
- Hoogeboom H.J. & Engelfriet J. (2004), Pushdown Automata. In: Martín-Vide C., Mitrana V. & Paun G. (Eds.), Formal Languages and Applications. Studies in Fuzziness and Soft Computing no. 148. Berlin: Springer. 117-138.
- Engelfriet J. & Maneth S. (2002), Two-way finite state transducers with nested pebbles. Diks K. & Rytter W. (Eds.), Proc. of the 27th International Symposium on Mathematical Foundations of Computer Science. 234-244.
- Engelfriet J. & Maneth S. (2002), Output String Languages of Compositions of Deterministic Macro Tree Transducers, Journal of Computer and System Sciences 64: 250-395.
- Engelfriet J. & Maneth S. (2002), Hierarchies of String Languages Generated by Deterministic Tree Transducers. Kuich W., Rozenberg G. & Salomaa A. (Eds.), Developments in Language Theory. 228-238.
- Engelfriet J. (2002), The Delta Operation: From Strings to Trees to Strings. In: Brauer W., Ehrig H., Karhumaki J. & Salomaa A. (Eds.), Formal and Natural Computing - Essays Dedicated to Grzegorz Rozenberg: Springer Verlag. 39-56.
- Bloem R. & Engelfriet J. (1998), A comparison of tree transductions defined by monadic second order logic and by attribute grammars. onbekend: LIACS.
- Drewes F. & Engelfriet J. (1998), Decidability of the finiteness of ranges of tree transductions, Information and Computation 145: 1-50.
- Engelfriet J. & Gelsema Tj. (1998), Structural Inclusion in the pi-Calculus with Replication. onbekend: LIACS.
- Engelfriet J. & Hoogeboom H.J. (1998), MSO Definable String Transductions and Two-Way Finite State Transducers. onbekend: LIACS.
- Engelfriet J. & Maneth S. (1998), Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations. onbekend: LIACS.
- Engelfriet J. & Vogler H. (1998), The Equivalence of Bottom-Up and Top-Down Tree-to-Graph Transducers, Journal of Computer and System Sciences 56: 332-356.
- Rozenberg G. & Engelfriet J. (1998), Elementary Net Systems. In: Reisig W. & Rozenberg G. (Eds.), Lectures on Petri Nets I: Basic Models. Heidelberg, Duitsland: Springer-Verlag. 12-121.
- Engelfriet J. & Gelsema Tj. (1998), Axioms for Generalized Graphs, Illustrated by a Cantor-Bernstein Proposition, Acta Informatica 35: 1075-1096.
- Engelfriet J. (1991), Iterated stack automata and complexity classes, Information and Computation 95(1): 21-75.