Wyniki wyszukiwania - BazTech

1

Tight Bounds for Cut-Operations on Deterministic Finite Automata

Drewes F., van der Merwe B., Holzer M., Jakobi S.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

89--110

EN

We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n-1).m+n states, otherwise, on DFAs accepting the cut of two individual languages that are accepted by n-andm-state DFAs, respectively. In the unary case we obtain max(2n-1;m+n-2) states as a tight bound--notice that for m ≤n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1). F( 1; n+2;-n+2; n+1 j-1 ) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n - 1)!). Finally, the bound drops to 2n - 1 for unary DFAs accepting the iterated cut of an n-state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs.

2

Path Languages of Random Permitting Context Tree Grammars are Regular

Drewes F., van der Merwe B.

Fundamenta Informaticae

|

2008

|

Vol. 82, nr 1-2

47-60

EN

The path languages of random permitting context tree languages are investigated. The main result is that these path languages are regular. This confirms a previous conjecture.

3

Bag Context Tree Grammars

Drewes F., du Toit C., Ewert S., van der Merwe B., van der Walt A.

Fundamenta Informaticae

|

2008

|

Vol. 86, nr 4

459-480

EN

We introduce bag context as a device for regulated rewriting in tree grammars. Bag context represents information that is not part of a developing tree, but instead evolves separately during a derivation. We present several results. First, we give some normal forms and equivalent formulations for bag context tree grammars. Then we compare bag context tree grammars to their random context counterparts. We show that bag context is strictly more powerful than random context; in doing so, we show that the class of bag context tree languages is the closure of the class of random context tree languages under linear top-down tree transductions. Finally, we consider the structural limitations of bag context tree grammars. We establish a necessary condition for languages generated by bag context tree grammars, and use it to present a tree language that cannot be generated by such a grammar. Moreover, we show that the class of bag context tree languages is incomparable with the class of branching synchronization tree languages.

4

Context-exploiting shapes for diagram transformation

Drewes F., Hoffmann B., Minas M.

Machine Graphics and Vision

|

2003

|

Vol. 12, No. 1

117-132

EN

DIA PLAN is a language for programming with graphs representing diagram that is currently being developed. The computational model of the language - nested graph transformation - suports nested structuring of graphs and graph variables, but is still intuitive. This paper discusses structural typing of nested graphs and nested graph transformation systems by shape rules. We extend the context-free shape rules proposed in earlier work to contexy-exploiting shape rules with which many relevant graph structures can be specifed. The conformance of a nested graph to the shape rules is decidable. If a trabsformation system conforms to shape rules as well. it can be shown to preserve shape conformance of the graphs it is applied to. This sets up a static type discipline for nested graph transformation.