Leiden University - Leiden Institute of Advanced Computer Science (LIACS)

Publications of Joost Engelfriet

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

Found 165 items. Searchstring `Engelfriet'