 |
 |
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
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
Bibliographic References
52 Documents citing this article
- Rindo Nakanishi;Ryoma Senda;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, https://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 (Basel), 10, 12, pp. 1956, 10.3390/math10121956, https://doi.org/10.3390/math10121956.
- Florian Frank;Stefan Milius;Henning Urbat, arXiv (Cornell University), Coalgebraic Semantics for Nominal Automata, pp. 45-66, 2022, 10.1007/978-3-031-10736-8_3, http://arxiv.org/abs/2202.06546.
- 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, arXiv (Cornell University), Active Learning for Deterministic Bottom-Up Nominal Tree Automata, pp. 342-359, 2022, 10.1007/978-3-031-17715-6_22, http://arxiv.org/abs/2208.08319.
- Simon Dierl;Falk Howar, Lecture Notes in Computer Science, $$\textsc {Reach}$$ on Register Automata via History Independence, pp. 11-30, 2022, 10.1007/978-3-031-09827-7_2.
- Venhoek, David;Moerman, Joshua;Rot, Jurriaan, 2022, Fast computations on ordered nominal sets, arXiv (Cornell University), 935, pp. 82-104, 10.1016/j.tcs.2022.09.002, https://arxiv.org/abs/1902.08414.
- Bartek Klin;Sławomir Lasota;Szymon Toruńczyk, Lecture Notes in Computer Science, Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages, pp. 365-384, 2021, 10.1007/978-3-030-71995-1_19, https://doi.org/10.1007/978-3-030-71995-1_19.
- Hans-Peter Deifel;Stefan Milius;Thorsten Wißmann, 2021, Coalgebra Encoding for Efficient Minimization, pp. 19-, 10.4230/lipics.fscd.2021.28.
- Henning Urbat;Daniel Hausmann;Stefan Milius;Lutz Schröder, Nominal Büchi Automata with Name Allocation, pp. 16-, 2021, 10.4230/lipics.concur.2021.4.
- Hiroyuki Seki;Reo Yoshimura;Yoshiaki Takata, 2021, Optimal run problem for weighted register automata, Theoretical Computer Science, 850, pp. 185-201, 10.1016/j.tcs.2020.11.003.
- 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, arXiv (Cornell University), Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata, 2021, Rome, Italy, 10.1109/lics52264.2021.9470634, http://arxiv.org/abs/2104.02438.
- Murdoch J. Gabbay, 2021, Algebras of UTxO blockchains, MSCS. Mathematical structures in computer science (Print), 31, 9, pp. 1034-1089, 10.1017/s0960129521000438, https://doi.org/10.1017/s0960129521000438.
- Radu Grigore;Stefan Kiefer, 2021, 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, 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, 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, Lecture Notes in Computer Science, Reactive Synthesis from Visibly Register Pushdown Automata, pp. 334-353, 2021, 10.1007/978-3-030-85315-0_19.
- Simon Dierl;Falk Howar, Lecture Notes in Computer Science, A Taxonomy and Reductions for Common Register Automata Formalisms, pp. 186-218, 2021, 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.
- Daniel Hausmann;Stefan Milius;Lutz Schröder, A Linear-Time Nominal μ-Calculus with Name Allocation., pp. 18-, 2020, 10.4230/lipics.mfcs.2021.58.
- Henning Urbat;Lutz Schröder, Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Automata Learning, 2020, Saarbrücken Germany, 10.1145/3373718.3394775.
- Lorenzo Clemente, 2020, On the Complexity of the Universality and Inclusion Problems for Unambiguous Context-Free Grammars, arXiv (Cornell University), 320, pp. 29-43, 10.4204/eptcs.320.2.
- Murdoch James Gabbay, 2020, Equivariant ZFA and the foundations of nominal techniques, arXiv (Cornell University), 30, 2, pp. 525-548, 10.1093/logcom/exz015, https://arxiv.org/abs/1801.09443.
- 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.
- Gerco van Heerdt;Tobias Kappé;Jurriaan Rot;Matteo Sammartino;Alexandra Silva, 2019, Tree Automata as Algebras: Minimisation and Determinisation, arXiv (Cornell University), 10.4230/lipics.calco.2019.6, https://arxiv.org/abs/1904.08802.
- Hans-Peter Deifel;Stefan Milius;Lutz Schröder;Thorsten Wißmann, arXiv (Cornell University), Generic Partition Refinement and Weighted Tree Automata, pp. 280-297, 2019, 10.1007/978-3-030-30942-8_18, https://arxiv.org/abs/1811.08850.
- Hiroyuki Seki;Reo Yoshimura;Yoshiaki Takata, Lecture Notes in Computer Science, Optimal Run Problem for Weighted Register Automata, pp. 91-110, 2019, 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, Warwick Research Archive Portal (University of Warwick), 20, 3, pp. 1-31, 10.1145/3326161, http://wrap.warwick.ac.uk/119092/1/WRAP-binary-reachability-timed-register-pushdown-automata-vector-Lazic-2019.pdf.
- Ryoma Senda;Yoshiaki Takata;Hiroyuki Seki, Lecture Notes in Computer Science, Generalized Register Context-Free Grammars, pp. 259-271, 2019, 10.1007/978-3-030-13435-8_19.
- Yi Xiao;Emilio Tuosto, 2019, On Learning Nominal Automata with Binders, arXiv (Cornell University), 304, pp. 137-155, 10.4204/eptcs.304.9.
- David Venhoek;Joshua Moerman;Jurriaan Rot, arXiv (Cornell University), Fast Computations on Ordered Nominal Sets, pp. 493-512, 2018, 10.1007/978-3-030-02508-3_26, http://arxiv.org/abs/1902.08414.
- M.M. Ebrahimi;Kh. Keshvardoost;M. Mahmoudi, 2018, Simple and subdirectly irreducible finitely supported Cb-sets, Theoretical Computer Science, 706, pp. 1-21, 10.1016/j.tcs.2017.08.003, https://doi.org/10.1016/j.tcs.2017.08.003.
- Sławomir Lasota;Radosław Piórkowski, Lecture notes in computer science, WQO Dichotomy for 3-Graphs, pp. 548-564, 2018, 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, Lecture notes in computer science, $$\mathbb {N}$$ -Memory Automata over the Alphabet $$\mathbb {N}$$, pp. 91-102, 2017, 10.1007/978-3-319-53733-7_6.
- Eryk Kopczyński;Szymon Toruńczyk, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, LOIS: syntax and semantics, 2017, Paris France, 10.1145/3009837.3009876.
- Joshua Moerman;Matteo Sammartino;Alexandra Silva;Bartek Klin;Michał Szynwelski, arXiv (Cornell University), Learning nominal automata, 2017, Paris France, 10.1145/3009837.3009879, https://arxiv.org/abs/1607.06268.
- 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.
- KopczyńskiEryk;ToruńczykSzymon, 2017, LOIS: syntax and semantics, SIGPLAN notices, 52, 1, pp. 586-598, 10.1145/3093333.3009876.
- Lutz Schröder;Dexter Kozen;Stefan Milius;Thorsten Wiβmann, arXiv (Cornell University), Nominal Automata with Name Binding, pp. 124-142, 2017, 10.1007/978-3-662-54458-7_8, http://arxiv.org/abs/1603.01455.
- MoermanJoshua;SammartinoMatteo;SilvaAlexandra;KlinBartek;SzynwelskiMichał, 2017, Learning nominal automata, UCL Discovery (University College London), 52, 1, pp. 613-625, 10.1145/3093333.3009879, https://discovery.ucl.ac.uk/id/eprint/10085264/.
- Piotr Hofman;Jérôme Leroux;Patrick Totzke, Edinburgh Research Explorer (University of Edinburgh), Linear combinations of unordered data vectors, 2017, Reykjavik, Iceland, 10.1109/lics.2017.8005065, https://www.pure.ed.ac.uk/ws/files/35462990/HLT2017.pdf.
- Thomas Colcombet;Daniela Petrişan, 2017, Automata and minimization, SIGLOG news, 4, 2, pp. 4-27, 10.1145/3090064.3090066, https://doi.org/10.1145/3090064.3090066.
- Andrew Pitts, 2016, Nominal techniques, 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, arXiv (Cornell University), 207, pp. 57-75, 10.4204/eptcs.207.3.
- Manuel Bodirsky;Antoine Mottet, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction, 2016, New York NY USA, 10.1145/2933575.2934515.
- Piotr Hofman;Sławomir Lasota;Ranko Lazić;Jérôme Leroux;Sylvain Schmitz;et al., Coverability Trees for Petri Nets with Unordered Data, pp. 445-461, 2016, 10.1007/978-3-662-49630-5_26, https://hal.inria.fr/hal-01252674.
- Sławomir Lasota, Lecture Notes in Computer Science, Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture, pp. 20-36, 2016, 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, CiteSeer X (The Pennsylvania State University), Locally Finite Constraint Satisfaction Problems, 2015, Kyoto, Japan, 10.1109/lics.2015.51, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.702.3798.
- Dexter Kozen;Konstantinos Mamouras;Alexandra Silva, CiteSeer X (The Pennsylvania State University), Completeness and Incompleteness in Nominal Kleene Algebra, pp. 51-66, 2015, 10.1007/978-3-319-24704-5_4, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.713.9909.
- Dexter Kozen;Konstantinos Mamouras;Daniela Petrişan;Alexandra Silva, eCommons (Cornell University), Nominal Kleene Coalgebra, pp. 286-298, 2015, 10.1007/978-3-662-47666-6_23, https://hdl.handle.net/1813/39108.
Share and export
Consultation statistics
This page has been seen 1842 times.
This article's PDF has been downloaded 646 times.