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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.3217/jucs-016-05-0653 | JOURNAL OF UNIVERSAL COMPUTER SCIENCE |
Keywords | Field | DocType |
language operations,language equations,regular languages,state complexity,decidability | Data mining,Algebra,Computer science,State complexity,Algorithm,Orthogonality,Decidability,Concatenation,Regular language | Journal |
Volume | Issue | ISSN |
16 | 5 | 0948-695X |
Citations | PageRank | References |
4 | 0.39 | 17 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mark Daley | 1 | 166 | 22.18 |
Michael Domaratzki | 2 | 268 | 24.98 |
Kai Salomaa | 3 | 1311 | 138.71 |