Joost Engelfriet

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.

[BibT_eX]

[DOI]

Helmut Seidl

J. Comput. Syst. Sci., 2009

Extended multi bottom-up tree transducers.

[BibT_eX]

[DOI]

Eric Lilin

Andreas Maletti

Acta Informatica, 2009

The time complexity of typechecking tree-walking tree transducers.

[BibT_eX]

[DOI]

Acta Informatica, 2009

2007

Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2007

An exercise in structural congruence.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

A Kleene characterization of computability.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

Finitary Compositions of Two-way Finite-State Transductions.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2007

XML transformation by tree-walking transducers with invisible pebbles.

[BibT_eX]

[DOI]

Bart Samwel

Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

2006

Clique-Width for 4-Vertex Forbidden Subgraphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

The equivalence problem for deterministic MSO tree transducers is decidable.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

Nested Pebbles and Transitive Closure.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

2005

Clique-Width for Four-Vertex Forbidden Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

Branching synchronization grammars with nested tables.

[BibT_eX]

[DOI]

Frank Drewes

J. Comput. Syst. Sci., 2004

A new natural structural congruence in the pi-calculus with replication.

[BibT_eX]

[DOI]

Acta Informatica, 2004

2003

Macro Tree Translations of Linear Size Increase are MSO Definable.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

A comparison of pebble tree transducers with macro tree transducers.

[BibT_eX]

[DOI]

Acta Informatica, 2003

Branching Grammars: A Generalization of ET0L Systems.

[BibT_eX]

[DOI]

Frank Drewes

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

2002

Output String Languages of Compositions of Deterministic Macro Tree Transducers.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Bottom-Up and Top-Down Tree Series Transformations.

[BibT_eX]

[DOI]

Zoltán Fülöp

J. Autom. Lang. Comb., 2002

Two-Way Finite State Transducers with Nested Pebbles.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

The Delta Operation: From Strings to Trees to Strings.

[BibT_eX]

[DOI]

Proceedings of the Formal and Natural Computing, 2002

2001

MSO definable string transductions and two-way finite-state transducers.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2001

Structural inclusion in the pi-calculus with replication.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Hierarchies of String Languages Generated by Deterministic Tree Transducers.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Roderick Bloem

J. Comput. Syst. Sci., 2000

Characterizing and Deciding MSO-Definability of Macro Tree Transductions.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

1999

Multisets and Structural Congruence of the pi-Calculus with Replication.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1999

Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations.

[BibT_eX]

[DOI]

Inf. Comput., 1999

Derivation Trees of Ground Term Rewriting Systems.

[BibT_eX]

[DOI]

Inf. Comput., 1999

Trips on Trees.

[BibT_eX]

[DOI]

Jan-Pascal van Best

Acta Cybern., 1999

Two-Way Finite State Transducers and Monadic Second-Order Logic.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

Tree-Walking Pebble Automata.

[BibT_eX]

Proceedings of the Jewels are Forever, 1999

1998

The Equivalence of Bottom-Up and Top-Down Tree-to-Graph Transducers.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Decidability of the Finiteness of Ranges of Tree Transductions.

[BibT_eX]

[DOI]

Frank Drewes

Inf. Comput., 1998

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

[BibT_eX]

[DOI]

Acta Informatica, 1998

Tree Languages Generated be Context-Free Graph Grammars.

[BibT_eX]

[DOI]

Proceedings of the Theory and Application of Graph Transformations, 1998

1997

Context-Free Graph Grammars.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Formal Languages, Volume 3: Beyond Words., 1997

Logical Description of Contex-Free Graph Languages.

[BibT_eX]

[DOI]

Vincent van Oostrom

J. Comput. Syst. Sci., 1997

Domino Treewidth.

[BibT_eX]

[DOI]

Hans L. Bodlaender

J. Algorithms, 1997

Context-Free Graph Grammars and Concatenation of Graphs.

[BibT_eX]

[DOI]

Jan Joris Vereijken

Acta Informatica, 1997

Node Replacement Graph Grammars.

[BibT_eX]

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

Monadic Second Order Logic and Node Relations on Graphs and Trees.

[BibT_eX]

[DOI]

Roderick Bloem

Proceedings of the Structures in Logic and Computer Science, 1997

1996

Characterization and Complexity of Uniformly Non Primitive Labeled 2-Structures.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

