×

Emptiness problems for distributed automata. (English) Zbl 1443.68091

Summary: We investigate the decidability of the emptiness problem for three classes of distributed automata. These devices operate on finite directed graphs, acting as networks of identical finite-state machines that communicate in an infinite sequence of synchronous rounds. The problem is shown to be decidable in LogSpace for a class of forgetful automata, where the nodes see the messages received from their neighbors but cannot remember their own state. When restricted to the appropriate families of graphs, these forgetful automata are equivalent to classical finite word automata, but strictly more expressive than finite tree automata. On the other hand, we also show that the emptiness problem is undecidable in general. This already holds for two heavily restricted classes of distributed automata: those that reject immediately if they receive more than one message per round, and those whose state diagram must be acyclic except for self-loops. Additionally, to demonstrate the flexibility of distributed automata in simulating different models of computation, we provide a characterization of constraint satisfaction problems by identifying a class of automata with exactly the same computational power.

MSC:

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bienvenu, M.; ten Cate, B.; Lutz, C.; Wolter, F., Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP, ACM Trans. Database Syst., 39, 4, 1-44 (2014) · Zbl 1474.68082
[2] Blackburn, P.; van Benthem, J., Modal logic: a semantic perspective, (Blackburn, P.; van Benthem, J.; Wolter, F., Handbook of Modal Logic. Handbook of Modal Logic, Studies in Logic and Practical Reasoning, vol. 3 (2007), Elsevier), 1-84 · Zbl 1114.03001
[3] Blackburn, P.; de Rijke, M.; Venema, Y., Modal Logic, Cambridge Tracts in Theoretical Computer Science, vol. 53 (2002), Cambridge University Press: Cambridge University Press Cambridge
[4] Bloem, R.; Jacobs, S.; Khalimov, A.; Konnov, I.; Rubin, S.; Veith, H.; Widder, J., Decidability of Parameterized Verification, Synthesis Lectures on Distributed Computing Theory (2015), Morgan & Claypool Publishers · Zbl 1400.68006
[5] Bodirsky, M.; Dalmau, V., Datalog and constraint satisfaction with infinite templates, J. Comput. Syst. Sci., 79, 1, 79-100 (2013) · Zbl 1263.68051
[6] Bulatov, A. A., A dichotomy theorem for nonuniform CSPs, (58th IEEE Annual Symposium on Foundations of Computer Science. 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 (2017)), 319-330
[7] Carton, O.; Guillon, B.; Reiter, F., Counter machines and distributed automata - a story about exchanging space and time, (Baetens, J. M.; Kutrib, M., Cellular Automata and Discrete Complex Systems - 24th IFIP WG 1.5 International. Cellular Automata and Discrete Complex Systems - 24th IFIP WG 1.5 International, Workshop, AUTOMATA 2018, Ghent, Belgium, June 20-22, 2018, Proceedings. Cellular Automata and Discrete Complex Systems - 24th IFIP WG 1.5 International. Cellular Automata and Discrete Complex Systems - 24th IFIP WG 1.5 International, Workshop, AUTOMATA 2018, Ghent, Belgium, June 20-22, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10875 (2018), Springer), 13-28 · Zbl 1508.68233
[8] Comon, H.; Dauchet, M.; Gilleron, R.; Jacquemard, F.; Löding, C.; Lugiez, D.; Tison, S.; Tommasi, M., Tree automata techniques and applications (2008), release November 18, 2008
[9] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (1998) · Zbl 0914.68075
[10] Feier, C.; Kuusisto, A.; Lutz, C., Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics (invited talk), (20th International Conference on Database Theory. 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy (2017)), 1-17 · Zbl 1402.68046
[11] Goles, E.; Ollinger, N.; Theyssier, G., Introducing freezing cellular automata, (Cellular Automata and Discrete Complex Systems. Cellular Automata and Discrete Complex Systems, Turku, Finland. Cellular Automata and Discrete Complex Systems. Cellular Automata and Discrete Complex Systems, Turku, Finland, TUCS Lecture Notes, vol. 24 (2015)), 65-73, hal-id: hal-01294144
[12] Göös, M.; Suomela, J., Locally checkable proofs in distributed computing, Theory Comput., 12, 1, 1-33 (2016) · Zbl 1401.68085
[13] Hella, L.; Järvisalo, M.; Kuusisto, A.; Laurinharju, J.; Lempiäinen, T.; Luosto, K.; Suomela, J.; Virtema, J., Weak models of distributed computing, with connections to modal logic, (Kowalski, D.; Panconesi, A., ACM Symposium on Principles of Distributed Computing. ACM Symposium on Principles of Distributed Computing, PODC ’12, Funchal, Madeira, Portugal, July 16-18, 2012 (2012), ACM), 185-194 · Zbl 1301.68120
[14] Hella, L.; Järvisalo, M.; Kuusisto, A.; Laurinharju, J.; Lempiäinen, T.; Luosto, K.; Suomela, J.; Virtema, J., Weak models of distributed computing, with connections to modal logic, Distrib. Comput., 28, 1, 31-53 (2015) · Zbl 1322.68075
[15] Immerman, N., Descriptive Complexity, Graduate Texts in Computer Science (1999), Springer · Zbl 0918.68031
[16] Kutrib, M., Cellular automata - a computational point of view, (New Developments in Formal Languages and Applications, vol. 113 (2008), Springer), 183-227 · Zbl 1156.68488
[17] Kutrib, M.; Malcher, A., Cellular automata with sparse communication, Theor. Comput. Sci., 411, 38-39, 3516-3526 (2010) · Zbl 1207.68214
[18] Kuusisto, A., Modal logic and distributed message passing automata, (Rocca, S. R.D., Computer Science Logic 2013 (CSL 2013). Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2-5, 2013, Torino, Italy. Computer Science Logic 2013 (CSL 2013). Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2-5, 2013, Torino, Italy, LIPIcs, vol. 23 (2013), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 452-468 · Zbl 1356.68154
[19] Kuusisto, A., Infinite networks, halting and local algorithms, (Peron, A.; Piazza, C., Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification. Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2014, Verona, Italy, September 10-12, 2014. Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification. Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2014, Verona, Italy, September 10-12, 2014, EPTCS, vol. 161 (2014)), 147-160 · Zbl 1467.68206
[20] Löding, C., Basics on tree automata, (D’Souza, D.; Shankar, P., Modern Applications of Automata Theory. Modern Applications of Automata Theory, IISc Research Monographs Series, vol. 2 (2012), World Scientific), 79-109 · Zbl 1256.68103
[21] Lutz, C.; Wolter, F., Non-uniform data complexity of query answering in description logics, (Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference. Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012 (2012)), 297-307
[22] Reiter, F., Distributed graph automata, (30th Annual ACM/IEEE Symposium on Logic in Computer Science. 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015 (2015), IEEE Computer Society), 192-201 · Zbl 1401.68166
[23] Reiter, F., Asynchronous distributed automata: a characterization of the modal mu-fragment, (Chatzigiannakis, I.; Indyk, P.; Kuhn, F.; Muscholl, A., 44th International Colloquium on Automata, Languages, and Programming. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017. 44th International Colloquium on Automata, Languages, and Programming. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, LIPIcs, vol. 80 (2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik Warsaw, Poland), 1-4 · Zbl 1442.68096
[24] Seidel, S. R., Language Recognition and the Synchronization of Cellular Automata (1979), Department of Computer Science, University of Iowa, Tech. Rep. 79-02
[25] Suomela, J., Survey of local algorithms, ACM Comput. Surv., 45, 2, 1-40 (2013) · Zbl 1293.68306
[26] Terrier, V., Language recognition by cellular automata, (Rozenberg, G.; Bäck, T.; Kok, J. N., Handbook of Natural Computing (2012), Springer), 123-158
[27] Vollmar, R., On cellular automata with a finite number of state changes, (Knödel, W.; Schneider, H. J., Parallel Processes and Related Automata, vol. 3 (1981), Springer: Springer Vienna), 181-191 · Zbl 0458.68013
[28] Zhuk, D., A proof of CSP dichotomy conjecture, (58th IEEE Annual Symposium on Foundations of Computer Science. 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 (2017)), 331-342
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.