 |
 |
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
Classifications
Mathematics Subject Classification 20201
Sources:
- [1] zbMATH Open.
Bibliographic References
51 Documents citing this article
- 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, 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, 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, arXiv (Cornell University), 935, pp. 82-104, 10.1016/j.tcs.2022.09.002, http://arxiv.org/abs/1902.08414.
- 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.
- 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, International Conference on Concurrency Theory, Nominal Büchi Automata with Name Allocation, pp. 16-, 2021, 10.4230/lipics.concur.2021.4.
- 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, RWTH Publications (RWTH Aachen), Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata, 2021, Rome, Italy, 10.1109/lics52264.2021.9470634, https://publications.rwth-aachen.de/record/817082.
- 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, 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, Mathematical Foundations of Computer Science, 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, pp. 900-914, 2020, Saarbrücken Germany, 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, arXiv (Cornell University), 320, pp. 29-43, 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, 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.
- Murdoch Gabbay, 2019, 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, 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.
- 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, 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, UCL Discovery (University College London), 52, 1, pp. 613-625, 10.1145/3093333.3009879, https://discovery.ucl.ac.uk/id/eprint/10085264/.
- 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, 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.
- 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, https://doi.org/10.1016/j.tcs.2017.08.003.
- Piotr Hofman;Jerome Leroux;Patrick Totzke, Edinburgh Research Explorer (University of Edinburgh), Linear combinations of unordered data vectors, pp. 1-11, 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, ACM SIGLOG News, 4, 2, pp. 4-27, 10.1145/3090064.3090066, https://doi.org/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, arXiv (Cornell University), 207, pp. 57-75, 10.4204/eptcs.207.3.
- Eryk Kopczyński;Szymon Toruńczyk, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, LOIS: syntax and semantics, 2016, Paris France, 10.1145/3009837.3009876.
- Joshua Moerman;Matteo Sammartino;Alexandra Silva;Bartek Klin;Michał Szynwelski, arXiv (Cornell University), Learning nominal automata, 2016, Paris France, 10.1145/3009837.3009879, http://arxiv.org/abs/1607.06268.
- 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, pp. 475-486, 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, UCL Discovery (University College London), Completeness and Incompleteness in Nominal Kleene Algebra, pp. 51-66, 2015, 10.1007/978-3-319-24704-5_4, https://discovery.ucl.ac.uk/id/eprint/10117572/1/Silva_NKA.pdf.
- 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 2515 times.
This article's PDF has been downloaded 799 times.