Derick Wood

I&C Journal 2008 Journal Article

Generalizations of 1-deterministic regular languages

• Yo-Sub Han
• Derick Wood

We examine two generalizations of 1-deterministic regular languages that are used for the content models of DTDs in XML. They are k-lookahead determinism and k-block-determinism. The k-lookahead determinism uses the first k symbols w 1 w 2 ⋯ w k of the current input string as lookahead to process the first symbol w 1. On the other hand, the k-block-determinism takes k w 1 w 2 ⋯ w k as lookahead and process the whole k symbols. We show that there is a hierarchy in k-lookahead determinism and there is a proper hierarchy in k-block-determinism. Moreover, we prove that k-block-deterministic regular languages are a proper subfamily of deterministic k-lookahead regular languages.

TCS Journal 2007 Journal Article

Obtaining shorter regular expressions from finite-state automata

• Yo-Sub Han
• Derick Wood

We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.

TCS Journal 2007 Journal Article

On the existence of prime decompositions

• Yo-Sub Han
• Arto Salomaa
• Kai Salomaa
• Derick Wood
• Sheng Yu

We investigate factorizations of regular languages in terms of prime languages. A language is said to be strongly prime decomposable if any way of factorizing it yields a prime decomposition in a finite number of steps. We give a characterization of the strongly prime decomposable regular languages and using the characterization we show that every regular language over a unary alphabet has a prime decomposition. We show that there exist non-regular unary languages that do not have prime decompositions. We also consider infinite factorizations of unary languages.

TCS Journal 2007 Journal Article

Prefix-free regular languages and pattern matching

• Yo-Sub Han
• Yajun Wang
• Derick Wood

We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We prove that a prefix-free regular expression gives only a linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. Furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.

TCS Journal 2004 Journal Article

Introduction

• Bruce W. Watson
• Derick Wood

TCS Journal 2004 Journal Article

On the state complexity of reversals of regular languages

• Arto Salomaa
• Derick Wood
• Sheng Yu

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2 n for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.

TCS Journal 2001 Journal Article

Normal form algorithms for extended context-free grammars

• Jürgen Albert
• Dora Giammarresi
• Derick Wood

We investigate the complexity of a variety of normal-form transformations for extended context-free grammars, where by extended we mean that the set of right-hand sides for each nonterminal in such a grammar is a regular set. The study is motivated by the implementation project GraMa which will provide a C++ toolkit for the symbolic manipulation of context-free objects just as Grail does for regular objects. Our results generalize known complexity bounds for context-free grammars but do so in nontrivial ways. Specifically, we introduce a new representation scheme for extended context-free grammars (the symbol-threaded expression forest), a new normal form for these grammars (dot normal form) and new regular expression algorithms.

I&C Journal 2001 Journal Article

SGML and XML Document Grammars and Exceptions

• Pekka Kilpeläinen
• Derick Wood

The Standard Generalized Markup Language (SGML) and the Extensible Markup Language (XML) allow users to define document-type definitions (DTDs), which are essentially extended context-free grammars expressed in a notation that is similar to extended Backus–Naur form. The right-hand side of a production, called a content model, is both an extended and a restricted regular expression. The semantics of content models for SGML DTDs can be modified by exceptions (XML does not allow exceptions). Inclusion exceptions allow named elements to appear anywhere within the content of a content model, and exclusion exceptions preclude named elements from appearing in the content of a content model. We give precise definitions of the semantics of exceptions, and prove that they do not increase the expressive power of SGML DTDs when we restrict DTDs according to accepted SGML practice. We prove the following results: 1. Exceptions do not increase the expressive power of extended context-free grammars. 2. For each DTD with exceptions, we can obtain a structurally equivalent extended context-free grammar. 3. For each DTD with exceptions, we can construct a structurally equivalent DTD when we restrict the DTD to adhere to accepted SGML practice. 4. Exceptions are a powerful shorthand notation—eliminating them may cause exponential growth in the size of an extended context-free grammar or of a DTD.

I&C Journal 1998 Journal Article

One-Unambiguous Regular Languages

• Anne Brüggemann-Klein
• Derick Wood

