State complexity of orthogonal catenation

Simple item page
dc.creatorDaley, Mark
dc.creatorDomaratzki, Michael
dc.creatorSalomaa, Kai
dc.date2009-04-22
dc.date.accessioned2026-07-07T13:07:11Z
dc.date.available2026-07-07T13:07:11Z
dc.descriptionA 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.
dc.descriptionDCFS 2008
dc.identifierhttps://arxiv.org/abs/0904.3366
dc.identifierhttp://arxiv.org/abs/0904.3366
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/228011
dc.subjectFormal Languages and Automata Theory
dc.titleState complexity of orthogonal catenation
dc.typetext

Files

Collections

arXiv