18 Search Results for "Wagner, Thomas"


Document
Towards Realistic Pedestrian Route Planning

Authors: Simeon Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)


Abstract
Pedestrian routing has its specific set of challenges, which are often neglected by state-of-the-art route planners. For instance, the lack of detailed sidewalk data and the inability to traverse plazas and parks in a natural way often leads to unappealing and suboptimal routes. In this work, we first propose to augment the network by generating sidewalks based on the street geometry and adding edges for routing over plazas and squares. Using this and further information, our query algorithm seamlessly handles node-to-node queries and queries whose origin or destination is an arbitrary location on a plaza or inside a park. Our experiments show that we are able to compute appealing pedestrian routes at negligible overhead over standard routing algorithms.

Cite as

Simeon Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, and Dorothea Wagner. Towards Realistic Pedestrian Route Planning. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{andreev_et_al:OASIcs.ATMOS.2015.1,
  author =	{Andreev, Simeon and Dibbelt, Julian and N\"{o}llenburg, Martin and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Towards Realistic Pedestrian Route Planning}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.1},
  URN =		{urn:nbn:de:0030-drops-54592},
  doi =		{10.4230/OASIcs.ATMOS.2015.1},
  annote =	{Keywords: pedestrian routing, realistic model, shortest paths, speed-up technique}
}
Document
Speed-Consumption Tradeoff for Electric Vehicle Route Planning

Authors: Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)


Abstract
We study the problem of computing routes for electric vehicles (EVs) in road networks. Since their battery capacity is limited, and consumed energy per distance increases with velocity, driving the fastest route is often not desirable and may even be infeasible. On the other hand, the energy-optimal route may be too conservative in that it contains unnecessary detours or simply takes too long. In this work, we propose to use multicriteria optimization to obtain Pareto sets of routes that trade energy consumption for speed. In particular, we exploit the fact that the same road segment can be driven at different speeds within reasonable intervals. As a result, we are able to provide routes with low energy consumption that still follow major roads, such as freeways. Unfortunately, the size of the resulting Pareto sets can be too large to be practical. We therefore also propose several nontrivial techniques that can be applied on-line at query time in order to speed up computation and filter insignificant solutions from the Pareto sets. Our extensive experimental study, which uses a real-world energy consumption model, reveals that we are able to compute diverse sets of alternative routes on continental networks that closely resemble the exact Pareto set in just under a second---several orders of magnitude faster than the exhaustive algorithm.

Cite as

Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-Consumption Tradeoff for Electric Vehicle Route Planning. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 138-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{baum_et_al:OASIcs.ATMOS.2014.138,
  author =	{Baum, Moritz and Dibbelt, Julian and H\"{u}bschle-Schneider, Lorenz and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Speed-Consumption Tradeoff for Electric Vehicle Route Planning}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{138--151},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.138},
  URN =		{urn:nbn:de:0030-drops-47583},
  doi =		{10.4230/OASIcs.ATMOS.2014.138},
  annote =	{Keywords: electric vehicles, shortest paths, route planning, bicriteria optimization, algorithm engineering}
}
Document
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

Authors: Bireswar Das, Jacobo Torán, and Fabian Wagner

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time~\cite{Bo90},\cite{YBFT}.We give restricted space algorithms for these problems proving the following results: \begin{itemize} \item Isomorphism for bounded tree distance width graphs is in \Log\ and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace. \item For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i.e.\ considering only isomorphisms mapping bags in one decomposition blockwise onto bags in the other decomposition) is in \Log. \item For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in \LogCFL. \item As a corollary the isomorphism problem for bounded treewidth graphs is in \LogCFL. This improves the known \TCone\ upper bound for the problem given by Grohe and Verbitsky~\cite{GV06}. \end{itemize}