The ISO standard for the Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard, the right-hand sides of productions are based on regular expressions, although only regular expressions that denote words unambiguously, in the sense of the ISO standard, are allowed. In general, a word that is denoted by a regular expression is witnessed by a sequence of occurrences of symbols in the regular expression that match the word. In an unambiguous regular expression as defined by Booket al. (1971, IEEE Trans. Comput. C-20(2), 149–153), each word has at most one witness. But the SGML standard also requires that a witness be computed incrementally from the word with a one-symbol lookahead; we call such regular expressions 1-unambiguous. A regular language is a 1-unambiguouslanguage if it is denoted by some 1-unambiguous regular expression. We give a Kleene theorem for 1-unambiguous languages and characterize 1-unambiguous regular languages in terms of structural properties of the minimal deterministic automata that recognize them. As a result we are able to prove the decidability of whether a given regular expression denotes a 1-unambiguous language; if it does, then we can construct an equivalent 1-unambiguous regular expression in worst-case optimal time.

I&C Journal 1998 Journal Article

One-Unambiguous Regular Languages

• Anne Brüggemann-Klein
• Derick Wood

The ISO standard for the Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard, the right-hand sides of productions are based on regular expressions, although only regular expressions that denote words unambiguously, in the sense of the ISO standard, are allowed. In general, a word that is denoted by a regular expression is witnessed by a sequence of occurrences of symbols in the regular expression that match the word. In an unambiguous regular expression as defined by Booket al. (1971, IEEE Trans. Comput. C-20(2), 149–153) each word has at most one witness. But the SGML standard also requires that a witness be computed incrementally from the word with a one-symbol lookahead; we call such regular expressions 1-unambiguous. A regular language is a 1-unambiguous languageif it is denoted by some 1-unambiguous regular expression. We give a Kleene theorem for 1-unambiguous languages and characterize 1-unambiguous regular language in terms of structural properties of the minimal deterministic automata that recognize them. As a result we are able to prove the decidability of whether a given regular expression denotes a 1-unambiguous language; if it does, then we can construct an equivalent 1-unambiguous regular expression in worst-case optimal time.

TCS Journal 1996 Journal Article

Structural equivalence and ET0L grammars

• Kai Salomaa
• Derick Wood
• Yu Sheng

For a given context-sensitive grammar G we construct ET0L grammars G 1 and G 2 that are structurally equivalent if and only if the language generated by G is empty, which implies that structural equivalence is undecidable for ET0L grammars. In contrast, structural equivalence is decidable for E0L grammars and for extended E0L grammars. In fact, we show that structural equivalence is undecidable for propagating ET0L grammars in which the number of tables is restricted to be at most two. A stronger notion of equivalence that requires the sets of syntax trees to be isomorphic is shown to be decidable for ET0L grammars.

TCS Journal 1994 Journal Article

Balance in AVL trees and space cost of brother trees

• Helen Cameron
• Derick Wood

We characterize AVL trees that have, for their heights and weights, the maximum numbers of nodes whose subtrees differ in height by one (imbalanced nodes). We obtain the result from a characterization of brother trees with the maximum space costs for their heights and weights. The proof is based on a novel tree transformation that is of interest in its own right.

MFCS Conference 1994 Conference Paper

Complexity of E0L Structural Equivalence

• Kai Salomaa
• Derick Wood
• Sheng Yu 0001

Abstract We show that the EOL structural equivalence problem is logspace hard for deterministic exponential time. Also, we show that this question can be solved in linear space by a synchronized alternating Turing machine, and thus establish an exponential space upper bound for its complexity. The equivalence of finite tree automata is shown to be logspace reducible to context-free structural equivalence. The converse reduction is well known and thus context-free structural equivalence is complete for deterministic exponential time.

SODA Conference 1991 Conference Paper

Adaptive Heuristics for Binary Search Trees and Constant Linkage Cost

• Tony W. Lai
• Derick Wood

TCS Journal 1990 Journal Article

A tight upper bound for the path length of AVL trees

• Rolf Klein
• Derick Wood

We prove that the internal path length of an AVL tree of size N is bounded from above by 1. 4404N(log 2 N-log 2 log 2 N)+O(N) and show that this bound is achieved by an infinite family of AVL trees, each tree of which is not of maximal height. These results carry over to the comparison cost of brother trees.

I&C Journal 1989 Journal Article

A new measure of presortedness

• Vladimir Estivill-Castro
• Derick Wood

A new measure of presortedness is presented which we call Par. We prove that it is distinct from other common measures of presortedness and we design sorting algorithms that sort a sequence X in O(|X| log Par(X)) comparisons. Moreover, we prove that this is Par-optimal in a comparison-based model of computation.

