Joost Engelfriet at the DBLP Bibliography Server

J. Engelfriet.

Computability by monadic second-order logic.
Information Processing Letters 167 (2021) 106074.
doi:10.1016/j.ipl.2020.106074

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.
doi:10.1016/j.tcs.2020.10.030
arXiv: 1809.05730 .

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.
doi:10.1007/s00236-019-00360-8

J. Engelfriet, H. Vogler.

A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage.
Discrete Mathematics & Theoretical Computer Science 22 (2020).
doi:10.23638/DMTCS-22-4-3

J. Engelfriet.

Corrigendum to "Iterated stack automata and complexity classes".
Information and Computation 267 (2019) 164-167.
doi:https://doi.org/10.1016/j.ic.2019.05.003

J. Engelfriet, A. Maletti, S. Maneth.

Multiple context-free tree grammars: Lexicalization and characterization.
Theoretical Computer Science 728 (2018) 29-99.
doi:10.1016/j.tcs.2018.03.014

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.
doi:10.1016/j.jcss.2016.11.001

J. Engelfriet.

The Trees of Hanoi.
Slightly revised version of Memorandum Nr. 325, Department of Applied Mathematics, Twente University of Technology, January 1981, 2017.
arXiv: 1710.04551 .

J. Engelfriet, A. Maletti, S. Maneth.

Multiple Context-Free Tree Grammars: Lexicalization and Characterization.
2017.
arXiv: 1707.03457 .

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.
doi:10.1007/s00224-015-9660-2

J. Engelfriet.

Erratum to: "Top-down Tree Transducers with Regular Look-ahead".
Theory of Computing Systems 58 (2016) 377-379.
doi:10.1007/s00224-015-9647-z

J. Engelfriet, S. Maneth, H. Seidl.

Look-ahead removal for total deterministic top-down tree transducers.
Theoretical Computer Science 616 (2016) 18-58.
doi:10.1016/j.tcs.2015.12.005

H. Seidl, S. Maneth, G. Kemper, J. Engelfriet.

Equivalence - Combinatorics, algebra, proofs.
In: Dependable Software Systems Engineering (J. Esparza, O. Grumberg, S. Sickert, eds.), NATO Science for Peace and Security Series - D: Information and Communication Security, v. 45, IOS Press, 202-243, 2016.
online .

F. Drewes, J. Engelfriet.

The generative power of delegation networks.
Information and Computation 245 (2015) 213-258.
doi:10.1016/j.tcs.2015.12.005

F. Drewes, J. Engelfriet.

Context-free tree grammars are as powerful as context-free jungle grammars.
Acta Cybernetica 22 (2015) 373-392.
doi:10.1007/s00236-015-0224-3
open access .

J. Engelfriet.

Two-way pebble transducers for partial functions and their composition.
Acta Informatica 52 (2015) 559-571.
doi:10.1007/s00236-015-0224-3
open access .

J. Engelfriet.

Tree automata and tree grammars.
Revised version of Lecture Notes DAIMI FN-10, Department of Computer Science, Aarhus University, Denmark, April 1975, 2015.
arXiv: 1510.02036 .

J. Engelfriet.

Context-free grammars with storage.
Revised version of Report 86-11, Department of Computer Science, University of Leiden, July 1986, 2014.
arXiv: 1408.0683 .

J. Engelfriet, S. Maneth, H. Seidl.

How to remove the look-ahead of top-down tree transducers.
In: Developments in Language Theory 2014 (DLT 2014) (A.M. Shur, M.V. Volkov, eds.), Lecture Notes in Computer Science, v. 8633, Springer-Verlag, 103-115, 2014.
doi:10.1007/978-3-319-09698-8_10

M. Benedikt, J. Engelfriet, S. Maneth.

Determinacy and rewriting of top-down and MSO tree transformations.
Mathematical Foundations of Computer Science 2013 (MFCS 2013). Lecture Notes in Computer Science 8087 (2013) 146-158.

B. Courcelle, J. Engelfriet.

Graph Structure and Monadic Second-Order Logic - A language-theoretic approach. Encyclopedia of Mathematics and its Applications, volume 138, Cambridge University Press, 2012.

F. Drewes, J. Engelfriet.

The generative power of delegation networks.
Report UMINF 12.15, 2012.
pdf .

A. Maletti, J. Engelfriet.

Strong lexicalization of tree adjoining grammars.
In: Proceedings 50th annual meeting of the Association for Computational Linguistics (ACL 2012), v. 1, 506-515, 2012.
www.aclweb.org/anthology/P12-1053 (pdf) .

J. Engelfriet.