Cite as

Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 227-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2010.2457,
  author =	{Das, Bireswar and Tor\'{a}n, Jacobo and Wagner, Fabian},
  title =	{{Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{227--238},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2457},
  URN =		{urn:nbn:de:0030-drops-24570},
  doi =		{10.4230/LIPIcs.STACS.2010.2457},
  annote =	{Keywords: Complexity, Algorithms, Graph Isomorphism Problem, Treewidth, LogCFL}
}
Document
Planar Graph Isomorphism is in Log-Space

Authors: Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)


Abstract
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important special case by presenting an upper bound that matches the known log-space hardness [JKMT03]. In fact, we show the formally stronger result that planar graph canonization is in log-space. This improves the previously known upper bound of AC1 [MR91]. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to log-space reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in log-space by [DLN08]. This is achieved by using the above decomposition, and by making significant modifications to Lindell’s algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph.

Cite as

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar Graph Isomorphism is in Log-Space. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{datta_et_al:DagSemProc.09421.6,
  author =	{Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian},
  title =	{{Planar Graph Isomorphism is in Log-Space}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--32},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.6},
  URN =		{urn:nbn:de:0030-drops-24169},
  doi =		{10.4230/DagSemProc.09421.6},
  annote =	{Keywords: Planar Graphs, Graph Isomorphism, Logspace}
}
Document
Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

Authors: Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)


Abstract
Graph isomorphism is an important and widely studied computational problem with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently, \cite{DLNTW09} proved that planar isomorphism is complete for log-space. We extend this result %of \cite{DLNTW09} further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as a minor, and give a log-space algorithm. Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into triconnected components, which are known to be either planar or $K_5$ components \cite{Vaz89}. This gives a triconnected component tree similar to that for planar graphs. An extension of the log-space algorithm of \cite{DLNTW09} can then be used to decide the isomorphism problem. For $K_5$ minor-free graphs, we consider $3$-connected components. These are either planar or isomorphic to the four-rung mobius ladder on $8$ vertices or, with a further decomposition, one obtains planar $4$-connected components \cite{Khu88}. We give an algorithm to get a unique decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components, and construct trees, accordingly. Since the algorithm of \cite{DLNTW09} does not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.

Cite as

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 145-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2009.2314,
  author =	{Datta, Samir and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian},
  title =	{{Graph Isomorphism for K\underline\{3,3\}-free and K\underline5-free graphs is in Log-space}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{145--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2314},
  URN =		{urn:nbn:de:0030-drops-23144},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2314},
  annote =	{Keywords: Graph isomorphism, K\underline\{3,3\}-free graphs, K\underline5-free graphs, log-space}
}
Document
Efficient Route Planning in Flight Networks

Authors: Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)


Abstract
We present a set of three new time-dependent models with increasing flexibility for realistic route planning in flight networks. By these means, we obtain small graph sizes while modeling airport procedures in a realistic way. With these graphs, we are able to efficiently compute a set of best connections with multiple criteria over a full day. It even turns out that due to the very limited graph sizes it is feasible to precompute full distance tables between all airports. As a result, best connections can be retrieved in a few microseconds on real world data.

Cite as

Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis. Efficient Route Planning in Flight Networks. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2009.2145,
  author =	{Delling, Daniel and Pajor, Thomas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Efficient Route Planning in Flight Networks}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2145},
  URN =		{urn:nbn:de:0030-drops-21450},
  doi =		{10.4230/OASIcs.ATMOS.2009.2145},
  annote =	{Keywords: Timetable information, flight modeling, shortest paths, multi criteria, table lookups Timetable information, flight modeling, shortest paths, multi criteria, table lookups}
}
Document
08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations

Authors: Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
From June 29, 2008, to July 4, 2008, the Dagstuhl Seminar 08271 ``Topological and Game-Theoretic Aspects of Infinite Computations'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, many 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

Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner. 08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.08271.1,
  author =	{Hertling, Peter and Selivanov, Victor and Thomas, Wolfgang and Wadge, William W. and Wagner, Klaus},
  title =	{{08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.1},
  URN =		{urn:nbn:de:0030-drops-16555},
  doi =		{10.4230/DagSemProc.08271.1},
  annote =	{Keywords: Automata theory, computability in analysis, dataflow computation, hierarchies, infinite computations, infinite games, reactive systems, specification and verification, topological complexity, Wadge reducibility}
}
Document
08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations

