Search Results

Documents authored by Grandjean, Étienne

Found 2 Possible Name Variants:

Grandjean, Étienne

Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.8
Conjunctive Grammars, Cellular Automata and Logic

Authors: Théo Grente and Étienne Grandjean

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognized by real-time one-dimensional one-way cellular automata. We prove two weakened versions of the open question Conj ⊆? RealTime1CA, where RealTime1CA is the class of languages recognized by real-time one-dimensional two-way cellular automata: 1) it is true for unary languages; 2) Conj ⊆ RealTime2OCA, i.e. any conjunctive language is recognized by a real-time two-dimensional one-way cellular automaton. Interestingly, we express the rules of a conjunctive grammar in two Horn logics, which exactly characterize the complexity classes RealTime1CA and RealTime2OCA.
Cite as

Théo Grente and Étienne Grandjean. Conjunctive Grammars, Cellular Automata and Logic. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grente_et_al:OASIcs.AUTOMATA.2021.8,
  author =	{Grente, Th\'{e}o and Grandjean, \'{E}tienne},
  title =	{{Conjunctive Grammars, Cellular Automata and Logic}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{8:1--8:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.8},
  URN =		{urn:nbn:de:0030-drops-140170},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.8},
  annote =	{Keywords: Computational complexity, Real-time, One-dimensional/two-dimensional cellular automaton, One-way/two-way communication, Grid-circuit, Unary language, Descriptive complexity, Existential second-order logic, Horn formula}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.99
Definability by Horn Formulas and Linear Time on Cellular Automata

Authors: Nicolas Bacquey, Etienne Grandjean, and Frédéric Olive

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We establish an exact logical characterization of linear time complexity of cellular automata of dimension d, for any fixed d: a set of pictures of dimension d belongs to this complexity class iff it is definable in existential second-order logic restricted to monotonic Horn formulas with built-in successor function and d+1 first-order variables. This logical characterization is optimal modulo an open problem in parallel complexity. Furthermore, its proof provides a systematic method for transforming an inductive formula defining some problem into a cellular automaton that computes it in linear time.
Cite as

Nicolas Bacquey, Etienne Grandjean, and Frédéric Olive. Definability by Horn Formulas and Linear Time on Cellular Automata. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 99:1-99:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bacquey_et_al:LIPIcs.ICALP.2017.99,
  author =	{Bacquey, Nicolas and Grandjean, Etienne and Olive, Fr\'{e}d\'{e}ric},
  title =	{{Definability by Horn Formulas and Linear Time on Cellular Automata}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{99:1--99:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.99},
  URN =		{urn:nbn:de:0030-drops-74174},
  doi =		{10.4230/LIPIcs.ICALP.2017.99},
  annote =	{Keywords: picture languages, linear time, cellular automata of any dimension, local induction, descriptive complexity, second-order logic, horn formulas, logic}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.274
Descriptive complexity for pictures languages

Authors: Etienne Grandjean and Frédéric Olive

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
This paper deals with logical characterizations of picture languages of any dimension by syntactical fragments of existential second-order logic. Two classical classes of picture languages are studied: - the class of "recognizable" picture languages, i.e. projections of languages defined by local constraints (or tilings): it is known as the most robust class extending the class of regular languages to any dimension; - the class of picture languages recognized on "nondeterministic cellular automata in linear time" : cellular automata are the simplest and most natural model of parallel computation and linear time is the minimal time-bounded class allowing synchronization of nondeterministic cellular automata. We uniformly generalize to any dimension the characterization by Giammarresi et al. (1996) of the class of "recognizable" picture languages in existential monadic second-order logic. We state several logical characterizations of the class of picture languages recognized in linear time on nondeterministic cellular automata. They are the first machine-independent characterizations of complexity classes of cellular automata. Our characterizations are essentially deduced from normalization results we prove for first-order and existential second-order logics over pictures. They are obtained in a general and uniform framework that allows to extend them to other "regular" structures.
Cite as

Etienne Grandjean and Frédéric Olive. Descriptive complexity for pictures languages. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 274-288, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.CSL.2012.274,
  author =	{Grandjean, Etienne and Olive, Fr\'{e}d\'{e}ric},
  title =	{{Descriptive complexity for pictures languages}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{274--288},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.274},
  URN =		{urn:nbn:de:0030-drops-36783},
  doi =		{10.4230/LIPIcs.CSL.2012.274},
  annote =	{Keywords: Picture languages, locality and tiling, recognizability, linear time, cellular automata, logical characterizations, second-order logic}
}

Grandjean, Etienne

Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.8
Conjunctive Grammars, Cellular Automata and Logic

Authors: Théo Grente and Étienne Grandjean

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognized by real-time one-dimensional one-way cellular automata. We prove two weakened versions of the open question Conj ⊆? RealTime1CA, where RealTime1CA is the class of languages recognized by real-time one-dimensional two-way cellular automata: 1) it is true for unary languages; 2) Conj ⊆ RealTime2OCA, i.e. any conjunctive language is recognized by a real-time two-dimensional one-way cellular automaton. Interestingly, we express the rules of a conjunctive grammar in two Horn logics, which exactly characterize the complexity classes RealTime1CA and RealTime2OCA.
Cite as

Théo Grente and Étienne Grandjean. Conjunctive Grammars, Cellular Automata and Logic. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grente_et_al:OASIcs.AUTOMATA.2021.8,
  author =	{Grente, Th\'{e}o and Grandjean, \'{E}tienne},
  title =	{{Conjunctive Grammars, Cellular Automata and Logic}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{8:1--8:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.8},
  URN =		{urn:nbn:de:0030-drops-140170},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.8},
  annote =	{Keywords: Computational complexity, Real-time, One-dimensional/two-dimensional cellular automaton, One-way/two-way communication, Grid-circuit, Unary language, Descriptive complexity, Existential second-order logic, Horn formula}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.99
Definability by Horn Formulas and Linear Time on Cellular Automata

Authors: Nicolas Bacquey, Etienne Grandjean, and Frédéric Olive

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We establish an exact logical characterization of linear time complexity of cellular automata of dimension d, for any fixed d: a set of pictures of dimension d belongs to this complexity class iff it is definable in existential second-order logic restricted to monotonic Horn formulas with built-in successor function and d+1 first-order variables. This logical characterization is optimal modulo an open problem in parallel complexity. Furthermore, its proof provides a systematic method for transforming an inductive formula defining some problem into a cellular automaton that computes it in linear time.
Cite as

Nicolas Bacquey, Etienne Grandjean, and Frédéric Olive. Definability by Horn Formulas and Linear Time on Cellular Automata. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 99:1-99:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bacquey_et_al:LIPIcs.ICALP.2017.99,
  author =	{Bacquey, Nicolas and Grandjean, Etienne and Olive, Fr\'{e}d\'{e}ric},
  title =	{{Definability by Horn Formulas and Linear Time on Cellular Automata}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{99:1--99:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.99},
  URN =		{urn:nbn:de:0030-drops-74174},
  doi =		{10.4230/LIPIcs.ICALP.2017.99},
  annote =	{Keywords: picture languages, linear time, cellular automata of any dimension, local induction, descriptive complexity, second-order logic, horn formulas, logic}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.274
Descriptive complexity for pictures languages

Authors: Etienne Grandjean and Frédéric Olive

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
This paper deals with logical characterizations of picture languages of any dimension by syntactical fragments of existential second-order logic. Two classical classes of picture languages are studied: - the class of "recognizable" picture languages, i.e. projections of languages defined by local constraints (or tilings): it is known as the most robust class extending the class of regular languages to any dimension; - the class of picture languages recognized on "nondeterministic cellular automata in linear time" : cellular automata are the simplest and most natural model of parallel computation and linear time is the minimal time-bounded class allowing synchronization of nondeterministic cellular automata. We uniformly generalize to any dimension the characterization by Giammarresi et al. (1996) of the class of "recognizable" picture languages in existential monadic second-order logic. We state several logical characterizations of the class of picture languages recognized in linear time on nondeterministic cellular automata. They are the first machine-independent characterizations of complexity classes of cellular automata. Our characterizations are essentially deduced from normalization results we prove for first-order and existential second-order logics over pictures. They are obtained in a general and uniform framework that allows to extend them to other "regular" structures.
Cite as

Etienne Grandjean and Frédéric Olive. Descriptive complexity for pictures languages. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 274-288, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.CSL.2012.274,
  author =	{Grandjean, Etienne and Olive, Fr\'{e}d\'{e}ric},
  title =	{{Descriptive complexity for pictures languages}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{274--288},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.274},
  URN =		{urn:nbn:de:0030-drops-36783},
  doi =		{10.4230/LIPIcs.CSL.2012.274},
  annote =	{Keywords: Picture languages, locality and tiling, recognizability, linear time, cellular automata, logical characterizations, second-order logic}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact