28 Search Results for "Taylor, Peter"


Document
Practical Minimum Path Cover

Authors: Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu

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


Abstract
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to solve the problem by a simple reduction to minimum flow, recent theoretical advances exploit this idea to obtain algorithms parameterized by the number of paths of an MPC, known as the width. These results obtain fast [Mäkinen et al., TALG 2019] and even linear time [Cáceres et al., SODA 2022] algorithms in the small-width regime. In this paper, we present the first publicly available high-performance implementation of state-of-the-art MPC algorithms, including the parameterized approaches. Our experiments on random DAGs show that parameterized algorithms are orders-of-magnitude faster on dense graphs. Additionally, we present new fast pre-processing heuristics based on transitive edge sparsification. We show that our heuristics improve MPC-solvers by orders of magnitude.

Cite as

Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu. Practical Minimum Path Cover. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{caceres_et_al:LIPIcs.SEA.2024.3,
  author =	{C\'{a}ceres, Manuel and Mumey, Brendan and Toivonen, Santeri and Tomescu, Alexandru I.},
  title =	{{Practical Minimum Path Cover}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{3:1--3:19},
  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.3},
  URN =		{urn:nbn:de:0030-drops-203687},
  doi =		{10.4230/LIPIcs.SEA.2024.3},
  annote =	{Keywords: minimum path cover, directed acyclic graph, maximum flow, parameterized algorithms, edge sparsification, algorithm engineering}
}
Document
Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs

Authors: Daniel Hambly, Rhyd Lewis, and Padraig Corcoran

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


Abstract
In this paper, we examine the NP-hard problem of identifying fixed-length s-t paths in edge-weighted graphs - that is, a path of a desired length k from a source vertex s to a target vertex t. Many existing strategies look at paths whose lengths are determined by the number of edges in the path. We, however, look at the length of the path as the sum of the edge weights. Here, three exact algorithms for this problem are proposed: the first based on an integer programming (IP) formulation, the second a backtracking algorithm, and the third based on an extension of Yen’s algorithm. Analysis of these algorithms on random graphs shows that the backtracking algorithm performs best on smaller values of k, whilst the IP is preferable for larger values of k.

Cite as

Daniel Hambly, Rhyd Lewis, and Padraig Corcoran. Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 15:1-15:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{hambly_et_al:LIPIcs.SEA.2024.15,
  author =	{Hambly, Daniel and Lewis, Rhyd and Corcoran, Padraig},
  title =	{{Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{15:1--15:11},
  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.15},
  URN =		{urn:nbn:de:0030-drops-203805},
  doi =		{10.4230/LIPIcs.SEA.2024.15},
  annote =	{Keywords: Graphs, paths, backtracking, integer programming, Yen’s algorithm}
}
Document
Engineering A* Search for the Flip Distance of Plane Triangulations

Authors: Philip Mayer and Petra Mutzel

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


Abstract
The flip distance for two triangulations of a point set is defined as the smallest number of edge flips needed to transform one triangulation into another, where an edge flip is the act of replacing an edge of a triangulation by a different edge such that the result remains a triangulation. We adapt and engineer a sophisticated A* search algorithm acting on the so-called flip graph. In particular, we prove that previously proposed lower bounds for the flip distance form consistent heuristics for A* and show that they can be computed efficiently using dynamic algorithms. As an alternative approach, we present an integer linear program (ILP) for the flip distance problem. We experimentally evaluate our approaches on a new real-world benchmark data set based on an application in geodesy, namely sea surface reconstruction. Our evaluation reveals that A* search consistently outperforms our ILP formulation as well as a naive baseline, which is bidirectional breadth-first search. In particular, the runtime of our approach improves upon the baseline by more than two orders of magnitude. Furthermore, our A* search successfully solves most of the considered sea surface instances with up to 41 points. This is a substantial improvement compared to the baseline, which struggles with subsets of the real-world data of size 25. Lastly, to allow the consideration of global sea level data, we developed a decomposition-based heuristic for the flip distance. In our experiments it yields optimal flip distance values for most of the considered sea level data and it can be applied to large data sets due to its fast runtime.

Cite as

Philip Mayer and Petra Mutzel. Engineering A* Search for the Flip Distance of Plane Triangulations. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{mayer_et_al:LIPIcs.SEA.2024.23,
  author =	{Mayer, Philip and Mutzel, Petra},
  title =	{{Engineering A* Search for the Flip Distance of Plane Triangulations}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-203887},
  doi =		{10.4230/LIPIcs.SEA.2024.23},
  annote =	{Keywords: Computational Geometry, Triangulations, Flip Distance, A-star Search, Integer Linear Programming}
}
Document
Improved Cut Strategy for Tensor Network Contraction Orders

Authors: Christoph Staudt, Mark Blacher, Julien Klaus, Farin Lippmann, and Joachim Giesen

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


Abstract
In the field of quantum computing, simulating quantum systems on classical computers is crucial. Tensor networks are fundamental in simulating quantum systems. A tensor network is a collection of tensors, that need to be contracted into a result tensor. Tensor contraction is a generalization of matrix multiplication to higher order tensors. The contractions can be performed in different orders, and the order has a significant impact on the number of floating point operations (flops) needed to get the result tensor. It is known that finding an optimal contraction order is NP-hard. The current state-of-the-art approach for finding efficient contraction orders is to combinine graph partitioning with a greedy strategy. Although heavily used in practice, the current approach ignores so-called free indices, chooses node weights without regarding previous computations, and requires numerous hyperparameters that need to be tuned at runtime. In this paper, we address these shortcomings by developing a novel graph cut strategy. The proposed modifications yield contraction orders that significantly reduce the number of flops in the tensor contractions compared to the current state of the art. Moreover, by removing the need for hyperparameter tuning at runtime, our approach converges to an efficient solution faster, which reduces the required optimization time by at least an order of magnitude.

Cite as

Christoph Staudt, Mark Blacher, Julien Klaus, Farin Lippmann, and Joachim Giesen. Improved Cut Strategy for Tensor Network Contraction Orders. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{staudt_et_al:LIPIcs.SEA.2024.27,
  author =	{Staudt, Christoph and Blacher, Mark and Klaus, Julien and Lippmann, Farin and Giesen, Joachim},
  title =	{{Improved Cut Strategy for Tensor Network Contraction Orders}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{27:1--27:19},
  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.27},
  URN =		{urn:nbn:de:0030-drops-203924},
  doi =		{10.4230/LIPIcs.SEA.2024.27},
  annote =	{Keywords: tensor network, contraction order, graph partitioniong, quantum simulation}
}
Document
Invited Talk
Meaningfulness and Genericity in a Subsuming Framework (Invited Talk)

Authors: Delia Kesner, Victor Arrial, and Giulio Guerrieri

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)


Abstract
This paper studies the notion of meaningfulness for a unifying framework called dBang-calculus, which subsumes both call-by-name (dCBN) and call-by-value (dCBV). We first define meaningfulness in dBang and then characterize it by means of typability and inhabitation in an associated non-idempotent intersection type system previously appearing in the literature. We validate the proposed notion of meaningfulness by showing two properties: (1) consistency of the smallest theory, called ℋ, equating all meaningless terms, and (2) genericity, stating that meaningless subterms have no bearing on the significance of meaningful terms. The theory ℋ is also shown to have a unique consistent and maximal extension ℋ*, which coincides with a well-known notion of observational equivalence. Last but not least, we show that the notions of meaningfulness and genericity in the literature for dCBN and dCBV are subsumed by the corresponding ones proposed here for the dBang-calculus.

Cite as

Delia Kesner, Victor Arrial, and Giulio Guerrieri. Meaningfulness and Genericity in a Subsuming Framework (Invited Talk). In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{kesner_et_al:LIPIcs.FSCD.2024.1,
  author =	{Kesner, Delia and Arrial, Victor and Guerrieri, Giulio},
  title =	{{Meaningfulness and Genericity in a Subsuming Framework}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.1},
  URN =		{urn:nbn:de:0030-drops-203305},
  doi =		{10.4230/LIPIcs.FSCD.2024.1},
  annote =	{Keywords: Lambda calculus, Solvability, Meaningfulness, Inhabitation, Genericity}
}
Document
The Flower Calculus

Authors: Pablo Donato

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)


