5 Search Results for "Fox, Jorge"


Document
Practical Computation of Graph VC-Dimension

Authors: David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)


Abstract
For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G = (V,E), the VC-dimension of G is defined as the VC-dimension of (V, N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v ∈ V in G. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.

Cite as

David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8,
  author =	{Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent},
  title =	{{Practical Computation of Graph VC-Dimension}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8},
  URN =		{urn:nbn:de:0030-drops-203731},
  doi =		{10.4230/LIPIcs.SEA.2024.8},
  annote =	{Keywords: VC-dimension, graph, algorithm}
}
Document
Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)

Authors: James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter

Published in: Dagstuhl Manifestos, Volume 10, Issue 1 (2024)


Abstract
Knowledge Representation and Reasoning is a central, longstanding, and active area of Artificial Intelligence. Over the years it has evolved significantly; more recently it has been challenged and complemented by research in areas such as machine learning and reasoning under uncertainty. In July 2022,sser a Dagstuhl Perspectives workshop was held on Knowledge Representation and Reasoning. The goal of the workshop was to describe the state of the art in the field, including its relation with other areas, its shortcomings and strengths, together with recommendations for future progress. We developed this manifesto based on the presentations, panels, working groups, and discussions that took place at the Dagstuhl Workshop. It is a declaration of our views on Knowledge Representation: its origins, goals, milestones, and current foci; its relation to other disciplines, especially to Artificial Intelligence; and on its challenges, along with key priorities for the next decade.

Cite as

James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter. Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282). In Dagstuhl Manifestos, Volume 10, Issue 1, pp. 1-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@Article{delgrande_et_al:DagMan.10.1.1,
  author =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  title =	{{Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)}},
  pages =	{1--61},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2024},
  volume =	{10},
  number =	{1},
  editor =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagMan.10.1.1},
  URN =		{urn:nbn:de:0030-drops-201403},
  doi =		{10.4230/DagMan.10.1.1},
  annote =	{Keywords: Knowledge representation and reasoning, Applications of logics, Declarative representations, Formal logic}
}
Document
Survey
Semantic Web: Past, Present, and Future

Authors: Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1


Abstract
Ever since the vision was formulated, the Semantic Web has inspired many generations of innovations. Semantic technologies have been used to share vast amounts of information on the Web, enhance them with semantics to give them meaning, and enable inference and reasoning on them. Throughout the years, semantic technologies, and in particular knowledge graphs, have been used in search engines, data integration, enterprise settings, and machine learning. In this paper, we recap the classical concepts and foundations of the Semantic Web as well as modern and recent concepts and applications, building upon these foundations. The classical topics we cover include knowledge representation, creating and validating knowledge on the Web, reasoning and linking, and distributed querying. We enhance this classical view of the so-called "Semantic Web Layer Cake" with an update of recent concepts that include provenance, security and trust, as well as a discussion of practical impacts from industry-led contributions. We conclude with an outlook on the future directions of the Semantic Web. This is a living document. If you like to contribute, please contact the first author and visit: https://github.com/ascherp/semantic-web-primer

Cite as

Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal. Semantic Web: Past, Present, and Future. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 3:1-3:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@Article{scherp_et_al:TGDK.2.1.3,
  author =	{Scherp, Ansgar and Groener, Gerd and \v{S}koda, Petr and Hose, Katja and Vidal, Maria-Esther},
  title =	{{Semantic Web: Past, Present, and Future}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:37},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.3},
  URN =		{urn:nbn:de:0030-drops-198607},
  doi =		{10.4230/TGDK.2.1.3},
  annote =	{Keywords: Linked Open Data, Semantic Web Graphs, Knowledge Graphs}
}
Document
A Framework for Analyzing Composition of Security Aspects

Authors: Jorge Fox and Jan Juerjens

Published in: Dagstuhl Seminar Proceedings, Volume 6351, Methods for Modelling Software Systems (MMOSS) (2007)