A Multiset Semantics for the pi-Calculus with Replication.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Regular Description of Context-Free Graph Languages.

[BibT_eX]

[DOI]

Vincent van Oostrom

J. Comput. Syst. Sci., 1996

Finite Languages for the Representation of Finite Graphs.

[BibT_eX]

[DOI]

Andrzej Ehrenfeucht

J. Comput. Syst. Sci., 1996

Reverse Twin Shuffles.

[BibT_eX]

Bull. EATCS, 1996

Elementary Net Systems.

[BibT_eX]

[DOI]

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.

[BibT_eX]

Math. Syst. Theory, 1995

Grammatical Codes of Trees and Terminally Coded Grammars.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1995

1994

The Translation Power of Top-Down Tree-to-Graph Transducers.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

Hypergraph Languages of Bounded Degree.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

Context-Free Graph Languages of Bounded Degree are Generated by Apex Graph Grammars.

[BibT_eX]

[DOI]

Acta Informatica, 1994

Domino Treewith (Extended Abstract).

[BibT_eX]

[DOI]

Hans L. Bodlaender

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Concatenation of Graphs.

[BibT_eX]

[DOI]

Jan Joris Vereijken

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

Graph Grammars and Tree Transducers.

[BibT_eX]

[DOI]

Proceedings of the Trees in Algebra and Programming, 1994

Deciding the NTS Property of Context-Free Grammars.

[BibT_eX]

[DOI]

Proceedings of the Results and Trends in Theoretical Computer Science, 1994

1993

X-Automata on omega-Words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

Handle-Rewriting Hypergraph Grammars.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1993

1992

An Elementary Proof of Double Greibach Normal Form.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

Context-Free Hypergraph Grammars have the Same Term-Generating Power as Attribute Grammars.

[BibT_eX]

[DOI]

Acta Informatica, 1992

A Greibach Normal Form for Context-free Graph Grammars.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991

Iterated Stack Automata and Complexity Classes

[BibT_eX]

[DOI]

Inf. Comput., November, 1991

Modular Tree Transducers.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

Nonterminal Separation in Graph Grammars.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

A Regular Characterization of Graph Languages Definable in Monadic Second-Order Logic.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

The String Generating Power of Context-Free Hypergraph Grammars.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

Branching Processes of Petri Nets.

[BibT_eX]

[DOI]

Acta Informatica, 1991

1990

A Comparison of Boundary Graph Grammars and Context-Free Hypergraph Grammars

[BibT_eX]

[DOI]

Inf. Comput., February, 1990

Boundary Graph Grammars with Dynamic Edge Relabeling.

[BibT_eX]

[DOI]

Emo Welzl

J. Comput. Syst. Sci., 1990

The Complexity of Regular DNLC Graph Languages.

[BibT_eX]

[DOI]

IJsbrand Jan Aalbersberg

J. Comput. Syst. Sci., 1990

Complexity of boundary graph languages.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1990

Attribute Storage Optimization by Stacks.

[BibT_eX]

[DOI]

Willem de Jong

Acta Informatica, 1990

Net-Based Description Of Parallel Object-Based Systems, or POTs and POPs.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Object-Oriented Languages, 1990

Graph Grammars Based on Node Rewriting: An Introduction to NLC Graph Grammars.

[BibT_eX]

[DOI]

Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

The Term Generating Power of Context-Free Hypergraph Grammars.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

Context-free Handle-rewriting Hypergraph Grammars.

[BibT_eX]

[DOI]

Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

1989

Linear Graph Grammars: Power and Complexity

[BibT_eX]

[DOI]

Inf. Comput., April, 1989

The Power to Two-Way Deterministic Checking Stack Automata

[BibT_eX]

[DOI]

Inf. Comput., February, 1989

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

[BibT_eX]

[DOI]

SIGACT News, 1989

Passes, sweeps, and visits in attribute grammars.

[BibT_eX]

[DOI]

J. ACM, 1989

Automata with Storage on Infinite Words.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Context-Free NCE Graph Grammars.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1989

1988

Nonterminal Bounded NLC Graph Grammars.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1988

Prefix and Equality Languages of Rational Functions are Co-Context-Free.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

High Level Tree Transducers and Iterated Pushdown Tree Transducers.

[BibT_eX]

[DOI]

Acta Informatica, 1988

Apex Graph Grammars and Attribute Grammars.

