4 Search Results for "Marli�re, Gr�gory"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.20
Locality Theorems in Semiring Semantics

Authors: Clotilde Bizière, Erich Grädel, and Matthias Naaf

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Semiring semantics of first-order logic generalises classical Boolean semantics by permitting truth values from a commutative semiring, which can model information such as costs or access restrictions. This raises the question to what extent classical model-theoretic properties still apply, and how this depends on the algebraic properties of the semiring. In this paper, we study this question for the classical locality theorems due to Hanf and Gaifman. We prove that Hanf’s locality theorem generalises to all semirings with idempotent operations, but fails for many non-idempotent semirings. We then consider Gaifman normal forms and show that for formulae with free variables, Gaifman’s theorem does not generalise beyond the Boolean semiring. Also for sentences, it fails in the natural semiring and the tropical semiring. Our main result, however, is a constructive proof of the existence of Gaifman normal forms for min-max and lattice semirings. The proof implies a stronger version of Gaifman’s classical theorem in Boolean semantics: every sentence has a Gaifman normal form which does not add negations.
Cite as

Clotilde Bizière, Erich Grädel, and Matthias Naaf. Locality Theorems in Semiring Semantics. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{biziere_et_al:LIPIcs.MFCS.2023.20,
  author =	{Bizi\`{e}re, Clotilde and Gr\"{a}del, Erich and Naaf, Matthias},
  title =	{{Locality Theorems in Semiring Semantics}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.20},
  URN =		{urn:nbn:de:0030-drops-185546},
  doi =		{10.4230/LIPIcs.MFCS.2023.20},
  annote =	{Keywords: Semiring semantics, Locality, First-order logic}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.52
Combinatorial Resultants in the Algebraic Rigidity Matroid

Authors: Goran Malić and Ileana Streinu

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid CM_n associated to the Cayley-Menger ideal for n points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from K₄ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Gröbner Basis calculation took 5 days and 6 hrs.
Cite as

Goran Malić and Ileana Streinu. Combinatorial Resultants in the Algebraic Rigidity Matroid. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{malic_et_al:LIPIcs.SoCG.2021.52,
  author =	{Mali\'{c}, Goran and Streinu, Ileana},
  title =	{{Combinatorial Resultants in the Algebraic Rigidity Matroid}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.52},
  URN =		{urn:nbn:de:0030-drops-138514},
  doi =		{10.4230/LIPIcs.SoCG.2021.52},
  annote =	{Keywords: Cayley-Menger ideal, rigidity matroid, circuit polynomial, combinatorial resultant, inductive construction, Gr\"{o}bner basis elimination}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.23
Real Time Railway Traffic Management Modeling Track-Circuits

Authors: Paola Pellegrini, Grégory Marlière, and Joaquin Rodriguez

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
The real time railway traffic management seeks for the train routing and scheduling that minimize delays after an unexpected event perturbs the operations. In this paper, we propose a mixed-integer linear programming formulation for tackling this problem, modeling the infrastructure in terms of track-circuits, which are the basic components for train detection. This formulation considers all possible alternatives for train rerouting in the infrastructure and all rescheduling alternatives for trains along these routes. To the best of our knowledge, we present the first formulation that solves this problem to optimality. We tested the proposed formulation on real perturbation instances representing traffic in a control area including the Lille Flandres station (France), achieving very good performance in terms of computation time.
Cite as

Paola Pellegrini, Grégory Marlière, and Joaquin Rodriguez. Real Time Railway Traffic Management Modeling Track-Circuits. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 23-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{pellegrini_et_al:OASIcs.ATMOS.2012.23,
  author =	{Pellegrini, Paola and Marli\`{e}re, Gr\'{e}gory and Rodriguez, Joaquin},
  title =	{{Real Time Railway Traffic Management Modeling Track-Circuits}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{23--34},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.23},
  URN =		{urn:nbn:de:0030-drops-37004},
  doi =		{10.4230/OASIcs.ATMOS.2012.23},
  annote =	{Keywords: real time railway traffic management, mixed-integer linear programming, track-circuit, complex junction}
}
Document
DOI: 10.4230/DFU.SciViz.2010.136
Illustrative Focus+Context Approaches in Interactive Volume Visualization

Authors: Stefan Bruckner, M. Eduard Gröller, Klaus Mueller, Bernhard Preim, and Deborah Silver

Published in: Dagstuhl Follow-Ups, Volume 1, Scientific Visualization: Advanced Concepts (2010)

Abstract
Illustrative techniques are a new and exciting direction in visualization research. Traditional techniques which have been used by scientific illustrators for centuries are re-examined under the light of modern computer technology. In this paper, we discuss the use of the focus+context concept for the illustrative visualization of volumetric data. We give an overview of the state-of-the-art and discuss recent approaches which employ this concept in novel ways.
Cite as

Stefan Bruckner, M. Eduard Gröller, Klaus Mueller, Bernhard Preim, and Deborah Silver. Illustrative Focus+Context Approaches in Interactive Volume Visualization. In Scientific Visualization: Advanced Concepts. Dagstuhl Follow-Ups, Volume 1, pp. 136-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InCollection{bruckner_et_al:DFU.SciViz.2010.136,
  author =	{Bruckner, Stefan and Gr\"{o}ller, M. Eduard and Mueller, Klaus and Preim, Bernhard and Silver, Deborah},
  title =	{{Illustrative Focus+Context Approaches in Interactive Volume Visualization}},
  booktitle =	{Scientific Visualization: Advanced Concepts},
  pages =	{136--162},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-19-4},
  ISSN =	{1868-8977},
  year =	{2010},
  volume =	{1},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.SciViz.2010.136},
  URN =		{urn:nbn:de:0030-drops-27023},
  doi =		{10.4230/DFU.SciViz.2010.136},
  annote =	{Keywords: Illustrative Visualization, Volumetric Data}
}
  • Refine by Author
  • 1 Bizière, Clotilde
  • 1 Bruckner, Stefan
  • 1 Grädel, Erich
  • 1 Gröller, M. Eduard
  • 1 Malić, Goran
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 General and reference → Experimentation
  • 1 General and reference → Performance
  • 1 Mathematics of computing → Mathematical software performance
  • Show More...

  • Refine by Keyword
  • 1 Cayley-Menger ideal
  • 1 First-order logic
  • 1 Gröbner basis elimination
  • 1 Illustrative Visualization
  • 1 Locality
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2010
  • 1 2012
  • 1 2021
  • 1 2023

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