Abstract
The methodology of aspect-oriented software engineering has been proposed to factor out concerns that are orthogonal to the core functionality of a system. In particular, this is a useful approach to handling the difficulties of integrating non-functional requirements such as security into complex software systems. Doing so correctly and securely, however, still remains a non-trivial task. For example, one has to make sure that the "weaving" process actually enforces the aspects needed. This is highly non-obvious especially in the case of security, since different security aspects may actually contradict each other, in which case they cannot be woven in a sequential way without destroying each other. To address these problems, this paper introduces a framework for the aspect-oriented development of secure software using composition filters at the model level. Using an underlying foundation based on streamprocessing functions, we explore under which conditions security properties are preserved when composed as filters. Thanks to this foundation we may also rely on model level verification tools and on code and model weaving to remedy security failures. Our approach is explained using as case-studies a web banking application developed by a major German bank and a webstore design.

Cite as

Jorge Fox and Jan Juerjens. A Framework for Analyzing Composition of Security Aspects. In Methods for Modelling Software Systems (MMOSS). Dagstuhl Seminar Proceedings, Volume 6351, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{fox_et_al:DagSemProc.06351.3,
  author =	{Fox, Jorge and Juerjens, Jan},
  title =	{{A Framework for Analyzing Composition of Security Aspects}},
  booktitle =	{Methods for Modelling Software Systems (MMOSS)},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6351},
  editor =	{Ed Brinksma and David Harel and Angelika Mader and Perdita Stevens and Roel Wieringa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06351.3},
  URN =		{urn:nbn:de:0030-drops-8594},
  doi =		{10.4230/DagSemProc.06351.3},
  annote =	{Keywords: Aspects in software engineering, aspect interference, verification, semantics, formal methods}
}
Document
A Taxonomy of Aspects in Terms of Crosscutting Concerns

Authors: Jorge Fox

Published in: Dagstuhl Seminar Proceedings, Volume 6351, Methods for Modelling Software Systems (MMOSS) (2007)


Abstract
Aspect-orientation provides support for " Separation of Concerns" by means of techniques that first isolate and then weave concerns. Most work in aspect-orientation has achieved such goals at the programming level, even also at the modeling level. Though, in some cases the application of these techniques is independent of the problem itself. In other words, the techniques for weaving either code or models are in principle applicable to a number of problems without a clear criterion to answer questions like: in what software processes we may actually discuss aspect-orientation? This also brings other questions: what do we consider an aspect?, how do we deal with it?, are aspects crosscutting concerns? The first notions of aspect-orientation relate to crosscutting in code. We consider this a bottom-up approach. We believe though, that aspect-orientation can be better understood from an architectural perspective. We call this a top-down approach. We explore the question of ''what makes an aspect an aspect" and '' when do aspects arise" from a top-down perspective. This work relates to a definition of aspects in terms of requirements traceability, proposes a classification, and altogether a taxonomy.

Cite as

Jorge Fox. A Taxonomy of Aspects in Terms of Crosscutting Concerns. In Methods for Modelling Software Systems (MMOSS). Dagstuhl Seminar Proceedings, Volume 6351, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{fox:DagSemProc.06351.5,
  author =	{Fox, Jorge},
  title =	{{A Taxonomy of Aspects in Terms of Crosscutting Concerns}},
  booktitle =	{Methods for Modelling Software Systems (MMOSS)},
  pages =	{1--27},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6351},
  editor =	{Ed Brinksma and David Harel and Angelika Mader and Perdita Stevens and Roel Wieringa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06351.5},
  URN =		{urn:nbn:de:0030-drops-8603},
  doi =		{10.4230/DagSemProc.06351.5},
  annote =	{Keywords: Aspect-orientation, Software Engineering, Taxonomy}
}
  • Refine by Author
  • 2 Fox, Jorge
  • 1 Coudert, David
  • 1 Csikós, Mónika
  • 1 Delgrande, James P.
  • 1 Ducoffe, Guillaume
  • Show More...

  • Refine by Classification
  • 2 Computing methodologies → Knowledge representation and reasoning
  • 1 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Ontology engineering
  • 1 Information systems → Information integration
  • 1 Information systems → Markup languages
  • Show More...

  • Refine by Keyword
  • 1 Applications of logics
  • 1 Aspect-orientation
  • 1 Aspects in software engineering
  • 1 Declarative representations
  • 1 Formal logic
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 3 2024
  • 2 2007