Abstract
We introduce the flower calculus, a deep inference proof system for intuitionistic first-order logic inspired by Peirce’s existential graphs. It works as a rewriting system over inductive objects called "flowers", that enjoy both a graphical interpretation as topological diagrams, and a textual presentation as nested sequents akin to coherent formulas. Importantly, the calculus dispenses completely with the traditional notion of symbolic connective, operating solely on nested flowers containing atomic predicates. We prove both the soundness of the full calculus and the completeness of an analytic fragment with respect to Kripke semantics. This provides to our knowledge the first analyticity result for a proof system based on existential graphs, adapting semantic cut-elimination techniques to a deep inference setting. Furthermore, the kernel of rules targetted by completeness is fully invertible, a desirable property for both automated and interactive proof search.

Cite as

Pablo Donato. The Flower Calculus. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{donato:LIPIcs.FSCD.2024.5,
  author =	{Donato, Pablo},
  title =	{{The Flower Calculus}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.5},
  URN =		{urn:nbn:de:0030-drops-203343},
  doi =		{10.4230/LIPIcs.FSCD.2024.5},
  annote =	{Keywords: deep inference, graphical calculi, existential graphs, intuitionistic logic, Kripke semantics, cut-elimination}
}
Document
Track A: Algorithms, Complexity and Games
A Characterization of Complexity in Public Goods Games