The time complexity of typechecking tree-walking tree transducers.
Acta Informatica 46 (2009) 139-154.
doi:10.1007/s00236-008-0087-y

J. Engelfriet, E. Lilin, A. Maletti.

Extended multi bottom-up tree transducers -- Composition and decomposition.
Acta Informatica 46 (2009) 561-590.
doi:10.1007/s00236-009-0105-8

J. Engelfriet, S. Maneth, H. Seidl.

Deciding equivalence of top-down XML transformations in polynomial time.
Journal of Computer and System Sciences 75 (2009) 271-286.
doi:10.1016/j.jcss.2009.01.001

J. Engelfriet.

The complexity of typechecking tree-walking tree transducers.
LIACS Technical Report 2008-01, January 2008.
ps-file .

J. Engelfriet, E. Lilin, A. Maletti.

Extended Multi Bottom-Up Tree Transducers.
In: Developments in Language Theory, 12th International Conference, DLT 2008, Kyoto, Japan (M. Ito, M. Toyama, eds.), Lecture Notes in Computer Science, v. 5257, 2008.
doi:10.1007/978-3-540-85780-8

J. Engelfriet.

A Kleene characterization of computability.
Information Processing Letters 101 (2007) 139-140.
doi:10.1016/j.ipl.2006.09.003

J. Engelfriet, T. Gelsema.

An exercise in structural congruence.
Information Processing Letters 101 (2007) 1-5.
doi:10.1016/j.ipl.2006.08.001

J. Engelfriet, H.J. Hoogeboom.

Automata with nested pebbles capture first-order logic with transitive closure.
Logical Methods in Computer Science 3(2:3) (2007) 1-27.
doi:10.2168/LMCS-3(2:3)2007
presented at STACS 2006 . MathSciNet .

J. Engelfriet, H.J. Hoogeboom.

Finitary Compositions of Two-way Finite-State Transductions.
Fundamenta Informaticae 80 (2007) 111-123.

J. Engelfriet, H.J. Hoogeboom, B. Samwel.

XML Transformation by Tree-Walking Transducers with Invisible Pebbles.
In: Proceedings of the twenty-sixth ACM Symposium on Principles of Database Systems, PODS 2007 (L. Libkin, ed.), ACM Press, 63-72, 2007.
doi:10.1145/1265530.1265540
best newcomer award . author version .

A. Brandstädt, J. Engelfriet, H.-O. Le, V.V. Lozin.

Clique-width for 4-vertex forbidden subgraphs.
Theory of Computing Systems 39 (2006) 561-590.
doi:10.1007/s00224-005-1199-1

J. Engelfriet, H.J. Hoogeboom.

Nested Pebbles and Transitive Closure.
In: STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science (B. Durand, W. Thomas, eds.), Lecture Notes in Computer Science, v. 3884, 477-488, 2006.
doi:10.1007/11672142_39
Full paper published in 2007 .

J. Engelfriet, S. Maneth.

The equivalence problem for deterministic MSO tree transducers is decidable.
Information Processing Letters 100 (2006) 206-212.
doi:10.1016/j.ipl.2006.05.015

A. Brandstädt, J. Engelfriet, H.-O. Le, V.V. Lozin.

Clique-width for four-vertex forbidden subgraphs.
In: Fundamentals of Computation Theory, FCT 2005 (M. Liskiewicz, R. Reischuk, eds.), Lecture Notes in Computer Science, v. 3623, 185-196, 2005.
doi:10.1007/11537311_17

J. Engelfriet, S. Maneth.

The equivalence problem for deterministic MSO tree transducers is decidable.
In: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science (R. Ramanujam, S. Sen, eds.), Lecture Notes in Computer Science, v. 3821, 495-504, 2005.
doi:10.1007/11590156_40
Published in 2006 (IPL) . cs.LO/0506014 .

F. Drewes, J. Engelfriet.

Branching synchronization grammars with nested tables.
Journal of Computer and System Sciences 68 (2004) 611-656.
doi:10.1016/j.jcss.2003.10.001
ps-file .

J. Engelfriet, Tj. Gelsema.

A new natural structural congruence in the pi-calculus with replication.
Acta Informatica 40 (2004) 385-430.
doi:10.1007/s00236-004-0141-3

J. Engelfriet, Tj. Gelsema.

The decidability of structural congruence for replication restricted pi-calculus processes.
LIACS Technical Report 2004-07, May 2004.

H.J. Hoogeboom, J. Engelfriet.

Pushdown Automata.
In: Formal Languages and Applications (C. Martín-Vide, V. Mitrana, G. Paun, eds.), Studies in Fuzziness and Soft Computing, v. 148, Springer, Berlin, 117-138, 2004.
pdf-file . google books .

