109 urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891 JUCS - Journal of Universal Computer Science jucs 0948-695X 0948-6968 Journal of Universal Computer Science 10.3217/jucs-016-05-0653 29624 Research Article F.1.3 - Complexity Measures and Classes F.4.3 - Formal Languages Orthogonal Concatenation: Language Equations and State Complexity Daley Mark daley@csd.uwo.ca 1 Domaratzki Michael 2 Salomaa Kai 3 University of Western Ontario London, daley@csd.uwo.ca, Canada University of Western Ontario London daley@csd.uwo.ca Canada University of Manitoba Winnipeg, mdomarat@cs.umanitoba.ca, Canada University of Manitoba Winnipeg mdomarat@cs.umanitoba.ca Canada Queen's University, Kingston, Canada Queen's University Kingston Canada

Corresponding author: Mark Daley (daley@csd.uwo.ca).

Academic editor:

2010 01 03 2010 16 5 653 675 BEA0A213-8F22-56D8-B892-205BA4C1CA4A 7001125 Mark Daley, Michael Domaratzki, Kai Salomaa This article is freely available under the J.UCS Open Content License.

A language L is the orthogonal concatenation of languages L1 and L2 if every word of L can be written in a unique way as a concatenation of a word in L1 and a word in L2. The notion can be generalized for arbitrary language operations. We consider decidability properties of language orthogonality and the solvability of language equations involving the orthogonal concatenation operation. We establish a tight bound for the state complexity of orthogonal concatenation of regular languages.