Abstract | ||
---|---|---|
FO transductions, aperiodic deterministic two-way transducers, as well as aperiodic streaming string transducers are all equivalent models for first order definable functions. In this paper, we solve the problem of expressions capturing first order definable functions, thereby generalizing the seminal SF=AP (star-free expressions = aperiodic languages) result of Schützenberger. Our result also gen... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/LICS52264.2021.9470738 | 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
DocType | ISBN | Citations |
Conference | 978-1-6654-4895-6 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Luc Dartois | 1 | 0 | 0.34 |
Paul Gastin | 2 | 0 | 0.34 |
Shankara Narayanan Krishna | 3 | 243 | 42.57 |