F. Drewes, J. Engelfriet.

Branching grammars: a generalization of ET0L systems.
In: Proc. Developments in Language Theory, DLT 2003 (Z. Ésik, Z. Fülöp, eds.), Lecture Notes in Computer Science, v. 2710, Springer-Verlag, 266-278, 2003.
doi:10.1007/3-540-45007-6_21

J. Engelfriet, S. Maneth.

Macro tree translations of linear size increase are MSO definable.
SIAM Journal on Computing 32 (2003) 950-1006.
doi:10.1137/S0097539701394511
technical report (2001) . MathSciNet .

J. Engelfriet, S. Maneth.

A comparison of pebble tree transducers with macro tree transducers.
Acta Informatica 39 (2003) 613 - 698.
doi:10.1007/s00236-003-0120-0
MathSciNet .

J. Engelfriet.

The Delta Operation: From Strings to Trees to Strings.
In: Formal and Natural Computing - Essays Dedicated to Grzegorz Rozenberg (W. Brauer, H. Ehrig, J. Karhumäki, A. Salomaa, eds.), Lecture Notes in Computer Science, v. 2300, Springer Verlag, 39-56, 2002.
doi:10.1007/3-540-45711-9_3

J. Engelfriet, Z. Fülöp, H. Vogler.

Bottom-Up and Top-Down Tree Series Transformations.
Journal of Automata, Languages and Combinatorics 7 (2002) 11-70.
MathSciNet .

J. Engelfriet, S. Maneth.

Output String Languages of Compositions of Deterministic Macro Tree Transducers.
Journal of Computer and System Sciences 64 (2002) 350-395.
doi:10.1006/jcss.2001.1816
technical report . MathSciNet .

J. Engelfriet, S. Maneth.

Two-way finite state transducers with nested pebbles.
In: Proceedings MFCS'02 (K. Diks, W. Rytter, eds.), Lecture Notes in Computer Science, v. 2420, 234-244, 2002.
doi:10.1007/3-540-45687-2_19

J. Engelfriet, S. Maneth.

Hierarchies of String Languages Generated by Deterministic Tree Transducers.
In: Developments in Language Theory, DLT 2001 (W. Kuich, G. Rozenberg, A. Salomaa, eds.), Lecture Notes in Computer Science, v. 2295, 228-238, 2002.
MathSciNet .

J. Engelfriet, Tj. Gelsema.

Structural Inclusion in the pi-Calculus with Replication.
Theoretical Computer Science 258 (2001) 131-168.
doi:10.1016/S0304-3975(99)00330-8
MathSciNet .

J. Engelfriet, H.J. Hoogeboom.

MSO Definable String Transductions and Two-Way Finite State Transducers.
ACM Transactions on Computational Logic 2 (2001) 216-254.
doi:10.1145/371316.371512
arXiv:cs/9906007 . MathSciNet .

R. Bloem, J. Engelfriet.

A comparison of tree transductions defined by monadic second order logic and by attribute grammars.
Journal of Computer and System Sciences 61 (2000) 1-50.
doi:10.1006/jcss.1999.1684
technical report . MathSciNet .

J. Engelfriet, S. Maneth.

Tree Languages Generated by Context-Free Graph Grammars.
In: Theory and Applications of Graph Transformations , 6th International Workshop, TAGT'98 (H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 1764, Springer Verlag, 15-29, 2000.

J. Engelfriet, S. Maneth.

Characterizing and Deciding MSO-definability of Macro Tree Transductions.
In: Theoretical Aspects of Computer Science, 17th International Symposium, STACS'2000 (H. Reichel, S. Tison, eds.), Lecture Notes in Computer Science, v. 1770, Springer Verlag, 542-554, 2000.
doi:10.1007/3-540-46541-3_45
full paper (as TR) .

J. Engelfriet.

Derivation trees of ground term rewriting systems.
Information and Computation 152 (1999) 1-15.
doi:10.1006/inco.1998.2786 10.1006/inco.1998.2786
technical report . MathSciNet .

J. Engelfriet, Tj. Gelsema.

Multisets and Structural Congruence of the pi-Calculus with Replication.
Theoretical Computer Science 211 (1999) 311-337.
doi:10.1016/S0304-3975(97)00179-5
technical report . MathSciNet .

J. Engelfriet, H.J. Hoogeboom.

Tree-walking pebble automata.
In: Jewels are forever, contributions to Theoretical Computer Science in honor of Arto Salomaa (J. Karhumäki, H. Maurer, G. Paun, G. Rozenberg, eds.), Springer Verlag, 72-83, 1999.