Authors: Matan Gilboa

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We complete the characterization of the computational complexity of equilibrium in public goods games on graphs. In this model, each vertex represents an agent deciding whether to produce a public good, with utility defined by a "best-response pattern" determining the best response to any number of productive neighbors. We prove that the equilibrium problem is NP-complete for every finite non-monotone best-response pattern. This answers the open problem of [Gilboa and Nisan, 2022], and completes the answer to a question raised by [Papadimitriou and Peng, 2021], for all finite best-response patterns.

Cite as

Matan Gilboa. A Characterization of Complexity in Public Goods Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 73:1-73:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{gilboa:LIPIcs.ICALP.2024.73,
  author =	{Gilboa, Matan},
  title =	{{A Characterization of Complexity in Public Goods Games}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{73:1--73:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.73},
  URN =		{urn:nbn:de:0030-drops-202164},
  doi =		{10.4230/LIPIcs.ICALP.2024.73},
  annote =	{Keywords: Nash Equilibrium, Public Goods, Computational Complexity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
Solving Promise Equations over Monoids and Groups

Authors: Alberto Larrauri and Stanislav Živný

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups.

Cite as

Alberto Larrauri and Stanislav Živný. Solving Promise Equations over Monoids and Groups. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 146:1-146:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{larrauri_et_al:LIPIcs.ICALP.2024.146,
  author =	{Larrauri, Alberto and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Solving Promise Equations over Monoids and Groups}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{146:1--146:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.146},
  URN =		{urn:nbn:de:0030-drops-202893},
  doi =		{10.4230/LIPIcs.ICALP.2024.146},
  annote =	{Keywords: constraint satisfaction, promise constraint satisfaction, equations, minions}
}
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
Position
Standardizing Knowledge Engineering Practices with a Reference Architecture

Authors: Bradley P. Allen and Filip Ilievski

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
Knowledge engineering is the process of creating and maintaining knowledge-producing systems. Throughout the history of computer science and AI, knowledge engineering workflows have been widely used given the importance of high-quality knowledge for reliable intelligent agents. Meanwhile, the scope of knowledge engineering, as apparent from its target tasks and use cases, has been shifting, together with its paradigms such as expert systems, semantic web, and language modeling. The intended use cases and supported user requirements between these paradigms have not been analyzed globally, as new paradigms often satisfy prior pain points while possibly introducing new ones. The recent abstraction of systemic patterns into a boxology provides an opening for aligning the requirements and use cases of knowledge engineering with the systems, components, and software that can satisfy them best, however, this direction has not been explored to date. This paper proposes a vision of harmonizing the best practices in the field of knowledge engineering by leveraging the software engineering methodology of creating reference architectures. We describe how a reference architecture can be iteratively designed and implemented to associate user needs with recurring systemic patterns, building on top of existing knowledge engineering workflows and boxologies. We provide a six-step roadmap that can enable the development of such an architecture, consisting of scope definition, selection of information sources, architectural analysis, synthesis of an architecture based on the information source analysis, evaluation through instantiation, and, ultimately, instantiation into a concrete software architecture. We provide an initial design and outcome of the definition of architectural scope, selection of information sources, and analysis. As the remaining steps of design, evaluation, and instantiation of the architecture are largely use-case specific, we provide a detailed description of their procedures and point to relevant examples. We expect that following through on this vision will lead to well-grounded reference architectures for knowledge engineering, will advance the ongoing initiatives of organizing the neurosymbolic knowledge engineering space, and will build new links to the software architectures and data science communities.

Cite as

Bradley P. Allen and Filip Ilievski. Standardizing Knowledge Engineering Practices with a Reference Architecture. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.2.1.5,
  author =	{Allen, Bradley P. and Ilievski, Filip},
  title =	{{Standardizing Knowledge Engineering Practices with a Reference Architecture}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:23},
  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.5},
  URN =		{urn:nbn:de:0030-drops-198623},
  doi =		{10.4230/TGDK.2.1.5},
  annote =	{Keywords: knowledge engineering, knowledge graphs, quality attributes, software architectures, sociotechnical systems}
}
Document
On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Authors: Peter Mayr

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


Abstract
For a fixed finite algebra 𝐀, we consider the decision problem SysTerm(𝐀): does a given system of term equations have a solution in 𝐀? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of 𝐀. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [Bulatov, 2017] and Zhuk [Zhuk, 2017], it follows that SysTerm(𝐀) for a finite algebra 𝐀 is in P if 𝐀 has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra 𝐀 in a congruence modular variety (e.g. for a quasigroup), SysTerm(𝐀) is in P if the core of 𝐀 is abelian and is NP-complete otherwise. Given 𝐀 by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.

Cite as

Peter Mayr. On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{mayr:LIPIcs.MFCS.2023.66,
  author =	{Mayr, Peter},
  title =	{{On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{66:1--66:12},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.66},
  URN =		{urn:nbn:de:0030-drops-186007},
  doi =		{10.4230/LIPIcs.MFCS.2023.66},
  annote =	{Keywords: systems of equations, general algebras, constraint satisfaction}
}
Document
Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments

Authors: Markus Grimmer

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
There is a broad range of packages and libraries for verified numerical computation. C-XSC is a library combining one of the most extensive sets of functions and operations on the one hand with a wide range of applications and special features on the other hand. As such it is an important task both to make use of its existing capabilities in applications and to develop further extensions giving access to additional areas and environments. In this talk, we present some examples of extensions for C-XSC that have been developed lately. Among these are extensions that give access to further hardware and software environments as well as applications making use of these possibilities. Software libraries for interval computation always imply great computation effort: One way to reduce computation times is the development of parallel methods to make use of parallel hardware. For this, it is important that the features and data types of the used library can be easily used in parallel programs. An MPI package for C-XSC data types allows to easily use C-XSC in parallel programs without bothering about the internal structure of data types. Another extension of C-XSC, the C-XSC Taylor arithmetic, is also covered by the MPI package. Parallel verified linear system solvers based on the package are available as well, and further development has been and is being done to integrate more efficient methods for interval linear system solution. One application making use of the mentioned extensions is a parallel verified Fredholm integral equation solver. Some results are given to demonstrate the reduction of computation time and, at the same time, the accuracy gain that can be obtained using the increased computation power. Naturally, hardware interval support would offer still more possibilities towards optimal performance of verified numerical software. Another possibility to extend the range of C-XSC is to make results available for further computations in other software environments as, for example, computer algebra packages. An example of this is presented for the Maple interval package intpakX. This kind of interfaces also allows the user to get access to further platforms like operating systems, compilers or even hardware. References: [1] ALiCEnext: http://www.alicenext.uni-wuppertal.de. [2] Blomquist, F.; Hofschuster, W.; Kraemer, W.: Real and Complex Taylor Arithmetic in C-XSC. Preprint BUW-WRSWT 2005/4, University of Wuppertal, 2005. [3] Grimmer, M.; Kraemer, W.: An MPI Extension for Verified Numerical Computations in Parallel Environments. In: Int. Conf. on Scientific Computing (CSC’07, Worldcomp’07) Las Vegas, June 25-28, 2007, Proceedings pp. 111-117, Arabnia et al. (eds.), 2007. [4] Grimmer, M.: An MPI Extension for the Use of C-XSC in Parallel Environments. Preprint BUW-WRSWT 2005/3, University of Wuppertal, 2005. [5] Grimmer, M.: Selbstverifizierende mathematische Softwarewerkzeuge im High Performance Computing. Dissertation, Logos Verlag, Berlin, 2007. [6] Grimmer, M.: Interval Arithmetic in Maple with intpakX. In: PAMM - Proceedings in Applied Mathematics and Mechanics, Vol. 2, Nr. 1, p. 442-443, Wiley-InterScience, 2003. [7] Hofschuster, W.; Kraemer, W.: C-XSC 2.0: A C++ Library for Extended Scientific Computing. Numerical Software with Result Verification, Lecture Notes in Computer Science, Volume 2991/2004, Springer-Verlag, Heidelberg, pp. 15 - 35, 2004. [8] Klein, W.: Enclosure Methods for Linear and Nonlinear Systems of Fredholm Integral Equations of the Second Kind. In: Adams, Kulisch: Scientific Computing with Result Verification, Academic Press, 1993.

Cite as

Markus Grimmer. Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{grimmer:DagSemProc.08021.10,
  author =	{Grimmer, Markus},
  title =	{{Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.10},
  URN =		{urn:nbn:de:0030-drops-14416},
  doi =		{10.4230/DagSemProc.08021.10},
  annote =	{Keywords: C-XSC, Integral Equations, Interval Arithmetic, Maple, MPI, Parallel Environment, Taylor Arithmetic, Verified Linear System Solver.}
}
Document
07461 Abstracts Collection – Numerical Methods for Structured Markov Chains

Authors: Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
From 11.11. to 14.11.07, the Dagstuhl Seminar 07461 ``Numerical Methods for Structured Markov Chains'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor. 07461 Abstracts Collection – Numerical Methods for Structured Markov Chains. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.1,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan and Remiche, Marie-Ange and Taylor, Peter},
  title =	{{07461 Abstracts Collection – Numerical Methods for Structured Markov Chains}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.1},
  URN =		{urn:nbn:de:0030-drops-14046},
  doi =		{10.4230/DagSemProc.07461.1},
  annote =	{Keywords: Matrix analytic methods, markov processes, queuing theory, numerical methods, structured matrices, telecommunication modeling, performance evaluation}
}
Document
07461 Executive Summary – Numerical Methods for Structured Markov Chains

Authors: Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
This Dagstuhl seminar has brought together leaders and young researchers in the fields of analysis of numerical algorithms, applied stochastic modeling and statistical inference, with the result of stimulating exchange of methodologies and experiences and generating synergetic collaborations. This has favored a better communication between these worlds where problems from the applications feed the theoretical research and where advanced numerical tools can be utilized in applications with reciprocal advantages.

Cite as

Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor. 07461 Executive Summary – Numerical Methods for Structured Markov Chains. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.2,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan and Remiche, Marie-Ange and Taylor, Peter},
  title =	{{07461 Executive Summary – Numerical Methods for Structured Markov Chains}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.2},
  URN =		{urn:nbn:de:0030-drops-14006},
  doi =		{10.4230/DagSemProc.07461.2},
  annote =	{Keywords: Matrix analytic methods, Markov processes, queuing theory, numerical methods, structured matrices, telecommunication modeling, performance evaluation.}
}
Document
A policy iteration algorithm for Markov decision processes skip-free in one direction

