Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 16 / Issue 5

available in:   PDF (212 kB) PS (173 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-016-05-0653


Orthogonal Concatenation: Language Equations and State Complexity

Mark Daley (University of Western Ontario London, Canada)

Michael Domaratzki (University of Manitoba Winnipeg, Canada)

Kai Salomaa (Queen's University, Canada)

Abstract: 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.

Keywords: decidability, language equations, language operations, regular languages, state complexity

Categories: F.1.3, F.4.3