Document Open Access Logo

Orbit-Finite Sets and Their Algorithms (Invited Talk)

Author Mikolaj Bojanczyk

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.1.pdf
  • Filesize: 1.5 MB
  • 14 pages

Document Identifiers

Author Details

Mikolaj Bojanczyk

Cite As Get BibTex

Mikolaj Bojanczyk. Orbit-Finite Sets and Their Algorithms (Invited Talk). In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.1

Abstract

An introduction to orbit-finite sets, which are a type of sets that are infinite enough to describe interesting examples, and finite enough to have algorithms running on them. The notion of orbit-finiteness is illustrated on the example of register automata, an automaton model dealing with infinite alphabets.

Subject Classification

Keywords
  • Orbit-finite sets
  • sets with atoms
  • data words
  • register automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur and David L Dill. A theory of timed automata. Theoretical computer science, 126(2):183-235, 1994. Google Scholar
  2. Michael Benedikt, Clemens Ley, and Gabriele Puppis. Automata vs. logics on data words. In Computer Science Logic, 24th International Workshop, CSL 2010, 19th Annual Conference of the EACSL, Brno, Czech Republic, August 23-27, 2010. Proceedings, pages 110-124, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15205-4_12.
  3. Michael Benedikt, Clemens Ley, and Gabriele Puppis. What you must remember when processing data words. In Proceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management, Buenos Aires, Argentina, May 17-20, 2010, 2010. URL: http://ceur-ws.org/Vol-619/paper11.pdf.
  4. Henrik Björklund and Thomas Schwentick. On notions of regularity for data languages. Theor. Comput. Sci., 411(4-5):702-715, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2009.10.009.
  5. Mikołaj Bojańczyk. Atom book [online]. URL: https://www.mimuw.edu.pl/~bojan/paper/atom-book.
  6. Mikołaj Bojańczyk. Nominal monoids. Theory Comput. Syst., 53(2):194-222, 2013. URL: http://dx.doi.org/10.1007/s00224-013-9464-1.
  7. Mikołaj Bojańczyk, Laurent Braud, Bartek Klin, and Slawomir Lasota. Towards nominal computation. In Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, pages 401-412, 2012. URL: http://dx.doi.org/10.1145/2103656.2103704.
  8. Mikołaj Bojańczyk, Bartek Klin, and Slawomir Lasota. Automata theory in nominal sets. Logical Methods in Computer Science, 10(3), 2014. URL: http://dx.doi.org/10.2168/LMCS-10(3:4)2014.
  9. Mikołaj Bojańczyk, Bartek Klin, Slawomir Lasota, and Szymon Toruńczyk. Turing machines with atoms. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, pages 183-192, 2013. URL: http://dx.doi.org/10.1109/LICS.2013.24.
  10. Mikołaj Bojańczyk and Slawomir Lasota. A machine-independent characterization of timed languages. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, pages 92-103, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31585-5_12.
  11. Mikołaj Bojańczyk, Luc Segoufin, and Szymon Toruńczyk. Verification of database-driven systems via amalgamation. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22-27, 2013, pages 63-74, 2013. URL: http://dx.doi.org/10.1145/2463664.2465228.
  12. Mikołaj Bojańczyk and Szymon Toruńczyk. Imperative programming in sets with atoms. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, pages 4-15, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.4.
  13. Karlis Cerans. Deciding properties of integral relational automata. In Automata, Languages and Programming, 21st International Colloquium, ICALP94, Jerusalem, Israel, July 11-14, 1994, Proceedings, pages 35-46, 1994. URL: http://dx.doi.org/10.1007/3-540-58201-0_56.
  14. Lorenzo Clemente and Slawomir Lasota. Reachability analysis of first-order definable pushdown systems. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany, pages 244-259, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2015.244.
  15. Lorenzo Clemente and Slawomir Lasota. Timed pushdown automata revisited. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 738-749, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.73.
  16. W. Hodges. Model Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1993. Google Scholar
  17. Michael Kaminski and Nissim Francez. Finite-memory automata. Theor. Comput. Sci., 134(2):329-363, 1994. URL: http://dx.doi.org/10.1016/0304-3975(94)90242-9.
  18. Bartek Klin, Slawomir Lasota, Joanna Ochremiak, and Szymon Toruńczyk. Turing machines with atoms, constraint satisfaction problems, and descriptive complexity. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS'14, Vienna, Austria, July 14-18, 2014, pages 58:1-58:10, 2014. URL: http://dx.doi.org/10.1145/2603088.2603135.
  19. Eryk Kopczynski and Szymon Toruńczyk. LOIS: syntax and semantics. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, pages 586-598, 2017. URL: http://dl.acm.org/citation.cfm?id=3009876.
  20. Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michal Szynwelski. Learning nominal automata. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, pages 613-625, 2017. URL: http://dl.acm.org/citation.cfm?id=3009879.
  21. Andrzej S. Murawski, Steven J. Ramsay, and Nikos Tzevelekos. Bisimilarity in fresh-register automata. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 156-167, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.24.
  22. Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log., 5(3):403-435, 2004. URL: http://dx.doi.org/10.1145/1013560.1013562.
  23. M. Pistore. History Dependent Automata. PhD thesis, University of Pisa, 1999. Google Scholar
  24. A. M. Pitts. Nominal Sets: Names and Symmetry in Computer Science, volume 57 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2013. Google Scholar
  25. Luc Segoufin. Automata and logics for words and trees over an infinite alphabet. In Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, pages 41-57, 2006. URL: http://dx.doi.org/10.1007/11874683_3.
  26. Victor Vianu. Automatic verification of database-driven systems: a new frontier. In Intl. Conf. on Database Theory (ICDT), pages 1-13, 2009. URL: http://dx.doi.org/10.1145/1514894.1514896.
  27. Jin yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992. URL: http://dx.doi.org/10.1007/BF01305232.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact