JUCS - Journal of Universal Computer Science 16(5): 653-675, doi: 10.3217/jucs-016-05-0653
Orthogonal Concatenation: Language Equations and State Complexity
Mark Daley‡,
Michael Domaratzki§,
Kai Salomaa|‡ University of Western Ontario London, daley@csd.uwo.ca, Canada§ University of Manitoba Winnipeg, mdomarat@cs.umanitoba.ca, Canada| Queen's University, Kingston, Canada
Corresponding author:
Mark Daley
(
daley@csd.uwo.ca
)
© Mark Daley, Michael Domaratzki, Kai Salomaa. Citation:
Daley M, Domaratzki M, Salomaa K (2010) Orthogonal Concatenation: Language Equations and State Complexity. JUCS - Journal of Universal Computer Science 16(5): 653-675. https://doi.org/10.3217/jucs-016-05-0653 | ![Open Access](/i/open_access_icon_colour.svg) |
AbstractA 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.
Keywordslanguage operations, language equations, regular languages, state complexity, decidability