Authors: Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
The theory of the infinite behaviour of continuously operating computing devices is of primary importance for several branches of theoretical and practical computer science. In particular, it is fundamental for the verification and synthesis of reactive systems like microprocessors or operating systems, for the understanding of dataflow computation, and for the development of adequate mathematical foundations for exact real computation. The seminar brought together researchers from many different disciplines who are working on theoretical or practical aspects of infinite computations. In this summary we describe the topics, the goals, and the contributions of the seminar.

Cite as

Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner. 08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.08271.2,
  author =	{Hertling, Peter and Selivanov, Victor and Thomas, Wolfgang and Wadge, William W. and Wagner, Klaus},
  title =	{{08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.2},
  URN =		{urn:nbn:de:0030-drops-16499},
  doi =		{10.4230/DagSemProc.08271.2},
  annote =	{Keywords: Automata theory, computability in analysis, dataflow computation, hierarchies, infinite computations, infinite games, reactive systems, specification}
}
Document
Cartesian Programming: The TransLucid Programming Language

Authors: John Plaice and Blanca Mancilla

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
The TransLucid programming language is a low-level intensional language, designed to be sufficiently rich for it to be the target language for translating the common programming paradigms into it, while still being fully declarative. The objects manipulated by TransLucid, called hyperdatons, are arbitrary-dimensional infinite arrays, indexed by multidimensional tuples of arbitrary types. We present the syntax, denotational and operational semantics for a simple TransLucid system, consisting of 1) a header detailing how expressions should be parsed, 2) a set of libraries of types, and operations thereon, defined in a host language, 3) a set of TransLucid equations, and 4) a TransLucid demand to be evaluated. The evaluation of a demand for an (identifier, context) pair is undertaken using eduction, where previously computed pairs are stored in a cache called a warehouse. The execution ensures that only those dimensions actually encountered during the execution of an expression are taken into account when caching intermediate results.

Cite as

John Plaice and Blanca Mancilla. Cartesian Programming: The TransLucid Programming Language. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{plaice_et_al:DagSemProc.08271.3,
  author =	{Plaice, John and Mancilla, Blanca},
  title =	{{Cartesian Programming: The TransLucid Programming Language}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.3},
  URN =		{urn:nbn:de:0030-drops-16546},
  doi =		{10.4230/DagSemProc.08271.3},
  annote =	{Keywords: Cartesian programming, Lucid language, declarative programming, multidimensional programming, context-aware programming, semantics.}
}
Document
Declarative Synchronous Multithreaded Programming

Authors: Blanca Mancilla and John Plaice

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
We demonstrate how TransLucid can be used as a reactive system. At each instant, there is a set of active ports, where sets of equations, demands and threads are all registered. Each thread defines a sequence of (state, demand) pairs, and threads may interact through the overall set of equations. The entire system remains fully declarative.

Cite as

Blanca Mancilla and John Plaice. Declarative Synchronous Multithreaded Programming. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{mancilla_et_al:DagSemProc.08271.4,
  author =	{Mancilla, Blanca and Plaice, John},
  title =	{{Declarative Synchronous Multithreaded Programming}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.4},
  URN =		{urn:nbn:de:0030-drops-16536},
  doi =		{10.4230/DagSemProc.08271.4},
  annote =	{Keywords: Synchronous programming, distributed computing, declarative programming, Cartesian programming, multidimensional programming.}
}
Document
General Logic Programs as Infinite Games

