Now showing items 1-3 of 3
State complexity of deletion and bipolar deletion
It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular ...
Growth Rate of Minimum Branching
(Institut fur Informatik, Justus-Liebig Universitat Giessen, 2018-03-14)
There are different ways of quantifying the nondeterminism used by a nondeterministic finite automaton (NFA). The amount of nondeterminism is measured as a function of the input length. For most ...
Site-directed insertion: Language equations and decision problems
Site-directed insertion is an overlapping insertion operation that can be viewed as analogous to the overlap assembly or chop operations that concatenate strings by overlapping a suffix and a prefix of the argument strings. ...