[BibT_eX]

[DOI]

Acta Informatica, 1988

1987

Look-Ahead on Pushdowns

[BibT_eX]

[DOI]

Inf. Comput., June, 1987

1986

<i>Corrigenda: </i> Pushdown Machines for the Macro Tree Tranducer.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

Pushdown Machines for the Macro Tree Transducer.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

The complexity of Languages Generated by Attribute Grammars.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

Apex Graph Grammars.

[BibT_eX]

[DOI]

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

Restricting the complexity of regular DNLC languages.

[BibT_eX]

[DOI]

IJsbrand Jan Aalbersberg

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

1985

Determinacy - (Observation Equivalence = Trace Equivalence).

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1985

Macro Tree Transducers.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

Hierarchies of Hyper-AFLs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

The non-computability of computability.

[BibT_eX]

Bull. EATCS, 1985

Characterization of High Level Tree Transducers.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1985

1984

Extended Macro Grammars and Stack Controlled Machines.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1984

Regular Characterizations of Macro Tree Transducers.

[BibT_eX]

Proceedings of the CAAP'84, 1984

1983

Context Free Normal Systems and ETOL Systems.

[BibT_eX]

[DOI]

Andrzej Ehrenfeucht

J. Comput. Syst. Sci., 1983

Iterated Pushdown Automata and Complexity Classes

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Attribute Grammars: Attribute Evaluation Methods.

[BibT_eX]

Proceedings of the Method and tools for compiler construction, 1983

1982

Three Hierarchies of Transducers.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1982

The Copying Power of One-State Tree Transducers.

[BibT_eX]

[DOI]

Sven Skyum

J. Comput. Syst. Sci., 1982

Simple Multi-Visit Attribute Grammars.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1982

1981

A Tranlsational Theorem for the Class of EOL Languages

[BibT_eX]

[DOI]

Inf. Control., August, 1981

Passes and Paths of Attributive Grammars

[BibT_eX]

[DOI]

Inf. Control., May, 1981

The Formal Power of One-Visit Attribute Grammars.

[BibT_eX]

[DOI]

Acta Informatica, 1981

Passes, Sweeps and Visits.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1981

1980

Tree Transducers, L Systems, and Two-Way Machines.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1980

Stack Machines and Classes of Nonnested Macro Languages.

[BibT_eX]

[DOI]

Erik Meineche Schmidt

Jan van Leeuwen

J. ACM, 1980

Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages.

[BibT_eX]

[DOI]

J. ACM, 1980

Formal Properties of One-Visit and Multi-Pass Attribute Grammars.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1980

1979

Equality Languages and Fixed Point Languages

[BibT_eX]

[DOI]

Inf. Control., October, 1979

Bounded Nesting in Macro Grammars

[BibT_eX]

[DOI]

Inf. Control., August, 1979

Extended Linear Macro Grammars, Iteration Grammars, and Register Programs.

[BibT_eX]

[DOI]

Peter R. J. Asveld

Acta Informatica, 1979

1978

IO and OI. II.

[BibT_eX]

[DOI]

Erik Meineche Schmidt

J. Comput. Syst. Sci., 1978

On Tree Transducers for Partial Functions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1978

Tree Transducers, L Systems and Two-Way Machines (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

Equality Languages, Fixed Point Languages and Representations of Recursively Enumerable Languages

[BibT_eX]

[DOI]

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977

Iterating Iterated Substitution.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1977

Top-down Tree Transducers with Regular Look-ahead.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1977

IO and OI. I.

[BibT_eX]

[DOI]

Erik Meineche Schmidt

J. Comput. Syst. Sci., 1977

Iterated Deterministic Substitution.

[BibT_eX]

[DOI]

Peter R. J. Asveld

Acta Informatica, 1977

Macro Grammars, Lindenmayer Systems and Other Copying Devices.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1977

1976

Surface Tree Languages and Parallel Derivation Trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1976

Copying Theorems.

[BibT_eX]

[DOI]

Sven Skyum

Inf. Process. Lett., 1976

1975

Bottom-up and Top-down Tree Transformations - A Comparison.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1975

1974

Simple Program Schemes and Formal Languages

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 20, Springer, ISBN: 3-540-06953-4, 1974

1972

A Note on Infinite Trees.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1972

Translation of Simple Program Schemes.

[BibT_eX]