Authors: Chrysida Galanaki, Panos Rondogiannis, and William W. Wadge

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
In [vE86] M.H. van Emden introduced a simple game semantics for definite logic programs. Recently [RW05,GRW05], the authors extended this game to apply to logic programs with negation. Moreover, under the assumption that the programs have a finite number of rules, it was demonstrated in [RW05,GRW05] that the game is equivalent to the well-founded semantics of negation. In this paper we present work-in-progress towards demonstrating that the game of [RW05,GRW05] is equivalent to the well-founded semantics even in the case of programs that have a countably infinite number of rules. We argue however that in this case the proof of correctness has to be more involved. More specifically, in order to demonstrate that the game is correct one has to define a refined game in which each of the two players in his first move makes a bet in the form of a countable ordinal. Each ordinal can be considered as a kind of clock that imposes a "time limit" to the moves of the corresponding player. We argue that this refined game can be used to give the proof of correctness for the countably infinite case.

Cite as

Chrysida Galanaki, Panos Rondogiannis, and William W. Wadge. General Logic Programs as Infinite Games. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{galanaki_et_al:DagSemProc.08271.5,
  author =	{Galanaki, Chrysida and Rondogiannis, Panos and Wadge, William W.},
  title =	{{General Logic Programs as Infinite Games}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.5},
  URN =		{urn:nbn:de:0030-drops-16519},
  doi =		{10.4230/DagSemProc.08271.5},
  annote =	{Keywords: Infinite Games, Negation in Logic Programming, Well-Founded Semantics}
}
Document
On the Semantic Approaches to Boolean Grammars

Authors: Vassilis Kountouriotis, Christos Nomikos, and Panos Rondogiannis

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
Boolean grammars extend context-free grammars by allowing conjunction and negation in rule bodies. This new formalism appears to be quite expressive and still efficient from a parsing point of view. Therefore, it seems reasonable to hope that boolean grammars can lead to more expressive tools that can facilitate the compilation process of modern programming languages. One important aspect concerning the theory of boolean grammars is their semantics. More specifically, the existence of negation makes it difficult to define a simple derivation-style semantics (such as for example in the case of context-free grammars). There have already been proposed a number of different semantic approaches in the literature. The purpose of this paper is to present the basic ideas behind each method and identify certain interesting problems that can be the object of further study in this area.

Cite as

Vassilis Kountouriotis, Christos Nomikos, and Panos Rondogiannis. On the Semantic Approaches to Boolean Grammars. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{kountouriotis_et_al:DagSemProc.08271.6,
  author =	{Kountouriotis, Vassilis and Nomikos, Christos and Rondogiannis, Panos},
  title =	{{On the Semantic Approaches to Boolean Grammars}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.6},
  URN =		{urn:nbn:de:0030-drops-16527},
  doi =		{10.4230/DagSemProc.08271.6},
  annote =	{Keywords: Boolean Grammars, Negation in Formal Grammars, Well-Founded Semantics}
}
Document
Topological Complexity of omega-Powers: Extended Abstract

Authors: Olivier Finkel and Dominique Lecomte

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
The operation of taking the omega-power $V^omega$ of a language $V$ is a fundamental operation over finitary languages leading to omega-languages. Since the set $X^omega$ of infinite words over a finite alphabet $X$ can be equipped with the usual Cantor topology, the question of the topological complexity of omega-powers of finitary languages naturally arises and has been posed by Damian Niwinski (1990), Pierre Simonnet (1992), and Ludwig Staiger (1997). We investigate the topological complexity of omega-powers. We prove the following very surprising results which show that omega-powers exhibit a great opological complexity: for each non-null countable ordinal $xi$, there exist some $Sigma^0_xi$-complete omega-powers, and some $Pi^0_xi$-complete omega-powers. On the other hand, the Wadge hierarchy is a great refinement of the Borel hierarchy, determined by Bill Wadge. We show that, for each ordinal $xi$ greater than or equal to 3, there are uncountably many Wadge degrees of omega-powers of Borel rank $xi +1$. Using tools of effective descriptive set theory, we prove some effective versions of the above results.

Cite as

Olivier Finkel and Dominique Lecomte. Topological Complexity of omega-Powers: Extended Abstract. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{finkel_et_al:DagSemProc.08271.7,
  author =	{Finkel, Olivier and Lecomte, Dominique},
  title =	{{Topological Complexity of omega-Powers: Extended Abstract}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.7},
  URN =		{urn:nbn:de:0030-drops-16505},
  doi =		{10.4230/DagSemProc.08271.7},
  annote =	{Keywords: Infinite words, omega-languages, omega-powers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge}
}
Document
Qualitative Abstraction and Inherent Uncertainty in Scene Recognition

