 |
 |
Mikołaj Bojańczyk ; Bartek Klin ; Sławomir Lasota - Automata theory in nominal sets
lmcs:1157 - Logical Methods in Computer Science, August 15, 2014, Volume 10, Issue 3 - https://doi.org/10.2168/LMCS-10(3:4)2014Automata theory in nominal setsArticle
Authors: Mikołaj Bojańczyk ; Bartek Klin 
; Sławomir Lasota NULL##0000-0001-5793-7425##0000-0001-8674-4470Mikołaj Bojańczyk;Bartek Klin;Sławomir Lasota
We study languages over infinite alphabets equipped with some structure that can be tested by recognizing automata. We develop a framework for studying such alphabets and the ensuing automata theory, where the key role is played by an automorphism group of the alphabet. In the process, we generalize nominal sets due to Gabbay and Pitts.
Source: arXiv.org:1402.0897
Volume: Volume 10, Issue 3
Secondary volumes: Selected Papers of the 26th IEEE Symposium on Logic in Computer Science (LICS 2011)
Published on: August 15, 2014
Imported on: January 6, 2012
Keywords: Computer Science - Logic in Computer Science, Computer Science - Formal Languages and Automata Theory
Funding:
- Source : OpenAIRE Graph
- Expressive Power of Tree Logics; Funder: European Commission; Code: 239850
Classifications
Mathematics Subject Classification 20201
Sources:
- [1] zbMATH Open.
Bibliographic References
60 Documents citing this article
- Bálint Kocsis;Jurriaan Rot, 2025, Complete Test Suites for Automata in Monoidal Closed Categories, Lecture notes in computer science, pp. 198-219, 10.1007/978-3-031-90897-2_10, https://doi.org/10.1007/978-3-031-90897-2_10.
- Kevin Zhou, 2025, Query Learning Bounds for Advice and Nominal Automata, Lecture notes in computer science, pp. 257-278, 10.1007/978-3-031-78709-6_13.
- Orna Grumberg;Orna Kupferman;Sarai Sheinvald, 2025, Variable automata over infinite alphabets, Formal Methods in System Design, 10.1007/s10703-025-00472-7, https://doi.org/10.1007/s10703-025-00472-7.
- Hiroyuki Seki, 2024, Automata and Grammars for Data Words, Lecture notes in computer science, pp. 3-16, 10.1007/978-3-031-71112-1_1.
- Vasileios Koutavas;Yu-Yang Lin;Nikos Tzevelekos, 2024, Pushdown Normal-Form Bisimulation: A Nominal Context-Free Approach to Program Equivalence, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 1-15, 10.1145/3661814.3662103.
- Victor Iwaniack, 2024, Automata in W-Toposes, and General Myhill-Nerode Theorems, SPIRE - Sciences Po Institutional REpository, pp. 93-113, 10.1007/978-3-031-66438-0_5, https://inria.hal.science/hal-05000828.
- Khadijeh Keshvardoost;Mahdieh Haddadi, 2023, Projective finitely supported M-sets, Quasigroups and Related Systems, 30, 2(48), pp. 219-240, 10.56415/qrs.v30.19, https://doi.org/10.56415/qrs.v30.19.
- Rindo NAKANISHI;Yoshiaki TAKATA;Hiroyuki SEKI, 2023, Pumping Lemmas for Languages Expressed by Computational Models with Registers, IEICE Transactions on Information and Systems, E106.D, 3, pp. 284-293, 10.1587/transinf.2022fcp0004, http://dx.doi.org/10.1587/transinf.2022fcp0004.
- Samuel Balco;Alexander Kurz, 2023, Completeness of Nominal PROPs, Logical Methods in Computer Science, Volume 19, Issue 1, 10.46298/lmcs-19(1:8)2023, https://doi.org/10.46298/lmcs-19(1:8)2023.
- Andrei Alexandru;Gabriel Ciobanu, 2022, Soft Sets with Atoms, Mathematics, 10, 12, pp. 1956, 10.3390/math10121956, https://doi.org/10.3390/math10121956.
- David Venhoek;Joshua Moerman;Jurriaan Rot, 2022, Fast computations on ordered nominal sets, Theoretical Computer Science, 935, pp. 82-104, 10.1016/j.tcs.2022.09.002, https://doi.org/10.1016/j.tcs.2022.09.002.
- Florian Frank;Stefan Milius;Henning Urbat, 2022, Coalgebraic Semantics for Nominal Automata, Lecture notes in computer science, pp. 45-66, 10.1007/978-3-031-10736-8_3.
- Peter Jonsson;Victor Lagerkvist, 2022, General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs, Algorithmica, 85, 1, pp. 188-215, 10.1007/s00453-022-01017-8, https://doi.org/10.1007/s00453-022-01017-8.
- Rindo Nakanishi;Yoshiaki Takata;Hiroyuki Seki, 2022, Active Learning for Deterministic Bottom-Up Nominal Tree Automata, Lecture notes in computer science, pp. 342-359, 10.1007/978-3-031-17715-6_22.
- Simon Dierl;Falk Howar, 2022, $$\textsc {Reach}$$ on Register Automata via History Independence, Lecture notes in computer science, pp. 11-30, 10.1007/978-3-031-09827-7_2.
- Wißmann, Thorsten, 2022, Supported Sets - A New Foundation for Nominal Sets and Automata, arXiv (Cornell University), 10.4230/lipics.csl.2023.38, http://arxiv.org/abs/2201.09825.
- Bartek Klin;Sławomir Lasota;Szymon Toruńczyk, 2021, Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages, Lecture notes in computer science, pp. 365-384, 10.1007/978-3-030-71995-1_19, https://doi.org/10.1007/978-3-030-71995-1_19.
- Deifel, Hans-Peter;Milius, Stefan;Wißmann, Thorsten, 2021, Coalgebra Encoding for Efficient Minimization, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 10.4230/lipics.fscd.2021.28, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2021.28.
- Hausmann, Daniel;Milius, Stefan;Schröder, Lutz, 2021, A Linear-Time Nominal μ-Calculus with Name Allocation, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 10.4230/lipics.mfcs.2021.58, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.58.
- Manuel Bodirsky;Bertalan Bodor, 2021, Permutation groups with small orbit growth, Journal of Group Theory, 24, 4, pp. 643-709, 10.1515/jgth-2018-0220, https://doi.org/10.1515/jgth-2018-0220.
- Mikolaj Bojanczyk;Bartek Klin;Joshua Moerman, 2021, Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata, Data Archiving and Networked Services (DANS), 10.1109/lics52264.2021.9470634.
- Murdoch J. Gabbay, 2021, Algebras of UTxO blockchains, Mathematical Structures in Computer Science, 31, 9, pp. 1034-1089, 10.1017/s0960129521000438, https://doi.org/10.1017/s0960129521000438.
- Ryoma SENDA;Yoshiaki TAKATA;Hiroyuki SEKI, 2021, Forward Regularity Preservation Property of Register Pushdown Systems, IEICE Transactions on Information and Systems, E104.D, 3, pp. 370-380, 10.1587/transinf.2020fcp0008, https://doi.org/10.1587/transinf.2020fcp0008.
- Ryoma SENDA;Yoshiaki TAKATA;Hiroyuki SEKI, 2021, LTL Model Checking for Register Pushdown Systems, IEICE Transactions on Information and Systems, E104.D, 12, pp. 2131-2144, 10.1587/transinf.2020edp7265, https://doi.org/10.1587/transinf.2020edp7265.
- Ryoma Senda;Yoshiaki Takata;Hiroyuki Seki, 2021, Reactive Synthesis from Visibly Register Pushdown Automata, Lecture notes in computer science, pp. 334-353, 10.1007/978-3-030-85315-0_19.
- Simon Dierl;Falk Howar, 2021, A Taxonomy and Reductions for Common Register Automata Formalisms, Lecture notes in computer science, pp. 186-218, 10.1007/978-3-030-91384-7_10.
- Thorsten Wißmann;Hans-Peter Deifel;Stefan Milius;Lutz Schröder, 2021, From generic partition refinement to weighted tree automata minimization, Formal Aspects of Computing, 33, 4-5, pp. 695-727, 10.1007/s00165-020-00526-z, https://doi.org/10.1007/s00165-020-00526-z.
- Urbat, Henning;Hausmann, Daniel;Milius, Stefan;Schröder, Lutz, 2021, Nominal Büchi Automata with Name Allocation, arXiv (Cornell University), 10.4230/lipics.concur.2021.4, http://arxiv.org/abs/2107.03213.
- Henning Urbat;Lutz Schröder, 2020, Automata Learning, Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 900-914, 10.1145/3373718.3394775.
- Hiroyuki Seki;Reo Yoshimura;Yoshiaki Takata, 2020, Optimal run problem for weighted register automata, Theoretical Computer Science, 850, pp. 185-201, 10.1016/j.tcs.2020.11.003.
- Lorenzo Clemente, 2020, On the Complexity of the Universality and Inclusion Problems for Unambiguous Context-Free Grammars, Electronic Proceedings in Theoretical Computer Science, 320, pp. 29-43, 10.4204/eptcs.320.2, https://doi.org/10.4204/eptcs.320.2.
- Radu Grigore;Stefan Kiefer, 2020, Selective monitoring, Journal of Computer and System Sciences, 117, pp. 99-129, 10.1016/j.jcss.2020.09.003.
- Ryoma SENDA;Yoshiaki TAKATA;Hiroyuki SEKI, 2020, Generalized Register Context-Free Grammars, IEICE Transactions on Information and Systems, E103.D, 3, pp. 540-548, 10.1587/transinf.2019fcp0010, https://doi.org/10.1587/transinf.2019fcp0010.
- Hans-Peter Deifel;Stefan Milius;Lutz Schröder;Thorsten Wißmann, 2019, Generic Partition Refinement and Weighted Tree Automata, arXiv (Cornell University), pp. 280-297, 10.1007/978-3-030-30942-8_18, http://arxiv.org/abs/1811.08850.
- Hiroyuki Seki;Reo Yoshimura;Yoshiaki Takata, 2019, Optimal Run Problem for Weighted Register Automata, Lecture notes in computer science, pp. 91-110, 10.1007/978-3-030-32505-3_6.
- Lorenzo Clemente;Sławomir Lasota;Ranko Lazić;Filip Mazowiecki, 2019, Binary Reachability of Timed-register Pushdown Automata and Branching Vector Addition Systems, ACM Transactions on Computational Logic, 20, 3, pp. 1-31, 10.1145/3326161.
- Murdoch Gabbay, 2019, Equivariant ZFA and the foundations of nominal techniques, arXiv (Cornell University), 30, 2, pp. 525-548, 10.1093/logcom/exz015, http://arxiv.org/abs/1801.09443.
- Ryoma Senda;Yoshiaki Takata;Hiroyuki Seki, 2019, Generalized Register Context-Free Grammars, Lecture notes in computer science, pp. 259-271, 10.1007/978-3-030-13435-8_19.
- Yi Xiao;Emilio Tuosto, 2019, On Learning Nominal Automata with Binders, Electronic Proceedings in Theoretical Computer Science, 304, pp. 137-155, 10.4204/eptcs.304.9, https://doi.org/10.4204/eptcs.304.9.
- van Heerdt, Gerco;Kappé, Tobias;Rot, Jurriaan;Sammartino, Matteo;Silva, Alexandra, 2019, Tree Automata as Algebras: Minimisation and Determinisation, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 10.4230/lipics.calco.2019.6, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.6.
- David Venhoek;Joshua Moerman;Jurriaan Rot, 2018, Fast Computations on Ordered Nominal Sets, Lecture notes in computer science, pp. 493-512, 10.1007/978-3-030-02508-3_26.
- Sławomir Lasota;Radosław Piórkowski, 2018, WQO Dichotomy for 3-Graphs, Lecture notes in computer science, pp. 548-564, 10.1007/978-3-319-89366-2_30, https://doi.org/10.1007/978-3-319-89366-2_30.
- Benedikt Brütsch;Patrick Landwehr;Wolfgang Thomas, 2017, $$\mathbb {N}$$ -Memory Automata over the Alphabet $$\mathbb {N}$$, Lecture notes in computer science, pp. 91-102, 10.1007/978-3-319-53733-7_6.
- Eryk Kopczyński;Szymon Toruńczyk, 2017, LOIS: syntax and semantics, ACM SIGPLAN Notices, 52, 1, pp. 586-598, 10.1145/3093333.3009876.
- Joshua Moerman;Matteo Sammartino;Alexandra Silva;Bartek Klin;Michał Szynwelski, 2017, Learning nominal automata, ACM SIGPLAN Notices, 52, 1, pp. 613-625, 10.1145/3093333.3009879.
- Khadijeh Keshvardoost;Mojgan Mahmoudi, 2017, Free functor from the category of G-nominal sets to that of 01-G-nominal sets, Soft Computing, 22, 11, pp. 3637-3648, 10.1007/s00500-017-2793-2.
- Lutz Schröder;Dexter Kozen;Stefan Milius;Thorsten Wißmann, 2017, Nominal Automata with Name Binding, Lecture notes in computer science, pp. 124-142, 10.1007/978-3-662-54458-7_8.
- M.M. Ebrahimi;Kh. Keshvardoost;M. Mahmoudi, 2017, Simple and subdirectly irreducible finitely supported Cb-sets, Theoretical Computer Science, 706, pp. 1-21, 10.1016/j.tcs.2017.08.003.
- Piotr Hofman;Jerome Leroux;Patrick Totzke, 2017, Linear combinations of unordered data vectors, Edinburgh Research Explorer (University of Edinburgh), pp. 1-11, 10.1109/lics.2017.8005065, http://ieeexplore.ieee.org/document/8005065/.
- Thomas Colcombet;Daniela Petrişan, 2017, Automata and minimization, ACM SIGLOG News, 4, 2, pp. 4-27, 10.1145/3090064.3090066.
- Andrew Pitts, 2016, Nominal techniques, ACM SIGLOG News, 3, 1, pp. 57-72, 10.1145/2893582.2893594, https://doi.org/10.1145/2893582.2893594.
- Bartek Klin;Michał Szynwelski, 2016, SMT Solving for Functional Programming over Infinite Structures, Electronic Proceedings in Theoretical Computer Science, 207, pp. 57-75, 10.4204/eptcs.207.3, https://doi.org/10.4204/eptcs.207.3.
- Eryk Kopczyński;Szymon Toruńczyk, 2016, LOIS: syntax and semantics, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, pp. 586-598, 10.1145/3009837.3009876.
- Joshua Moerman;Matteo Sammartino;Alexandra Silva;Bartek Klin;Michał Szynwelski, 2016, Learning nominal automata, arXiv (Cornell University), pp. 613-625, 10.1145/3009837.3009879, http://arxiv.org/abs/1607.06268.
- Manuel Bodirsky;Antoine Mottet, 2016, Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 623-632, 10.1145/2933575.2934515.
- Piotr Hofman;Sławomir Lasota;Ranko Lazić;Jérôme Leroux;Sylvain Schmitz;Patrick Totzke, 2016, Coverability Trees for Petri Nets with Unordered Data, pp. 445-461, 10.1007/978-3-662-49630-5_26, https://inria.hal.science/hal-01252674.
- Sławomir Lasota, 2016, Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture, Lecture notes in computer science, pp. 20-36, 10.1007/978-3-319-39086-4_3, https://doi.org/10.1007/978-3-319-39086-4_3.
- Bartek Klin;Eryk Kopczynski;Joanna Ochremiak;Szymon Torunczyk, 2015, Locally Finite Constraint Satisfaction Problems, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, abs 1203 1876, pp. 475-486, 10.1109/lics.2015.51.
- Dexter Kozen;Konstantinos Mamouras;Alexandra Silva, 2015, Completeness and Incompleteness in Nominal Kleene Algebra, Lecture notes in computer science, pp. 51-66, 10.1007/978-3-319-24704-5_4.
- Dexter Kozen;Konstantinos Mamouras;Daniela Petrişan;Alexandra Silva, 2015, Nominal Kleene Coalgebra, Lecture notes in computer science, pp. 286-298, 10.1007/978-3-662-47666-6_23.
Share and export
Consultation statistics
This page has been seen 3377 times.
This article's PDF has been downloaded 1144 times.