Joost Engelfriet

Affiliations:
  • Leiden Institute of Advanced Computer Science, Netherlands


According to our database1, Joost Engelfriet authored at least 157 papers between 1972 and 2021.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles.
Theor. Comput. Sci., 2021

Computability by monadic second-order logic.
Inf. Process. Lett., 2021

Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity.
Acta Informatica, 2021

2020
A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage.
Discret. Math. Theor. Comput. Sci., 2020

2019
Corrigendum to "Iterated stack automata and complexity classes" [Inf. Comput. 95 (1) (1991) 21-75].
Inf. Comput., 2019

2018
Multiple context-free tree grammars: Lexicalization and characterization.
Theor. Comput. Sci., 2018

2017
Composition Closure of Linear Extended Top-down Tree Transducers.
Theory Comput. Syst., 2017

Determinacy and rewriting of functional top-down and MSO tree transformations.
J. Comput. Syst. Sci., 2017

The Trees of Hanoi.
CoRR, 2017

Multiple Context-Free Tree Grammars and Multi-component Tree Adjoining Grammars.
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016
Equivalence - Combinatorics, Algebra, Proofs.
Proceedings of the Dependable Software Systems Engineering, 2016

Look-ahead removal for total deterministic top-down tree transducers.
Theor. Comput. Sci., 2016

Erratum to: "Top-down Tree Transducers with Regular Look-ahead".
Theory Comput. Syst., 2016

2015
The generative power of delegation networks.
Inf. Comput., 2015

Tree Automata and Tree Grammars.
CoRR, 2015

Context-Free Tree Grammars are as Powerful as Context-Free Jungle Grammars.
Acta Cybern., 2015

Two-way pebble transducers for partial functions and their composition.
Acta Informatica, 2015

2014
Context-Free Grammars with Storage.
CoRR, 2014

How to Remove the Look-Ahead of Top-Down Tree Transducers.
Proceedings of the Developments in Language Theory - 18th International Conference, 2014

2013
Look-Ahead Removal for Top-Down Tree Transducers.
CoRR, 2013

Determinacy and Rewriting of Top-Down and MSO Tree Transformations.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

2012
Book: Graph Structure and Monadic Second-Order Logic. A Language-Theoretic Approach.
Bull. EATCS, 2012

Strong Lexicalization of Tree Adjoining Grammars.
Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, July 8-14, 2012, Jeju Island, Korea, 2012

Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach.
Encyclopedia of mathematics and its applications 138, Cambridge University Press, ISBN: 978-0-521-89833-1, 2012

2009
Deciding equivalence of top-down XML transformations in polynomial time.
J. Comput. Syst. Sci., 2009

Extended multi bottom-up tree transducers.
Acta Informatica, 2009

The time complexity of typechecking tree-walking tree transducers.
Acta Informatica, 2009

2007
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure.
Log. Methods Comput. Sci., 2007

An exercise in structural congruence.
Inf. Process. Lett., 2007

A Kleene characterization of computability.
Inf. Process. Lett., 2007

Finitary Compositions of Two-way Finite-State Transductions.
Fundam. Informaticae, 2007

XML transformation by tree-walking transducers with invisible pebbles.
Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

2006
Clique-Width for 4-Vertex Forbidden Subgraphs.
Theory Comput. Syst., 2006

The equivalence problem for deterministic MSO tree transducers is decidable.
Inf. Process. Lett., 2006

Nested Pebbles and Transitive Closure.
Proceedings of the STACS 2006, 2006

2005
Clique-Width for Four-Vertex Forbidden Subgraphs.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004
Branching synchronization grammars with nested tables.
J. Comput. Syst. Sci., 2004

A new natural structural congruence in the pi-calculus with replication.
Acta Informatica, 2004

2003
Macro Tree Translations of Linear Size Increase are MSO Definable.
SIAM J. Comput., 2003

A comparison of pebble tree transducers with macro tree transducers.
Acta Informatica, 2003

Branching Grammars: A Generalization of ET0L Systems.
Proceedings of the Developments in Language Theory, 7th International Conference, 2003

2002
Output String Languages of Compositions of Deterministic Macro Tree Transducers.
J. Comput. Syst. Sci., 2002

Bottom-Up and Top-Down Tree Series Transformations.
J. Autom. Lang. Comb., 2002

Two-Way Finite State Transducers with Nested Pebbles.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

The Delta Operation: From Strings to Trees to Strings.
Proceedings of the Formal and Natural Computing, 2002

2001
MSO definable string transductions and two-way finite-state transducers.
ACM Trans. Comput. Log., 2001

Structural inclusion in the pi-calculus with replication.
Theor. Comput. Sci., 2001

Hierarchies of String Languages Generated by Deterministic Tree Transducers.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000
A Comparison of Tree Transductions Defined by Monadic Second Order Logic and by Attribute Grammars.
J. Comput. Syst. Sci., 2000

Characterizing and Deciding MSO-Definability of Macro Tree Transductions.
Proceedings of the STACS 2000, 2000

1999
Multisets and Structural Congruence of the pi-Calculus with Replication.
Theor. Comput. Sci., 1999

Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations.
Inf. Comput., 1999

Derivation Trees of Ground Term Rewriting Systems.
Inf. Comput., 1999

Trips on Trees.
Acta Cybern., 1999

Two-Way Finite State Transducers and Monadic Second-Order Logic.
Proceedings of the Automata, 1999

Tree-Walking Pebble Automata.
Proceedings of the Jewels are Forever, 1999

1998
The Equivalence of Bottom-Up and Top-Down Tree-to-Graph Transducers.
J. Comput. Syst. Sci., 1998

Decidability of the Finiteness of Ranges of Tree Transductions.
Inf. Comput., 1998

Axioms for Generalized Graphs, Illustrated by a Cantor-Bernstein Proposition.
Acta Informatica, 1998

Tree Languages Generated be Context-Free Graph Grammars.
Proceedings of the Theory and Application of Graph Transformations, 1998

1997
Context-Free Graph Grammars.
Proceedings of the Handbook of Formal Languages, Volume 3: Beyond Words., 1997

Logical Description of Contex-Free Graph Languages.
J. Comput. Syst. Sci., 1997

Domino Treewidth.
J. Algorithms, 1997

Context-Free Graph Grammars and Concatenation of Graphs.
Acta Informatica, 1997

Node Replacement Graph Grammars.
Proceedings of the Handbook of Graph Grammars and Computing by Graph Transformations, 1997

Monadic Second Order Logic and Node Relations on Graphs and Trees.
Proceedings of the Structures in Logic and Computer Science, 1997

1996
Characterization and Complexity of Uniformly Non Primitive Labeled 2-Structures.
Theor. Comput. Sci., 1996

A Multiset Semantics for the pi-Calculus with Replication.
Theor. Comput. Sci., 1996

Regular Description of Context-Free Graph Languages.
J. Comput. Syst. Sci., 1996

Finite Languages for the Representation of Finite Graphs.
J. Comput. Syst. Sci., 1996

Reverse Twin Shuffles.
Bull. EATCS, 1996

Elementary Net Systems.
Proceedings of the Lectures on Petri Nets I: Basic Models, 1996

1995
A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars.
Math. Syst. Theory, 1995

Grammatical Codes of Trees and Terminally Coded Grammars.
Fundam. Informaticae, 1995

1994
The Translation Power of Top-Down Tree-to-Graph Transducers.
J. Comput. Syst. Sci., 1994

Hypergraph Languages of Bounded Degree.
J. Comput. Syst. Sci., 1994

Context-Free Graph Languages of Bounded Degree are Generated by Apex Graph Grammars.
Acta Informatica, 1994

