Synchronizing deterministic push-down automata can be really hard. (English) Zbl 07798816
MSC:
68Qxx
Found 20 Documents (Results 1–20)
Synchronization of Parikh automata. (English) Zbl 07766938
Drewes, Frank (ed.) et al., Developments in language theory. 27th international conference, DLT 2023, Umeå, Sweden, June 12–16, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13911, 113-127 (2023).
MSC:
68Q45
Primitivity and Hurwitz primitivity of nonnegative matrix tuples: a unified approach. (English) Zbl 1516.15021
Reviewer: Juan Ramón Torregrosa Sánchez (Valencia)
Synchronizing words and monoid factorization, yielding a new parameterized complexity class? (English) Zbl 07618926
Some results concerning careful synchronization of partial automata and subset synchronization of DFA’s. (English) Zbl 07572315
Caron, Pascal (ed.) et al., Implementation and application of automata. 26th international conference, CIAA 2022, Rouen, France, June 28 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13266, 106-115 (2022).
MSC:
68Q45
Distributed graph problems through an automata-theoretic Lens. (English) Zbl 07495132
Jurdziński, Tomasz (ed.) et al., Structural information and communication complexity. 28th international colloquium, SIROCCO 2021, Wrocław, Poland, June 28 – July 1, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12810, 31-49 (2021).
Synchronizing series-parallel deterministic finite automata with loops and related problems. (English) Zbl 1508.68186
Synchronizing deterministic push-down automata can be really hard. (English) Zbl 07559404
Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 33, 15 p. (2020).
MSC:
68Qxx
Computational complexity of synchronization under regular constraints. (English) Zbl 1541.68194
Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 63, 14 p. (2019).
A forgotten theory of proofs? (English) Zbl 1509.03157
MSC:
03F03
On automata recognizing birecurrent sets. (English) Zbl 1412.68135
Reviewer: Andreas Maletti (Leipzig)
Complexity of preimage problems for deterministic finite automata. (English) Zbl 1512.68134
Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 32, 14 p. (2018).
Controlling a population. (English) Zbl 1437.68175
Meyer, Roland (ed.) et al., 28th international conference on concurrency theory. CONCUR 2017, Berlin, Germany, September 5–8, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 85, Article 12, 16 p. (2017).
Synchronizing automata over nested words. (English) Zbl 1475.68148
Jacobs, Bart (ed.) et al., Foundations of software science and computation structures. 19th international conference, FOSSACS 2016, held as part of the European joint conferences on theory and practice of software, ETAPS 2016, Eindhoven, The Netherlands, April 2–8, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9634, 252-268 (2016).
Filter Results by …
Document Type
- Journal Articles (12)
- Collection Articles (8)
all
top 5
Author
- Fernau, Henning (5)
- Wolf, Petra (3)
- Berlinkov, Mikhail V. (2)
- Bruchertseifer, Jens (2)
- Chang, Yi-Jun (2)
- Ferens, Robert (2)
- Gusev, Vladimir Valer’evich (2)
- Hoffmann, Stefan (2)
- Shirmohammadi, Mahsa (2)
- Studený, Jan (2)
- Suomela, Jukka (2)
- Szykuła, Marek (2)
- Volkov, Mikhail Vladimirovich (2)
- Yamakami, Tomoyuki (2)
- Bertrand, Nathalie (1)
- Chistikov, Dmitry V. (1)
- Dewaskar, Miheer (1)
- Doyen, Laurent (1)
- Engeler, Erwin (1)
- Genest, Blaise (1)
- Gerencsér, Balázs (1)
- Gimbert, Hugo (1)
- Holzer, Markus (1)
- Jungers, Raphaël M. (1)
- Martyugin, Pavel V. (1)
- Maslennikova, Marina I. (1)
- Massart, Thierry Jacques (1)
- Ruszil, Jakub (1)
- Ryzhikov, Andrew (1)
- Shabana, Hanan (1)
- Wu, Yaokun (1)
- Zhu, Yinfeng (1)