Authors: Joke Lambert, Benny van Houdt, and Chris Blondia

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
In this paper we present a new algorithm for policy iteration for Markov decision processes (MDP) skip-free in one direction. This algorithm, which is based on matrix analytic methods, is in the same spirit as the algorithm of White (Stochastic Models, 21:785-797, 2005) which was limited to matrices that are skip-free in both directions. Optimization problems that can be solved using Markov decision processes arise in the domain of optical buffers, when trying to improve loss rates of fibre delay line (FDL) buffers. Based on the analysis of such an FDL buffer we present a comparative study between the different techniques available to solve an MDP. The results illustrate that the exploitation of the structure of the transition matrices places us in a position to deal with larger systems, while reducing the computation times.

Cite as

Joke Lambert, Benny van Houdt, and Chris Blondia. A policy iteration algorithm for Markov decision processes skip-free in one direction. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{lambert_et_al:DagSemProc.07461.3,
  author =	{Lambert, Joke and van Houdt, Benny and Blondia, Chris},
  title =	{{A policy iteration algorithm for Markov decision processes skip-free in one direction}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.3},
  URN =		{urn:nbn:de:0030-drops-14032},
  doi =		{10.4230/DagSemProc.07461.3},
  annote =	{Keywords: Markov Decision Process, Policy Evaluation, Skip-Free, Optical buffers, Fibre Delay Lines}
}
  • Refine by Author
  • 5 Bini, Dario A.
  • 5 Meini, Beatrice
  • 3 Ramaswami, Vaidyanathan
  • 3 Remiche, Marie-Ange
  • 2 Bodrog, Levente
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Problems, reductions and completeness
  • 2 Computing methodologies → Knowledge representation and reasoning
  • 1 Applied computing → Physics
  • 1 Computing methodologies → Ontology engineering
  • 1 Information systems → Fixed length attributes
  • Show More...

  • Refine by Keyword
  • 2 Matrix analytic methods
  • 2 constraint satisfaction
  • 2 numerical methods
  • 2 queuing theory
  • 2 structured matrices
  • Show More...

  • Refine by Type
  • 28 document

  • Refine by Publication Year
  • 16 2008
  • 10 2024
  • 1 2006
  • 1 2023