Abstract | ||
---|---|---|
This paper explores different means of representation for algebraic transductions, i.e., word relations realized by pushdown transducers. The relevance of this work lies more in its point of view rather than any particular result. We are aiming at giving specific techniques for obtaining, or perhaps explaining, decompositions of algebraic (and incidentally, rational) relations, relying solely on their “machine” definition rather than some complex algebraic apparatus. From this point of view, we are hoping to have demystified the heavy formalism employed in the present literature. Some of the novelties of our work are: the use of “stack languages” and “embeddings,” which eliminate the need of arbitrary context-free languages in our characterizations, the study of uniformizations for algebraic transductions and the use of the so-called stack transductions for exposing the anatomy of pushdown transducers. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/s00236-006-0027-7 | Acta Inf. |
Keywords | Field | DocType |
specific technique,particular result,present literature,arbitrary context-free language,different mean,complex algebraic apparatus,word relation,pushdown transducers,algebraic transductions,heavy formalism,context free language | Discrete mathematics,Context-free language,Uniformization (set theory),Algebraic number,Formal language,Algebra,Computer science,Pure mathematics,Algebraic function,Grammar,Formalism (philosophy),Regular language | Journal |
Volume | Issue | ISSN |
43 | 6 | 1432-0525 |
Citations | PageRank | References |
4 | 0.46 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stavros Konstantinidis | 1 | 283 | 31.10 |
Nicolae Santean | 2 | 109 | 13.05 |
Sheng Yu | 3 | 697 | 77.85 |