文章基本信息
- 标题：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 等
- 期刊名称：Journal of Universal Computer Science
- 印刷版ISSN：0948-6968
- 出版年度：2010
- 卷号：16
- 期号：5
- 出版社：Graz University of Technology and Know-Center
- 摘要：
Abstract: A language L is the orthogonal concatenation of languages L 1 and L 2 if every word of L can be written in a unique way as a concatenation of a word in L 1 and a word in L 2. 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.
- 关键词：decidability, language equations, language operations, regular languages, state complexity
