Arrow Research search

Author name cluster

Joost Engelfriet

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

TCS Journal 2021 Journal Article

XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles

  • Joost Engelfriet
  • Hendrik Jan Hoogeboom
  • Bart Samwel

The pebble tree automaton and the pebble tree transducer are enhanced by additionally allowing an unbounded number of “invisible” pebbles (as opposed to the usual “visible” ones). The resulting pebble tree automata recognize the regular tree languages (i. e. , can validate all generalized DTD's) and hence can find all matches of MSO definable patterns. Moreover, when viewed as a navigational device, they lead to an XPath-like formalism that has a path expression for every MSO definable binary pattern. The resulting pebble tree transducers can apply arbitrary MSO definable tests to (the observable part of) their configurations, they (still) have a decidable typechecking problem, and they can model the recursion mechanism of XSLT. The time complexity of the typechecking problem for conjunctive queries that use MSO definable patterns can often be reduced through the use of invisible pebbles.

Details DOI

TCS Journal 2018 Journal Article

Multiple context-free tree grammars: Lexicalization and characterization

  • Joost Engelfriet
  • Andreas Maletti
  • Sebastian Maneth

Multiple (simple) context-free tree grammars are investigated, where “simple” means “linear and nondeleting”. Every multiple context-free tree grammar that is finitely ambiguous can be lexicalized; i. e. , it can be transformed into an equivalent one (generating the same tree language) in which each rule of the grammar contains a lexical symbol. Due to this transformation, the rank of the nonterminals increases at most by 1, and the multiplicity (or fan-out) of the grammar increases at most by the maximal rank of the lexical symbols; in particular, the multiplicity does not increase when all lexical symbols have rank 0. Multiple context-free tree grammars have the same tree generating power as multi-component tree adjoining grammars (provided the latter can use a root-marker). Moreover, every multi-component tree adjoining grammar that is finitely ambiguous can be lexicalized. Multiple context-free tree grammars have the same string generating power as multiple context-free (string) grammars and polynomial time parsing algorithms. A tree language can be generated by a multiple context-free tree grammar if and only if it is the image of a regular tree language under a deterministic finite-copying macro tree transducer. Multiple context-free tree grammars can be used as a synchronous translation device.

Details DOI

TCS Journal 2016 Journal Article

Look-ahead removal for total deterministic top-down tree transducers

  • Joost Engelfriet
  • Sebastian Maneth
  • Helmut Seidl

Top-down tree transducers are a convenient formalism for describing tree transformations. They can be equipped with regular look-ahead, which allows them to inspect a subtree before processing it. In certain cases, such a look-ahead can be avoided and the transformation can be realized by a transducer without look-ahead. Removing the look-ahead from a transducer, if possible, is technically highly challenging. For a restricted class of transducers with look-ahead, namely those that are total, deterministic, ultralinear, and bounded erasing, we present an algorithm that, for a given transducer from that class, (1) decides whether it is equivalent to a total deterministic transducer without look-ahead, and (2) constructs such a transducer if the answer is positive. For the whole class of total deterministic transducers with look-ahead we present a similar algorithm, which assumes that a so-called difference bound is known for the given transducer. The designer of a transducer can usually also determine a difference bound for it.

Details DOI

MFCS Conference 2013 Conference Paper

Determinacy and Rewriting of Top-Down and MSO Tree Transformations

  • Michael Benedikt
  • Joost Engelfriet
  • Sebastian Maneth

Abstract A query is determined by a view, if the result to the query can be reconstructed from the result of the view. We consider the problem of deciding for two given tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable, even for identity queries. For a large class of non-copying views, namely compositions of functional extended linear top-down tree transducers with regular look-ahead, we show that determinacy is decidable, where queries are given by deterministic top-down tree transducers with regular look-ahead or by MSO tree transducers. We also show that if a query is determined, then it can be rewritten into a query that works directly over the view and is in the same class as the given query. The proof relies on the decidability of equivalence for the two considered classes of queries, and on their closure under composition.

Details

MFCS Conference 2002 Conference Paper

Two-Way Finite State Transducers with Nested Pebbles

  • Joost Engelfriet
  • Sebastian Maneth

Abstract Two-way finite state transducers are considered with a fixed number of pebbles, of which the life times are nested. In the deterministic case, the transductions computed by such pebble transducers are closed under composition, and they can be realized by the composition of one-pebble transducers. The ranges of the k -pebble transducers form a hierarchy with respect to k, their finiteness problem is decidable, and they can be generated by compositions of k macro tree transducers. Related results hold in the nondeterministic case.

Details

TCS Journal 2001 Journal Article

Structural inclusion in the pi-calculus with replication

  • Joost Engelfriet
  • Tjalling Gelsema

Three notions of structural inclusion between process terms of the π-calculus are considered, and proven to be decidable and to have axiomatizations that are sound and complete in the multiset semantics Mπ of the π-calculus. All three are strong simulation relations.

Details DOI

TCS Journal 1996 Journal Article

A multiset semantics for the pi-calculus with replication

  • Joost Engelfriet

A multiset (or Petri net) semantics is defined for the π-calculus with replication. The semantic mapping is a strong bisimulation, and structurally congruent processes have the same semantics. This paper is readable without knowledge of Petri nets.

Details DOI

TCS Journal 1993 Journal Article

X-automata on ω-words

  • Joost Engelfriet
  • Hendrik Jan Hoogeboom

For any storage type X, the ω-languages accepted by X-automata are investigated. Six accepting conditions (including those introduced by Landweber) are compared for X-automata. The inclusions between the corresponding six families of ω-languages are essentially the same as for finite-state automata. Apart from unrestricted automata, also real-time and deterministic automata are considered. The main tools for this investigation are: (1) a characterization of the ω-languages accepted by X-automata in terms of inverse X-transductions of finite-state ω-languages; and (2) the existence of topological upper bounds on some of the families of accepted ω-languages (independent of the storage type X).

Details DOI

TCS Journal 1991 Journal Article

Modular tree transducers

  • Joost Engelfriet
  • Heiko Vogler

A new tree transducer, called a modular tree transducer, is introduced. This device specifies operations on trees and can be considered as a formalization of the concept of nested simultaneous primitive recursion on trees. Roughly speaking, a modular tree transducer is a special left-linear and non-overlapping term rewriting system of which the set of rules is partitioned into modules, each module being equipped with a non-negative integer: the number of the module. Then, a module with number i may call modules with numbers not less than i. Three properties are proved: (1) modular tree transducers compute exactly the (inductively defined) class of primitive recursive functions on trees; (2) the number of modules in modular tree transducers induces a strict hierarchy on the class of all modular tree transductions; and (3) by appropriately restricting the calling structure between modules, modular tree transducers characterize the compositions of macro tree transducers where the number of modules and the number of compositions coincide.

Details DOI

TCS Journal 1991 Journal Article

Nonterminal separation in graph grammars

  • Joost Engelfriet
  • George Leih
  • Grzegorz Rozenberg

The notion of nonterminal separation in eNCE graph grammars is introduced: such a graph grammar is k-separated (with k⩾1) if the distance between any two nonterminal nodes in any of its sentential forms is at least k (2-separated eNCE grammars are known as boundary eNCE graph grammars). There exists a 2-separated eNCE graph language that is not 3-separated. Apex eNCE graph grammars can be arbitrarily separated: every apex eNCE graph language can be generated by a k-separated apex eNCE grammar, for every k.

Details DOI

TCS Journal 1986 Journal Article

Pushdown machines for the macro tree transducer

  • Joost Engelfriet
  • Heiko Vogler

The macro tree transducer can be considered as a system of recursive function procedures with parameters, where the recursion is on a tree (e. g. , the syntax tree of a program). We investigate characterizations of the class of tree (tree-to-string) translations which is induced by macro tree transducers (macro tree-to-string transducers, respectively). For this purpose we define several pushdown machines of which the control is recursive without parameters, or even iterative, and which work on a generalized pushdown as storage. Because of the relevance for semantics of programming languages, we stress (besides the nondeterministic case) the study of machines for the total deterministic macro tree(-to-string) transducer, which translates every input tree into exactly one output tree (string, respectively). Finally, we characterize the n-fold composition of total deterministic macro tree transducers by recursive pushdown machines with an iterated pushdown as storage, which is a pushdown of pushdowns of … of pushdowns.

Details DOI

TCS Journal 1985 Journal Article

Determinancy → (observation equivalence = trace equivalence)

  • Joost Engelfriet

If an experiment s is conducted on a parallel process p, then, in general, different processes may result from the experiment, due to the nondeterministic behaviour of p (in the notation of Milner (1980): p p′ for different p′. Process p is called determinate if the resulting processes are all equivalent (i. e. , if p p′ and p p″, then p′ and p″ are equivalent). This means that, although p behaves nondeterministically, this cannot be detected by an observer of p. Let ⋍ denote observation equivalence, used in CCS (Milner, 1980), let ⋍f denote (the much weaker) failure equivalence, used for CSP (Hoare et al. , 1981; Brookes, 1983), and let ⋍t denote (the still weaker) trace equivalence. We show that the three corresponding notions of determinancy are the same, and that for determinate processes ⋍, ⋍f, and ⋍t are the same. Determinacy is preserved under ⋍ and ⋍f, but not under ⋍t.

Details DOI

TCS Journal 1977 Journal Article

Iterating iterated substitution

  • Joost Engelfriet

By iterating iterated substitution not all regular languages can be copied. Hence the smallest full hyper (1)-AFL is properly contained in ETOL, the smallest full hyper-AFL. The number of iterations of iterated substitution gives rise to a proper hierarchy. Consequently the smallest full hyper (1)-AFL is not a full principal AFL.

Details DOI

TCS Journal 1976 Journal Article

Surface tree languages and parallel derivation trees

  • Joost Engelfriet

The surface tree languages obtained by top-down finite state transformation of monadic trees are exactly the frontier-preserving homomorphic images of sets of derivation trees of ETOL systems. The corresponding class of tree transformation languages is therefore equal to the class of ETOL languages.

Details DOI