Domino Treewith (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Concatenation of Graphs.
Proceedings of the Graph Gramars and Their Application to Computer Science, 1994

Graph Grammars and Tree Transducers.
Proceedings of the Trees in Algebra and Programming, 1994

Deciding the NTS Property of Context-Free Grammars.
Proceedings of the Results and Trends in Theoretical Computer Science, 1994

1993
X-Automata on omega-Words.
Theor. Comput. Sci., 1993

Handle-Rewriting Hypergraph Grammars.
J. Comput. Syst. Sci., 1993

1992
An Elementary Proof of Double Greibach Normal Form.
Inf. Process. Lett., 1992

Context-Free Hypergraph Grammars have the Same Term-Generating Power as Attribute Grammars.
Acta Informatica, 1992

A Greibach Normal Form for Context-free Graph Grammars.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991
Iterated Stack Automata and Complexity Classes
Inf. Comput., November, 1991

Modular Tree Transducers.
Theor. Comput. Sci., 1991

Nonterminal Separation in Graph Grammars.
Theor. Comput. Sci., 1991

A Regular Characterization of Graph Languages Definable in Monadic Second-Order Logic.
Theor. Comput. Sci., 1991

The String Generating Power of Context-Free Hypergraph Grammars.
J. Comput. Syst. Sci., 1991

Branching Processes of Petri Nets.
Acta Informatica, 1991

1990
A Comparison of Boundary Graph Grammars and Context-Free Hypergraph Grammars
Inf. Comput., February, 1990

Boundary Graph Grammars with Dynamic Edge Relabeling.
J. Comput. Syst. Sci., 1990

The Complexity of Regular DNLC Graph Languages.
J. Comput. Syst. Sci., 1990

Complexity of boundary graph languages.
RAIRO Theor. Informatics Appl., 1990

Attribute Storage Optimization by Stacks.
Acta Informatica, 1990

Net-Based Description Of Parallel Object-Based Systems, or POTs and POPs.
Proceedings of the Foundations of Object-Oriented Languages, 1990

Graph Grammars Based on Node Rewriting: An Introduction to NLC Graph Grammars.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

The Term Generating Power of Context-Free Hypergraph Grammars.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

A Characterization of Context-Free NCE Graph Languages by Monadic Second-Order Logic on Trees.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

Context-free Handle-rewriting Hypergraph Grammars.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

1989
Linear Graph Grammars: Power and Complexity
Inf. Comput., April, 1989

The Power to Two-Way Deterministic Checking Stack Automata
Inf. Comput., February, 1989

The complexity of the circularity problem for attribute grammars: a note on a counterexample for a simpler construction.
SIGACT News, 1989

Passes, sweeps, and visits in attribute grammars.
J. ACM, 1989

Automata with Storage on Infinite Words.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Context-Free NCE Graph Grammars.
Proceedings of the Fundamentals of Computation Theory, 1989

1988
Nonterminal Bounded NLC Graph Grammars.
Theor. Comput. Sci., 1988

Prefix and Equality Languages of Rational Functions are Co-Context-Free.
Inf. Process. Lett., 1988

High Level Tree Transducers and Iterated Pushdown Tree Transducers.
Acta Informatica, 1988

Apex Graph Grammars and Attribute Grammars.
Acta Informatica, 1988

1987
Look-Ahead on Pushdowns
Inf. Comput., June, 1987

1986
<i>Corrigenda: </i> Pushdown Machines for the Macro Tree Tranducer.
Theor. Comput. Sci., 1986

Pushdown Machines for the Macro Tree Transducer.
Theor. Comput. Sci., 1986

The complexity of Languages Generated by Attribute Grammars.
SIAM J. Comput., 1986

Apex Graph Grammars.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1986

Restricting the complexity of regular DNLC languages.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1986

1985
Determinacy - (Observation Equivalence = Trace Equivalence).
Theor. Comput. Sci., 1985

Macro Tree Transducers.
J. Comput. Syst. Sci., 1985

Hierarchies of Hyper-AFLs.
J. Comput. Syst. Sci., 1985

The non-computability of computability.
Bull. EATCS, 1985

Characterization of High Level Tree Transducers.
Proceedings of the Automata, 1985

1984
Extended Macro Grammars and Stack Controlled Machines.
J. Comput. Syst. Sci., 1984

Regular Characterizations of Macro Tree Transducers.
Proceedings of the CAAP'84, 1984

1983
Context Free Normal Systems and ETOL Systems.
J. Comput. Syst. Sci., 1983

Iterated Pushdown Automata and Complexity Classes
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Attribute Grammars: Attribute Evaluation Methods.
Proceedings of the Method and tools for compiler construction, 1983

1982
Three Hierarchies of Transducers.
Math. Syst. Theory, 1982

The Copying Power of One-State Tree Transducers.
J. Comput. Syst. Sci., 1982

Simple Multi-Visit Attribute Grammars.
J. Comput. Syst. Sci., 1982

1981
A Tranlsational Theorem for the Class of EOL Languages
Inf. Control., August, 1981

Passes and Paths of Attributive Grammars
Inf. Control., May, 1981

The Formal Power of One-Visit Attribute Grammars.
Acta Informatica, 1981

Passes, Sweeps and Visits.
Proceedings of the Automata, 1981

1980
Tree Transducers, L Systems, and Two-Way Machines.
J. Comput. Syst. Sci., 1980

Stack Machines and Classes of Nonnested Macro Languages.
J. ACM, 1980

Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages.
J. ACM, 1980

Formal Properties of One-Visit and Multi-Pass Attribute Grammars.
Proceedings of the Automata, 1980

1979
Equality Languages and Fixed Point Languages
Inf. Control., October, 1979

Bounded Nesting in Macro Grammars
Inf. Control., August, 1979

Extended Linear Macro Grammars, Iteration Grammars, and Register Programs.
Acta Informatica, 1979

1978
IO and OI. II.
J. Comput. Syst. Sci., 1978

On Tree Transducers for Partial Functions.
Inf. Process. Lett., 1978

Tree Transducers, L Systems and Two-Way Machines (Extended Abstract)
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

Equality Languages, Fixed Point Languages and Representations of Recursively Enumerable Languages
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977
Iterating Iterated Substitution.
Theor. Comput. Sci., 1977

Top-down Tree Transducers with Regular Look-ahead.
Math. Syst. Theory, 1977

IO and OI. I.
J. Comput. Syst. Sci., 1977

Iterated Deterministic Substitution.
Acta Informatica, 1977

Macro Grammars, Lindenmayer Systems and Other Copying Devices.
Proceedings of the Automata, 1977

1976
Surface Tree Languages and Parallel Derivation Trees.
Theor. Comput. Sci., 1976

Copying Theorems.
Inf. Process. Lett., 1976

1975
Bottom-up and Top-down Tree Transformations - A Comparison.
Math. Syst. Theory, 1975

1974
Simple Program Schemes and Formal Languages
Lecture Notes in Computer Science 20, Springer, ISBN: 3-540-06953-4, 1974

1972
A Note on Infinite Trees.
Inf. Process. Lett., 1972

Translation of Simple Program Schemes.
Proceedings of the Automata, 1972


  Loading...