pith. sign in

arxiv: 0904.3366 · v1 · submitted 2009-04-22 · 💻 cs.FL

State complexity of orthogonal catenation

classification 💻 cs.FL
keywords catenationboundorthogonalwordcomplexitylanguagesstatearbitrary
0
0 comments X
read the original abstract

A language $L$ is the orthogonal catenation of languages $L_1$ and $L_2$ if every word of $L$ can be written in a unique way as a catenation of a word in $L_1$ and a word in $L_2$. We establish a tight bound for the state complexity of orthogonal catenation of regular languages. The bound is smaller than the bound for arbitrary catenation.

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.