Boundary sets of regular and context-free languages

We investigate the descriptional and computational complexity of boundary sets of regular and context-free languages. For a letter a, the right (left, respectively) a-boundary set of a language L consists of the words in L whose a-predecessor or a-successor w.r.t. the prefix (suffix, respectively) relation is not in L  . For regular languages described by deterministic finite automata (DFAs) we give tight bounds on the number of states for accepting boundary sets. Moreover, the question whether the boundary sets of a regular language is finite is shown to be NLNL-complete for DFAs, while it turns out to be PSPACEPSPACE-complete for nondeterministic devices. Boundary sets for context-free languages are not necessarily context free anymore. Here we find a subtle difference of right and left a-boundary sets. While right a-boundary sets of deterministic context-free languages stay deterministic context free, we give an example of a deterministic context-free language whose a-boundary set is already non-context free. In fact, the finiteness problem for a-boundary sets of context-free languages becomes undecidable.