Name
Abstract | ||
|---|---|---|
A language over an alphabet B= A boolean OR (A) over bar of opening (A) and closing ((A) over bar) brackets, is balanced if it is a subset of the Dyck language D-B over B, and it is well-formed if all words are prefixes of words in D-B. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-TW of non-linear tree transducers with output alphabet B whether or not the output language is balanced. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1142/S0129054121420077 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | DocType | Volume |
Balancedness, equivalence, longest common suffix/prefix | Journal | 32 |
Issue | ISSN | Citations |
06 | 0129-0541 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaela Loebel | 1 | 0 | 0.34 |
| Michael Luttenberger | 2 | 0 | 0.34 |
| Helmut Seidl | 3 | 1468 | 103.61 |