Authors: Carsten Elfers, Otthein Herzog, Andrea Miene, and Thomas Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)


Abstract
The interpretation of scenes, e.g., in videos, is demanding at all levels. At the image processing level it is necessary to apply an "intelligent" segmentation and to determine the objects of interest. For the higher symbolic levels it is a challenging task to perform the transition between quantitative and qualitative data and to determine the relations between objects. Here we assume that the position of objects ("agents") in images and videos will already be determined as a minimal requirement for the further analysis. The interpretation of complex and dynamic scenes with embedded intentional agents is one of the most challenging tasks in current AI and imposes highly heterogeneous requirements. A key problem is the efficient and robust representation of uncertainty. We propose that uncertainty should be distinguished with respect to two different epistemological sources: (1) noisy sensor information and (2) ignorance. In this presentation we propose possible solutions to this class of problems. The use and evaluation of sensory information in the field of robotics shows impressive results especially in the fields of localization (e.g. MCL) and map building (e.g. SLAM) but also imposes serious problems on the successive higher levels of processing due to the probabilistic nature. In this presentation we propose that the use of (a) qualitative abstraction (classic approach) from quantitative to (at least partial) qualitative representations and (b) coherence-based perception validation based on Dempster-Shafer (DST) can help to reduce the problem significantly. The second important probability problem class that will be addressed is ignorance. In our presentation we will focus on reducing missing information by inference. We contrast/compare our experiences in an important field of scene interpretation namely plan and intention recognition. The first approach is based on a logical abductive approach and the second approach in contrast uses a probabilistic approach (Relational Hidden Markov Model (RHMM)).

Cite as

Carsten Elfers, Otthein Herzog, Andrea Miene, and Thomas Wagner. Qualitative Abstraction and Inherent Uncertainty in Scene Recognition. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{elfers_et_al:DagSemProc.08091.11,
  author =	{Elfers, Carsten and Herzog, Otthein and Miene, Andrea and Wagner, Thomas},
  title =	{{Qualitative Abstraction and Inherent Uncertainty in Scene Recognition}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.11},
  URN =		{urn:nbn:de:0030-drops-16141},
  doi =		{10.4230/DagSemProc.08091.11},
  annote =	{Keywords: Scene interpretation, intentional agents, uncertainty, qualitative abstraction, coherence-based perception, abduction, RHMM}
}
Document
Engineering Time-Expanded Graphs for Faster Timetable Information

Authors: Daniel Delling, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)


Abstract
We present an extension of the well-known time-expanded approach for timetable information. By remodeling unimportant stations, we are able to obtain faster query times with less space consumption than the original model. Moreover, we show that our extensions harmonize well with speed-up techniques whose adaption to timetable networks is more challenging than one might expect.

Cite as

Daniel Delling, Thomas Pajor, and Dorothea Wagner. Engineering Time-Expanded Graphs for Faster Timetable Information. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2008.1582,
  author =	{Delling, Daniel and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Engineering Time-Expanded Graphs for Faster Timetable Information}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1582},
  URN =		{urn:nbn:de:0030-drops-15826},
  doi =		{10.4230/OASIcs.ATMOS.2008.1582},
  annote =	{Keywords: Timetable information, shortest path, modeling}
}
  • Refine by Author
  • 5 Wagner, Dorothea
  • 4 Pajor, Thomas
  • 4 Wagner, Fabian
  • 3 Thierauf, Thomas
  • 3 Wadge, William W.
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 shortest paths
  • 2 Automata theory
  • 2 Cartesian programming
  • 2 Timetable information
  • 2 Well-Founded Semantics
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 10 2008
  • 2 2009
  • 2 2010
  • 1 1994
  • 1 2005
  • Show More...

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