Complexity in Prefix-Free Regular Languages
classification
💻 cs.FL
keywords
languagescomplexityprefix-freestatedeterministicdifferencenondeterministicregular
read the original abstract
We examine deterministic and nondeterministic state complexities of regular operations on prefix-free languages. We strengthen several results by providing witness languages over smaller alphabets, usually as small as possible. We next provide the tight bounds on state complexity of symmetric difference, and deterministic and nondeterministic state complexity of difference and cyclic shift of prefix-free languages.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.