- 1
- Marie-Pierre Béal, Dominique Perrin, Antonio Restivo, and Wolfgang Steiner.
Recognizability in S-adic shifts.
to appear in Israel. J. Math., 2024.
arXiv:2302.06258.
- 2
- Marie-Pierre Béal, Dominique Perrin, and Antonio Restivo.
Decidable problems in substitution shifts.
J. Comput. Syst. Sci., 143:103529, 2024.
arXiv:2112.14499.
- 3
- Marie-Pierre Béal, Dominique Perrin, and Antonio Restivo.
Recognizability of morphisms.
Erg. Theor. & Dyn. Sys., 43(11):3578–3602, 2023.
arXiv:2110.10267, doi:10.1017/etds.2022.109.
- 4
- Marie-Pierre Béal, Dominique Perrin, and Antonio Restivo.
Unambiguously coded systems.
European Journal of Combinatorics, pages 103812, 2023.
arXiv:2103.01012.
- 5
- Marie-Pierre Béal and Maxime Crochemore.
Fast detection of specific fragments against a set of sequences.
In 27th International Conference on Developments in Language Theory, DLT 2023, volume 13911 of Lecture Notes in Computer Science, 51–60. 2023.
arXiv:2208.03451.
- 6
- Marie-Pierre Béal and Maxime Crochemore.
Checking whether a word is Hamming-isometric in linear time.
Theor. Comput. Sci., pages 55–59, 2022.
arXiv:2106.10541.
- 7
- Marie-Pierre Béal, Jean Berstel, Soren Eilers, and Dominique Perrin.
Symbolic dynamics.
In Jean-Éric Pin, editor, Handbook of Automata Theory, volume II, chapter 27, pages 987–1031.
EMS Press, 2021.
arXiv:1006.1265.
- 8
- Marie-Pierre Béal, Valérie Berthé, Dominique Perrin, and Antonio Restivo.
A note on one-sided recognizable morphisms.
2022.
arXiv:2204.03892.
- 9
- Marie-Pierre Béal and Pavel Heller.
Shifts of k-nested sequences.
Theor. Comput. Sci., 658:18–26, 2017.
- 10
- Marie-Pierre Béal and Pavel Heller.
Generalized Dyck shifts.
In Pascal Weil, editor, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, volume 10304 of Lecture Notes in Computer Science, 99–111. Springer, 2017.
- 11
- Marie-Pierre Béal, Michel Blockelet, and Catalin Dima.
Sofic-Dyck shifts.
Theor. Comput. Sci., 609:226–244, 2016.
URL: http://dx.doi.org/10.1016/j.tcs.2015.09.027.
- 12
- Marie-Pierre Béal and Dominique Perrin.
A quadratic algorithm for road coloring.
Discrete Applied Mathematics, 169:15–29, 2014.
URL: http://dx.doi.org/10.1016/j.dam.2013.12.002, doi:10.1016/j.dam.2013.12.002.
- 13
- Nathalie Aubrun and Marie-Pierre Béal.
Tree algebra of sofic tree languages.
RAIRO - Theor. Inf. and Applic., 48(4):431–451, 2014.
URL: http://dx.doi.org/10.1051/ita/2014018.
- 14
- Marie-Pierre Béal, Michel Blockelet, and Catalin Dima.
Zeta functions of finite-type-Dyck shifts are N-algebraic.
In 2014 Information Theory and Applications Workshop, ITA 2014, San Diego, CA, USA, February 9-14, 2014, 1–8. 2014.
URL: http://dx.doi.org/10.1109/ITA.2014.6804286, doi:10.1109/ITA.2014.6804286.
- 15
- Marie-Pierre Béal, Michel Blockelet, and Catalin Dima.
Sofic-Dyck shifts.
In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, 63–74. 2014.
URL: http://dx.doi.org/10.1007/978-3-662-44522-8_6, doi:10.1007/978-3-662-44522-8_6.
- 16
- Marie-Pierre Béal and Olivier Carton, editors.
Developments in Language Theory - 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings, volume 7907 of Lecture Notes in Computer Science, Springer, 2013.
URL: http://dx.doi.org/10.1007/978-3-642-38771-5, doi:10.1007/978-3-642-38771-5.
- 17
- Nathalie Aubrun and Marie-Pierre Béal.
Sofic tree-shifts.
Theory Comput. Syst., pages 621–644, 2013.
URL: http://dx.doi.org/10.1007/s00224-013-9456-1.
- 18
- Eugene Asarin, Nicolas Basset, Marie-Pierre Béal, Aldric Degorre, and Dominique Perrin.
Toward a timed theory of channel coding.
In FORMATS, 27–42. 2012.
URL: http://dx.doi.org/10.1007/978-3-642-33365-1_4.
- 19
- Nathalie Aubrun and Marie-Pierre Béal.
Tree-shifts of finite type.
Theoret. Comput. Sci., 459:16–25, 2012.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/TCS2012final.pdf.
- 20
- Marie-Pierre Béal, Jean-Marc Champarnaud, Jean-Philippe Dubernard, Hadrien Jeanne, and Sylvain Lombardy.
Decidability of geometricity of regular languages.
In Developments in Language Theory, 62–72. 2012.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/geometriqueDLT2012.pdf.
- 21
- Marie-Pierre Béal, Maxime Crochemore, Bruce E. Moision, and Paul H. Siegel.
Periodic-finite-type shift spaces.
IEEE Trans. Inform. Theory, 57(6):3677–3691, 2011.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/Pftss_Second_Revision.pdf.
- 22
- Marie-Pierre Béal, Mikhail V. Berlinkov, and Dominique Perrin.
A quadratic upper bound on the size of a synchronizing word in one-cluster automata.
Int. J. Found. Comput. Sci., 22(2):277–288, 2011.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/cernyJournalFinal.pdf.
- 23
- Marie-Pierre Béal, Sylvain Lombardy, and Dominique Perrin.
Embeddings of local automata.
Illinois J. Math., 54(1):155–174, 2010.
URL: http://hal-univ-mlv.archives-ouvertes.fr/hal-00619770/en/.
- 24
- Nathalie Aubrun and Marie-Pierre Béal.
Sofic and almost of finite type tree-shifts.
In Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings, volume 6072 of Lecture Notes in Computer Science, 12–24. Springer, 2010.
URL: http://monge.univ-mlv.fr/~aubrun/articles/csr2010.pdf.
- 25
- Marie-Pierre Béal, Jean Berstel, Brian Marcus, Dominique Perrin, Christophe Reutenauer, and Paul H. Siegel.
Variable-length codes and finite automata.
In Subhas Chandra Misra Issac Woungang, Sudip Misra, editor, Selected topics in information and coding theory, chapter 14, pages 505–584.
World Scientific Publishing Company, 2010.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/2008handbookcodes.pdf.
- 26
- Nathalie Aubrun and Marie-Pierre Béal.
Decidability of conjugacy of tree shifts of finite type.
In 36th International Colloquium on Automata, Languages and Programming (ICALP'09), volume 5555 of Lecture Notes in Computer Science, 132–143. Springer-Verlag, July 2009.
URL: http://www.springerlink.com/content/k2568m1662kp06j5/fulltext.pdf.
- 27
- Marie-Pierre Béal and Dominique Perrin.
A quadratic upper bound on the size of a synchronizing word in one-cluster automata.
In Developments in Language Theory, 81–90. 2009.
URL: http://dx.doi.org/10.1007/978-3-642-02737-6_6.
- 28
- Marie-Pierre Béal, Fabio Burderi, and Antonio Restivo.
Coding partitions of regular sets.
Internat. J. Algebra Comput., 19(8):1011–1023, 2009.
URL: http://dx.doi.org/10.1142/S0218196709005457.
- 29
- Marie-Pierre Béal and Dominique Perrin.
Completing codes in a sofic shift.
Theoret. Comput. Science, 410(43):4423–4431, 2009.
URL: http://dx.doi.org/10.1016/j.tcs.2009.07.023.
- 30
- Marie-Pierre Béal, Sylvain Lombardy, and Dominique Perrin.
Embeddings of local automata.
In 2008 IEEE International Symposium on Information Theory, ISIT 2008, 2351–2355. 2008.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/completionLocal.pdf.
- 31
- Marie-Pierre Béal, Eugen Czeizler, Jarkko Kari, and Dominique Perrin.
Unambiguous automata.
Mathematics in Computer Science, 1(4):625–638, 2008.
URL: http://dx.doi.org/10.1007/s11786-007-0027-1.
- 32
- Marie-Pierre Béal and Maxime Crochemore.
Minimizing incomplete automata.
In Finite-State Methods and Natural Language Processing (FSMNLP'08), Joint Research Center, 9–16. 2008.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/minimizingIncomplete.pdf.
- 33
- Marie-Pierre Béal, Fabio Burderi, and Antonio Restivo.
Coding partitions: regularity, maximality, and global ambiguity.
In Tero Harju, Juhani Karhumäki, and Arto Lepistö, editors, Developments in Language Theory, 11th International Conference, DLT 2007, Turku, Finland, July 3-6, 2007, Proceedings, volume 4588 of Lecture Notes in Computer Science, 48–59. Springer, 2007.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/DLT07.pdf.
- 34
- Marie-Pierre Béal and Maxime Crochemore.
Minimizing local automata.
In 2007 IEEE International Symposium on Information Theory, ISIT 2007, 1376–1380. 2007.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/aftIEEE.pdf.
- 35
- Marie-Pierre Béal, Sylvain Lombardy, and Jacques Sakarovitch.
Conjugacy and equivalence of weighted automata and functional transducers.
In Computer Science - Theory and Applications (CSR'06), volume 3967 of Lecture Notes in Comput. Sci., 58–69. Berlin, 2006. Springer.
URL: http://igm.univ-mlv.fr/~lombardy/publi/CSR06.pdf.
- 36
- Marie-Pierre Béal and Dominique Perrin.
Complete codes in a sofic shift.
In STACS 2006, volume 3884 of Lecture Notes in Comput. Sci., 127–136. Berlin, 2006. Springer.
URL: http://hal-univ-mlv.archives-ouvertes.fr/docs/00/61/98/56/PDF/hal.pdf.
- 37
- Marie-Pierre Béal and Dominique Perrin.
Codes, unambiguous automata and sofic systems.
Theoret. Comput. Sci., 356(1-2):6–13, 2006.
URL: http://hal.archives-ouvertes.fr/hal-00619226/.
- 38
- Marie-Pierre Béal, Francesca Fiorenzi, and Dominique Perrin.
The syntactic graph of a sofic shift is invariant under shift equivalence.
Internat. J. Algebra Comput., 16(3):443–460, 2006.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/aftTCS.pdf.
- 39
- Marie-Pierre Béal, Francesca Fiorenzi, and Dominique Perrin.
A hierarchy of shift equivalent sofic shifts.
Theoret. Comput. Sci., 345:390–205, 2005.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/greenSTACS.pdf.
- 40
- Marie-Pierre Béal, Sylvain Lombardy, and Jacques Sakarovitch.
On the equivalence of ℤ-automata.
In Automata, languages and programming (ICALP, 2005), volume 3580 of Lecture Notes in Comput. Sci., 397–409. Berlin, 2005. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/icalp05-050429.pdf.
- 41
- Marie-Pierre Béal, Gabriele Fici, and Maxime Crochemore.
Presentations of constrained systems with unconstrained positions.
IEEE Trans. Inform. Theory, 41(5):381–393, 2005.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/unconstrained2bis.pdf.
- 42
- Marie-Pierre Béal and Dominique Perrin.
Codes and sofic constraints.
Theoret. Comput. Sci., 340(2):381–393, 2005.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/restivo.pdf.
- 43
- Marie-Pierre Béal, Francesca Fiorenzi, and Filippo Mignosi.
Minimal forbidden patterns of multi-dimensional shifts.
Internat. J. Algebra Comput., 15(1):73–93, 2005.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/bidimensional.pdf.
- 44
- Marie-Pierre Béal and Olivier Carton.
Determinization of transducers over infinite words: the general case.
Theory Comput. Syst., 37(4):483–502, 2004.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/det2.pdf.
- 45
- Marie-Pierre Béal, Francesca Fiorenzi, and Dominique Perrin.
A hierarchy of irreducible sofic shifts.
In Mathematical foundations of computer science MFCS'04, volume 3153 of Lecture Notes in Comput. Sci., 611–622. Berlin, 2004. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/aftMFCS.pdf.
- 46
- Marie-Pierre Béal, Anne Bergeron, Sylvie Corteel, and Mathieu Raffinot.
An algorithmic view of gene teams.
Theoret. Comput. Sci., 320(2-4):395–418, 2004.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/Fusion-geneteam.pdf.
- 47
- Marie-Pierre Béal, Francesca Fiorenzi, and Dominique Perrin.
The syntactic graph of a sofic shift.
In STACS 2004, volume 2996 of Lecture Notes in Comput. Sci., 282–293. Berlin, 2004. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/greenSTACS.pdf.
- 48
- Marie-Pierre Béal and Dominique Perrin.
On the generating sequences of regular languages on $k$-symbols.
J. ACM, 50(6):955–980 (electronic), 2003.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/kaire.pdf.
- 49
- Marie-Pierre Béal, Maxime Crochemore, Filippo Mignosi, Antonio Restivo, and Marinella Sciortino.
Computing forbidden words of regular languages.
Fund. Inform., 56(1-2):121–135, 2003.
Special issue on computing patterns in strings.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/fialgo.pdf.
- 50
- Marie-Pierre Béal.
Extensions of the method of poles for code construction.
IEEE Trans. Inform. Theory, 49(6):1516–1523, 2003.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/ieee.pdf.
- 51
- Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch.
Squaring transducers: an efficient procedure for deciding functionality and sequentiality.
Theoret. Comput. Sci., 292(1):45–63, 2003.
Selected papers in honor of Jean Berstel.
- 52
- Marie-Pierre Béal and Dominique Perrin.
A weak equivalence between shifts of finite type.
Adv. in Appl. Math., 29(2):162–171, 2002.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/faible.pdf.
- 53
- Marie-Pierre Béal and Dominique Perrin.
On the enumerative sequences of regular languages on $k$ symbols.
In H. Alt and A. Ferreira, editors, STACS 2002, volume 2285 of Lecture Notes in Comput. Sci., 547–558. Berlin, 2002. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/stacsFinal.pdf.
- 54
- Marie-Pierre Béal and Olivier Carton.
Determinization of transducers over finite and infinite words.
Theoret. Comput. Sci., 289(1):225–251, 2002.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/det1.pdf.
- 55
- Frédérique Bassino, Marie-Pierre Béal, and Dominique Perrin.
Length distributions and regular sequences.
In Joachim Rosenthal and Brian Marcus, editors, Codes, systems, and graphical models (Minneapolis, MN, 1999), volume 123 of IMA Vol. Math. Appl., 415–437. New York, 2001. Springer.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/ActesIma.pdf.
- 56
- Marie-Pierre Béal.
Codage symbolique.
PhD thesis, Université de Marne-la-Vallée, 2001.
Habilitation à diriger des recherches.
- 57
- Marie-Pierre Béal and Olivier Carton.
Asynchronous sliding block maps.
In Developments in language theory (Aachen, 1999), 47–59. River Edge, NJ, 2000. World Sci. Publishing.
- 58
- Marie-Pierre Béal and Olivier Carton.
Computing the prefix of an automaton.
Theor. Inform. Appl., 34(6):503–514, 2000.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/prefix.pdf.
- 59
- Marie-Pierre Béal and Olivier Carton.
Determinization of transducers over infinite words.
In U. Montanari and others, editors, ICALP 2000), volume 1853 of Lecture Notes in Comput. Sci., 561–570. Berlin, 2000. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/icalp00.pdf.
- 60
- Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch.
Squaring transducers: an efficient procedure for deciding functionality and sequentiality.
In G. Gonnet, D. Panario, and A. Viola, editors, LATIN'2000, volume 1776 of Lecture Notes in Comput. Sci. Springer, 2000.
- 61
- M.-P. Béal, F. Mignosi, A. Restivo, and M. Sciortino.
Forbidden words in symbolic dynamics.
Adv. in Appl. Math., 25(2):163–193, 2000.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/forbiddenWords.pdf.
- 62
- Marie-Pierre Béal and Olivier Carton.
Asynchronous sliding block maps.
Theor. Inform. Appl., 34(2):139–156, 2000.
- 63
- Frédérique Bassino, Marie-Pierre Béal, and Dominique Perrin.
A finite state version of the Kraft-McMillan theorem.
SIAM J. Comput., 30(4):1211–1230 (electronic), 2000.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/siamfinal.pdf.
- 64
- Frédérique Bassino, Marie-Pierre Béal, and Dominique Perrin.
Enumerative sequences of leaves and nodes in rational trees.
Theoret. Comput. Sci., 221(1-2):41–60, 1999.
ICALP '97 (Bologna).
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/serielong.pdf.
- 65
- Marie-Pierre Béal.
On rotationally invariant codes.
Technical Report 98-13, Institut Gaspard-Monge, 1998.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/rotation.pdf.
- 66
- Frédérique Bassino, Marie-Pierre Béal, and Dominique Perrin.
Super-state automata and rational trees.
In LATIN'98: theoretical informatics (Campinas, 1998), volume 1380 of Lecture Notes in Comput. Sci., 42–52. Berlin, 1998. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/latin.pdf.
- 67
- Marie-Pierre Béal and Jean Senellart.
On the bound of the synchronization delay of a local automaton.
Theoret. Comput. Sci., 205(1-2):297–306, 1998.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/echelle.pdf.
- 68
- Frédérique Bassino, Marie-Pierre Béal, and Dominique Perrin.
Enumerative sequences of leaves in rational trees.
In ICALP'97: Automata, languages and programming (Bologna, 1997), volume 1256 of Lecture Notes in Comput. Sci., 76–86. Berlin, 1997. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/ical97.pdf.
- 69
- Marie-Pierre Béal and Dominique Perrin.
Symbolic dynamics and finite automata.
In Handbook of formal languages, Vol. 2, pages 463–505.
Springer, Berlin, 1997.
URL: http://igm.univ-mlv.fr/~beal/Recherche/Publications/miseAJourHandbook.pdf.
- 70
- Marie-Pierre Béal, Olivier Carton, and Christophe Reutenauer.
Cyclic languages and strongly cyclic languages.
In STACS 96 (Grenoble, 1996), volume 1046 of Lecture Notes in Comput. Sci., 49–59. Berlin, 1996. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/cycliques.pdf.
- 71
- Marie-Pierre Béal, Filippo Mignosi, and Antonio Restivo.
Minimal forbidden words and symbolic dynamics.
In STACS 96 (Grenoble, 1996), volume 1046 of Lecture Notes in Comput. Sci., 555–566. Berlin, 1996. Springer.
URL: http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/mignosi_stacs2.pdf.
- 72
- Marie-Pierre Béal.
Puissance extérieure d'un automate déterministe, application au calcul de la fonction zêta d'un système sofique.
RAIRO Inform. Théor. Appl., 29(2):85–103, 1995.
- 73
- Jonathan Ashley and Marie-Pierre Béal.
A note on the method of poles for code construction.
IEEE Trans. Inform. Theory, 40(2):512–517, 1994.
- 74
- Marie-Pierre Béal.
Codage symbolique.
Masson, 1993.
- 75
- Jonathan Ashley and Marie-Pierre Béal.
Codage dans certains systèmes dynamiques symboliques.
In Actes des Journées Montoises 1990, 1–4. Université de Mons-Hainaut, 1990.
- 76
- Marie-Pierre Béal.
The method of poles: a coding method for constrained channels.
IEEE Trans. Inform. Theory, 36(4):763–772, 1990.
- 77
- Marie-Pierre Béal.
Codes circulaires, automates locaux et entropie.
Theoret. Comput. Sci., 57(2-3):283–302, 1988.
- 78
- Marie-Pierre Béal.
Au sujet du premier théorème d'Adler sur l'équivalence de deux systèmes de type fini de même entropie.
Technical Report 88-38, LITP, 1988.
- 79
- Marie-Pierre Béal.
Codage, automates locaux et entropie.
Thesis, Université Paris 7, 1987.
- 80
- Marie-Pierre Béal and Dominique Perrin.
Une caractérisation des ensembles sofiques.
C. R. Acad. Sci. Paris Sér. I Math., 303(6):255–257, 1986.