J. Engelfriet, H.J. Hoogeboom.

Two-way finite state transducers and monadic second-order logic.
In: Automata, Languages and Programming, 26th International Colloquium, ICALP'99 (J. Wiedermann, P. van Emde Boas, M. Nielsen, eds.), Lecture Notes in Computer Science, v. 1644, Springer Verlag, 311-320, 1999.
doi:10.1007/3-540-48523-6_28
Full paper in ACMToCL 2001 .

J. Engelfriet, H.J. Hoogeboom, J.-P. van Best.

Trips on Trees.
Acta Cybernetica 14 (1999) 51-64.
Acta Cybernetica .

J. Engelfriet, S. Maneth.

Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations.
Information and Computation 154 (1999) 34-91.
doi:10.1006/inco.1999.2807
technical report . MathSciNet .

F. Drewes, J. Engelfriet.

Decidability of the finiteness of ranges of tree transductions.
Information and Computation 145 (1998) 1-50.
doi:10.1006/inco.1998.2715

J. Engelfriet, Tj. Gelsema.

Axioms for Generalized Graphs, Illustrated by a Cantor-Bernstein Proposition.
Acta Informatica 35 (1998) 1075-1096.
doi:10.1007/s002360050152
technical report .

J. Engelfriet, H. Vogler.

The Equivalence of Bottom-Up and Top-Down Tree-to-Graph Transducers.
Journal of Computer and System Sciences 56 (June 1998) 332-356.
doi:10.1006/jcss.1998.1573
MathSciNet .

G. Rozenberg, J. Engelfriet.