I&C Journal 1987 Journal Article

Optimal computation of finitely oriented convex hulls

• Gregory J.E. Rawlins
• Derick Wood

We define four versions of the “convex hull” of a simple finitely oriented polygon (i. e. , a polygon whose edge orientations all belong to some fixed finite set of angles) and give optimal algorithms to find them. Two of these generalize the notions of the orthogonal convex hull of an orthogonal polygon and the traditional “bounding box” of a polygon. Three of the hulls have worst-case time complexity Θ(n + f) and worst case space complexity θ(n) space, where n is the number of edges of a given polygon and f (≥2) is the number of allowed orientations. We also show that testing whether an arbitrary simple polygon is (finitely oriented) convex has worst-case time and space complexity θ(n + f) and θ(n), respectively.

I&C Journal 1987 Journal Article

The node visit cost of brother trees

• Rolf Klein
• Derick Wood

The performance of a brother search tree depends on its shape; it can be measured by three basic cost measures: node visit cost, comparison cost, and space cost. The structure of brother trees that are optimal with respect to each of these cost measures is already known, as well as how to construct them in linear time. In this paper we investigate sharp bounds for the range that the node visit cost may take for a given size of tree. To this end we determine the structure of those brother trees which, for a given size N, have maximal (or pessimal) node visit cost. We derive a tight upper bound for the node visit cost of brother search trees which together with the lower bound obtained earlier yields the desired range estimation. Furthermore, we show that at least 11. 6% of the internal nodes of a brother tree of maximal height are unary.

MFCS Conference 1981 Conference Paper

On Structural Similarity of Context-Free Grammars

• Eljas Soisalon-Soininen
• Derick Wood

Abstract Given a grammar for translation or compiling purposes, the structure of the grammar reflects the semantics of the language rather than good parsing properties. Thus the language is often parsed with respect to another grammar, which satisfies the property that the derivation trees of the original grammar can be recovered from those of the parsing grammar. "Undercover" is introduced as a new concept for the formal treatment of such grammatical relations and properties of this relation are explored with an emphasis on decidability results and the relationship to existing concepts such as "cover" and "Reynolds cover". Some decidability questions can be related to language theoretic results on inclusion problems for simple languages.

MFCS Conference 1980 Conference Paper

Approaches to Concurrency in B-Trees

• Yat-Sang Kwong
• Derick Wood

MFCS Conference 1979 Invited Paper

A Survey of Grammar and L Forms-1978

• Derick Wood

Abstract The present paper gives an overview of grammar and L form theory as of January 31, 1979. It is intended to complement Ginsburg's 1977 survey of grammar forms [G]. Hence although we present some new results on grammar forms the main thrust of the paper is to survey L forms. The number of papers in this area is now over 65, see [W1] hence it may be observed that this is indeed a fast developing area, as is claimed in [M]. A more detailed exposition of the area can be found in [W2]. Because of this many open problems are stated in the hope that our own [G and MSW] excitement with this new area of formal language theory will be catching.

MFCS Conference 1979 Conference Paper

A Uniform Approach to Balanced Binary and Multiway Trees

• Thomas Ottmann
• Derick Wood

STOC Conference 1979 Conference Paper

Storage Representations for Tree-Like Data Structures

• Arnold L. Rosenberg
• Derick Wood
• Zvi Galil

We review the motivation underlying the study of data encodings and the formal framework of the study. We then present a series of results whose main message is that (complete) trees are materially less congenial storage representations for tree-like data structures than they have been shown to be for array-like data structures. In response to these results, we propose a new data structure, called a dree , which we show to share the advantages of trees, but not to suffer their disadvantages, when used as a storage structure.

TCS Journal 1976 Journal Article

A decomposition theorem for hyper-algebraic extensions of language families

• Jan van Leeuwen
• Derick Wood

In modern theories of rewriting structures, hyper-sentential and hyper-algebraic extensions of languages-families have abstracted the imminent features of iterated parallel substitution. After introducing the concept of a (depth-bounded) translation, we show that for each language L hyper-algebraic over a natural family F there are F -translations Δ, ḡD and languages L 1, …, L m hyper-sentential over F such that, for some p, q ⩾ 0. Two specializations of this result are given, when more assumptions are made about F. These are, firstly, a translation theorem and, secondly, an alphabetic homomorphism theorem for hyper-algebraic extensions (an alphabetic homomorphism is a letter-to-letter or letter-to-ε homomorphism).