pith. sign in

arxiv: 1607.04031 · v1 · pith:4AR5T64Inew · submitted 2016-07-14 · 💻 cs.FL

State complexity of multiple catenation

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

We improve some results relative to the state complexity of the multiple catenation described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for witnesses. We also give some refinements to the algebraic expression of the state complexity, which is especially complex with this operation. We obtain these results by using peculiar DFAs defined by Brzozowski.

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.