Elementary Net Systems.
In: Lectures on Petri Nets I: Basic Models (W. Reisig, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 1491, Springer-Verlag, 12-121, 1998.

R. Bloem, J. Engelfriet.

Monadic Second Order Logic and Node Relations on Graphs and Trees.
In: Structures in Logic and Computer Science (J. Mycielski, G. Rozenberg, A. Salomaa, eds.), Lecture Notes in Computer Science, v. 1261, Springer-Verlag, 144-161, 1997.
doi:10.1007/3-540-63246-8_9
MathSciNet .

R. Bloem, J. Engelfriet.

Characterization of Properties and Relations Defined in Monadic Second Order Logic on the Nodes of Trees.
Leiden University Technical Report 97-03, August 1997.

H.L. Bodlaender, J. Engelfriet.

Domino Treewidth.
Journal of Algorithms 24 (July 1997) 94-123.
doi:10.1006/jagm.1996.0854

J. Engelfriet.

Context-Free Graph Grammars.
In: Handbook of Formal Languages, Volume 3: Beyond Words (G. Rozenberg, A. Salomaa, eds.), Springer-Verlag, 125-213, 1997.
MathSciNet .

J. Engelfriet, V. van Oostrom.

Logical description of context-free graph-languages.
Journal of Computer and System Sciences 55 (1997) 489-503.
doi:10.1006/jcss.1997.1510
technical report . MathSciNet .

J. Engelfriet, G. Rozenberg.

Node Replacement Graph Grammars.
In: Handbook of Graph Grammars and Computing by Graph Transformation, Volume 1: Foundations (G. Rozenberg, ed.), World Scientific, 1-94, 1997.

J. Engelfriet, J.-J. Vereijken.

Context-free graph grammars and concatenation of graphs.
Acta Informatica 34 (1997) 773-803.
doi:10.1007/s002360050106

A. Ehrenfeucht, J. Engelfriet, G. Rozenberg.

Finite languages for the representation of finite graphs.
Journal of Computer and System Sciences 52 (1996) 170-184.
doi:10.1006/jcss.1996.0013

J. Engelfriet.

A multiset semantics for the pi-calculus with replication.
Theoretical Computer Science 153 (1996) 65-94.
doi:10.1016/0304-3975(95)00118-2
MathSciNet .

J. Engelfriet.

Reverse twin shuffles.
Bulletin of the EATCS 60 (1996) 144.
revised version .

J. Engelfriet, T. Harju, A. Proskurowski, G. Rozenberg.

Characterization and complexity of uniformly nonprimitive labeled 2-structures.
Theoretical Computer Science 154 (1996) 247-282.
doi:10.1016/0304-3975(94)00272-X
MathSciNet .

J. Engelfriet, V. van Oostrom.

Regular description of context-free graph languages.
Journal of Computer and System Sciences 53 (1996) 556-574.
doi:10.1006/jcss.1996.0087

J. Engelfriet, J.J. Vereijken.

Concatenation of graphs.
In: Graph Grammars and their Application to Computer Science (J. Cuny, H. Ehrig, G. Engels, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 1073, 368-382, 1996.
Journal paper in 1997 .

H.L. Bodlaender, J. Engelfriet.

Domino treewidth.
In: Proc. Graph Theoretic Concepts in Computer Science WG'94 (E. W.Mayr, G. Schmidt, G. Tinhofer, eds.), Lecture Notes in Computer Science, v. 903, 1-13, 1995.
Journal paper in 1997 .

B. Courcelle, J. Engelfriet.

A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars.
Mathematical Systems Theory 28 (1995) 515-552.

A. Ehrenfeucht, J. Engelfriet, P. ten Pas, G. Rozenberg.

Grammatical Codes of Trees and Terminally Coded Grammars.
Fundamenta Informaticae 23 (1995) 1-33.
MathSciNet .

J. Engelfriet.

Deciding the NTS Property of Context-Free Grammars.
In: Results and Trends in Theoretical Computer Science (J. Karhumäki, H. Maurer, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 812, 124-130, 1994.
technical report .

J. Engelfriet.

Graph Grammars and Tree Transducers.
In: Proceedings CAAP'94 (S. Tison, ed.), Lecture Notes in Computer Science, v. 787, 15-36, 1994.
technical report . MathSciNet .

J. Engelfriet, L.M. Heyker.

Hypergraph Languages of Bounded Degree.
Journal of Computer and System Sciences 48 (1994) 58-89.
doi:10.1016/S0022-0000(05)80022-4
MathSciNet .

J. Engelfriet, L.M. Heyker, G. Leih.

Context-free Graph Languages of Bounded Degree are generated by Apex Graph Grammars.
Acta Informatica 31 (1994) 341-378.
doi:10.1007/BF01178511
MathSciNet .

J. Engelfriet, H. Vogler.

The Translation Power of Top-Down Tree-To-Graph Transducers.
Journal of Computer and System Sciences 49 (1994) 258-305.
doi:10.1016/S0022-0000(05)80050-9
MathSciNet .

B. Courcelle, J. Engelfriet, G. Rozenberg.

Handle-rewriting hypergraph grammars.
Journal of Computer and System Sciences 46 (1993) 218-270.
doi:10.1016/0022-0000(93)90004-G
MathSciNet .

J. Engelfriet.

A multiset semantics for the pi-calculus with replication.
In: CONCUR'93 (E. Best, ed.), Lecture Notes in Computer Science, v. 715, Springer-Verlag, Berlin, 7-21, 1993.
Journal paper in 1996 . technical report . MathSciNet .

J. Engelfriet, H.J. Hoogeboom.

X-automata on omega-words.
Theoretical Computer Science 110 (1993) 1-51.
doi:10.1016/0304-3975(93)90349-X
MathSciNet .

J. Engelfriet.

A Greibach normal form for context-free graph grammars.
In: Automata, Languages, and Programming (W. Kuich, ed.), Lecture Notes in Computer Science, v. 623, 138-149, 1992.

J. Engelfriet.

An elementary proof of Double Greibach Normal Form.
Information Processing Letters 44 (1992) 291-293.

J. Engelfriet, L.M. Heyker.

Context-free hypergraph grammars have the same term-generating power as attribute grammars.
Acta Informatica 29 (1992) 161-210.
doi:10.1007/BF01178504

B. Courcelle, J. Engelfriet, G. Rozenberg.

Context-free handle-rewriting hypergraph grammars.
In: Graph-Grammars and their Application to Computer Science (H. Ehrig, H.-J. Kreowski, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 532, Springer-Verlag, Berlin, 253-268, 1991.
doi:10.1007/BFb0017394
Journal paper in 1993 .

J. Engelfriet.

A regular characterization of graph languages definable in monadic second-order logic.
Theoretical Computer Science 88 (1991) 139-150.
doi:10.1016/0304-3975(91)90078-G

J. Engelfriet.

Branching processes of Petri nets.
Acta Informatica 28 (1991) 575-591.
doi:10.1007/BF01463946

J. Engelfriet.

A characterization of context-free NCE graph languages by monadic second-order logic on trees.
In: Graph-Grammars and their Application to Computer Science (H. Ehrig, H.-J. Kreowski, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 532, Springer-Verlag, Berlin, 311-327, 1991.
doi:10.1007/BFb0017397

J. Engelfriet.

Iterated stack automata and complexity classes.
Information and Computation 95 (1991) 21-75.
doi:10.1016/0890-5401(91)90015-T

J. Engelfriet, L.M. Heyker.

The string generating power of context-free hypergraph grammars.
Journal of Computer and System Sciences 43 (1991) 328-360.
doi:10.1016/0022-0000(91)90018-Z

J. Engelfriet, L.M. Heyker.

The term generating power of context-free hypergraph grammars.
In: Graph-Grammars and their Application to Computer Science (H. Ehrig, H.-J. Kreowski, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 532, Springer-Verlag, Berlin, 328-343, 1991.
doi:10.1007/BFb0017398
Journal paper in 1992 .

J. Engelfriet, G. Leih, G. Rozenberg.

Net-based description of parallel object-based systems, or POTs and POPs.
In: Foundations of Object-Oriented Languages (J.W.de Bakker, W.P.de Roever, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 489, Springer-Verlag, Berlin, 229-273, 1991.
doi:10.1007/BFb0019446

J. Engelfriet, G. Leih, G. Rozenberg.

Nonterminal separation in graph grammars.
Theoretical Computer Science 82 (1991) 95-111.

J. Engelfriet, G. Rozenberg.

Graph grammars based on node rewriting: an introduction to NLC graph grammars.
In: Graph-Grammars and their Application to Computer Science (H. Ehrig, H.-J. Kreowski, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 532, Springer-Verlag, Berlin, 12-23, 1991.
doi:10.1007/BFb0017374

J. Engelfriet, H. Vogler.

Modular tree transducers (fundamental study).
Theoretical Computer Science 78 (1991) 267-303.

IJ.J. Aalbersberg, J. Engelfriet, G. Rozenberg.

The complexity of regular DNLC graph languages.
Journal of Computer and System Sciences 40 (1990) 376-404.
doi:10.1016/0022-0000(90)90004-5

J. Engelfriet, W.A. de Jong.

Attribute storage optimization by stacks.
Acta Informatica 27 (1990) 567-581.
doi:10.1007/BF00277390

J. Engelfriet, G. Leih.

Complexity of boundary graph languages.
R.A.I.R.O. -- Informatique Théorique et Applications 24 (1990) 267-274.

J. Engelfriet, G. Leih, G. Rozenberg.

Formalizing the behaviour of parallel object-based systems by Petri nets.
In: Semantics for concurrency (M.Z. Kwiatkowska, M.W. Shields, R.M. Thomas, eds.), Workshops on Computing, Springer-Verlag, Berlin, 204-221, 1990.

J. Engelfriet, G. Leih, E. Welzl.

Boundary graph grammars with dynamic edge relabeling.
Journal of Computer and System Sciences 40 (1990) 307-345.
doi:10.1016/0022-0000(90)90002-3

J. Engelfriet, G. Rozenberg.

A comparison of boundary graph grammars and context-free hypergraph grammars.
Information and Computation 84 (1990) 163-206.
doi:10.1016/0890-5401(90)90038-J

J. Engelfriet.

The power of two way deterministic checking stack automata.
Information and Computation 80 (1989) 114-120.
doi:10.1016/0890-5401(89)90015-1

J. Engelfriet.

Context-free NCE graph grammars.
In: FCT'89 (J. Csirik, J. Demetrovics, F. Gecseg, eds.), Lecture Notes in Computer Science, v. 380, 148-161, 1989.
doi:10.1007/3-540-51498-8_15

J. Engelfriet.

The complexity of the circularity problem for attribute grammars: a note on a counterexample for a simpler construction.
SIGACT News (Summer 1989) 57-59.

J. Engelfriet, G. File.

Passes, sweeps, and visits in attribute grammars.
Journal of the ACM 36 (1989) 841-869.
doi:10.1145/76359.76366

J. Engelfriet, H.J. Hoogeboom.

Automata with storage on infinite words.
In: Automata, Languages and Programming (G. Ausiello, M. Dezani-Ciancaglini, S. Ronchi Della Rocca, eds.), Lecture Notes in Computer Science, v. 372, 289-303, 1989.
doi:10.1007/BFb0035767
Journal paper in 1993 .

J. Engelfriet, G. Leih.

Linear graph grammars: power and complexity.
Information and Computation 81 (1989) 88-121.
doi:10.1016/0890-5401(89)90030-8

J. Engelfriet, H.J. Hoogeboom.

Prefix and equality languages of rational functions are co-context-free.
Information Processing Letters 28 (1988) 77-79.
doi:10.1016/0020-0190(88)90167-6
MathSciNet .

J. Engelfriet, G. Leih.

Nonterminal bounded NLC graph grammars.
Theoretical Computer Science 59 (1988) 309-315.

J. Engelfriet, G. Leih, G. Rozenberg.

Apex graph grammars and attribute grammars.
Acta Informatica 25 (1988) 537-571.
doi:10.1007/BF00279953

J. Engelfriet, H. Vogler.

High level tree transducers and iterated pushdown machines.
Acta Informatica 26 (1988) 131-192.

IJ.J. Aalbersberg, J. Engelfriet, G. Rozenberg.

Restricting the complexity of regular DNLC languages.
In: Graph-grammars and their Application to Computer Science (H. Ehrig, M. Nagl, G. Rozenberg, A. Rosenfeld, eds.), Lecture Notes in Computer Science, v. 291, Springer Verlag, 147-166, 1987.
doi:10.1007/3-540-18771-5_51

J. Engelfriet.

Generating strings with hypergraph grammars.
In: Essays on concepts, formalisms, and tools (dedicated to Leo Verbeek) (P.R.J. Asveld, A. Nijholt, eds.), CWI Tract, v. 42, 43-58, 1987.

J. Engelfriet, G. Leih, G. Rozenberg.

Apex graph grammars.
In: Graph-grammars and their Application to Computer Science (H. Ehrig, M. Nagl, G. Rozenberg, A. Rosenfeld, eds.), Lecture Notes in Computer Science, v. 291, Springer Verlag, 167-185, 1987.
doi:10.1007/3-540-18771-5_52

J. Engelfriet, H. Vogler.

Look-ahead on pushdowns.
Information and Computation 73 (1987) 245-279.

J. Engelfriet.

Context-free grammars with storage.
Leiden University Technical Report I86-11, 1986.

J. Engelfriet.

The complexity of languages generated by attribute grammars.
SIAM Journal on Computing 15 (1986) 70-86.

J. Engelfriet.

The ETOL hierarchy is in the OI hierarchy..
In: The Book of L (G. Rozenberg, A. Salomaa, eds.), Springer-Verlag, Berlin, 101-109, 1986.

J. Engelfriet, H. Vogler.

Pushdown machines for the macro tree transducer.
Theoretical Computer Science 42 (1986) 251-368.
doi:10.1016/0304-3975(86)90052-6

J. Engelfriet, H. Vogler.

Pushdown machines for the macro tree transducer (corrigenda).
Theoretical Computer Science 48 (1986) 339.
doi:10.1016/0304-3975(86)90102-7

J. Engelfriet.

The non-computability of computability.
Bulletin of the EATCS 26 (1985) 36-39.

J. Engelfriet.

Hierarchies of hyper-AFLs.
Journal of Computer and System Sciences 30 (1985) 86-115.
doi:10.1016/0022-0000(85)90006-6

J. Engelfriet.

Determinacy implies (observation equivalence = trace equivalence).
Theoretical Computer Science 36 (1985) 21-25.
doi:10.1016/0304-3975(85)90028-3

J. Engelfriet, H. Vogler.

Macro tree transducers.
Journal of Computer and System Sciences 31 (1985) 71-146.
doi:10.1016/0022-0000(85)90066-2

J. Engelfriet, H. Vogler.

Characterization of high level tree transducers.
In: Automata, Languages and Programming, 12th Colloquium (W. Brauer, ed.), Lecture Notes in Computer Science, v. 194, 171-178, 1985.
doi:10.1007/BFb0015742

J. Engelfriet.

Attribute grammars: attribute evaluation methods.
In: Methods and Tools for Compiler Construction (B. Lorho, ed.), Cambridge University Press, 103-138, 1984.

J. Engelfriet, G. Slutzki.

Extended macro grammars and stack controlled machines.
Journal of Computer and System Sciences 29 (1984) 366-408.
doi:10.1016/0022-0000(84)90006-0

J. Engelfriet, H. Vogler.

Regular characterizations of macro tree transducers.
In: Ninth colloquium on Trees in Algebra and Programming (B. Courcelle, ed.), Cambridge University Press, 103-117, 1984.

A. Ehrenfeucht, J. Engelfriet, G. Rozenberg.

Context-free normal systems and ETOL systems.
Journal of Computer and System Sciences 26 (1983) 34-46.
doi:10.1016/0022-0000(83)90019-3

P.R.J. Asveld, J. Engelfriet.

A note on non-generators of full AFL's.
International Journal of Computer Mathematics 2 (1982) 13-17.
doi:10.1080/00207168208803322

J. Engelfriet.

Three hierarchies of transducers.
Mathematical Systems Theory 15 (1982) 95-125.
doi:10.1007/BF01786975

J. Engelfriet, G. File.

Simple multi-visit attribute grammars.
Journal of Computer and System Sciences 24 (1982) 283-314.
doi:10.1016/0022-0000(82)90030-7

J. Engelfriet, S. Skyum.

The copying power of one-state tree transducers..
Journal of Computer and System Sciences 25 (1982) 418-435.
doi:10.1016/0022-0000(82)90019-8

J. Engelfriet.

The Trees of Hanoi.
TW-Memorandum 325, Twente University of Technology, January 1981, not submitted.

J. Engelfriet, G. File.

The formal power of one-visit attribute grammars.
Acta Informatica 16 (1981) 275-302.
doi:10.1007/BF00289307

J. Engelfriet, G. File.

Passes and paths of attribute grammars.
Information and Control 49 (1981) 125-169.
doi:10.1016/S0019-9958(81)90466-6

J. Engelfriet, G. Rozenberg.

A translational theorem for the class of EOL languages.
Information and Control 50 (1981) 175-183.
doi:10.1016/S0019-9958(81)90198-4

J. Engelfriet.

Some open questions and recent results on tree transducers and tree languages.
In: Formal language theory: perspectives and open problems (R.V. Book, ed.), Academic Press, New York, 241-286, 1980.

J. Engelfriet, J. van Leeuwen, E.M. Schmidt.

Stack machines and classes of nonnested macro languages.
Journal of the ACM 27 (1980) 96-117.
doi:10.1145/322169.322178

J. Engelfriet, G. Rozenberg.

Fixed point languages, equality languages and representation of recursively enumerable languages.
Journal of the ACM 27 (1980) 499-518.
doi:10.1145/322203.322211

J. Engelfriet, G. Rozenberg, G. Slutzki.

Tree transducers, L systems and two-way machines.
Journal of Computer and System Sciences 20 (1980) 150-202.
doi:10.1016/0022-0000(80)90058-6

P.R.J. Asveld, J. Engelfriet.

Extended linear macro grammars, iteration grammars, and register programs.
Acta Informatica 11 (1979) 259-285.
doi:10.1007/BF00289071

J. Engelfriet, G. Rozenberg.

Equality languages and fixed point languages.
Information and Control 43 (1979) 20-49.
doi:10.1016/S0019-9958(79)90082-2

J. Engelfriet, G. Slutzki.

Bounded nesting in macro grammars.
Information and Control 42 (1979) 157-193.
doi:10.1016/S0019-9958(79)90635-1

J. Engelfriet.

Two-way automata and checking automata.
In: 3rd Advanced Course on Foundations of Computer Science (J.W. de Bakker, J. van Leeuwen, eds.), Mathematical Centre Tract, v. 108, 3-70, 1978.

J. Engelfriet.

On tree transducers for partial functions.
Information Processing Letters 7 (1978) 170-172.
doi:doi:10.1016/0020-0190(78)90060-1

J. Engelfriet, E.M. Schmidt.

IO and OI (2).
Journal of Computer and System Sciences 16 (1978) 67-99.
doi:10.1016/0022-0000(78)90051-X

P.R.J. Asveld, J. Engelfriet.

Iterated deterministic substitution.
Acta Informatica 8 (1977) 285-302.
doi:10.1007/BF00264471

J. Engelfriet.

Top-down tree transducers with regular look-ahead.
Mathematical Systems Theory 10 (1977) 289-303.
doi:10.1007/BF01683280

J. Engelfriet.

Iterating iterated substitution.
Theoretical Computer Science 5 (1977) 85-100.
doi:10.1016/0304-3975(77)90043-3

J. Engelfriet, E.M. Schmidt.

IO and OI (1).
Journal of Computer and System Sciences 15 (1977) 328-353.
doi:10.1016/S0022-0000(77)80034-2

J. Engelfriet.

Surface tree languages and parallel derivation trees.
Theoretical Computer Science 2 (1976) 9-27.
doi:10.1016/0304-3975(76)90003-7

J. Engelfriet, S. Skyum.

Copying theorems.
Information Processing Letters 4 (1976) 157-161.
doi:10.1016/0020-0190(76)90086-7

J. Engelfriet.

Tree automata and tree grammars.
DAIMI FN-10 (Lecture Notes), Aarhus University, April 1975.

J. Engelfriet.

Bottom-up and top-down tree transformations - a comparison.
Mathematical Systems Theory 9 (1975) 198-231.
doi:10.1007/BF01704020

J. Engelfriet.

Simple program schemes and formal languages. Lecture Notes in Computer Science, volume 20, Springer-Verlag, 1974.
doi:10.1007/3-540-06953-4

J. Engelfriet.

A note on infinite trees.
Information Processing Letters 1 (1972) 229-232.
doi:10.1016/0020-0190(72)90017-8