19 Search Results for "Kiefer, Peter"

Document
DOI: 10.4230/LIPIcs.COSIT.2024.3
Can You Sketch in 3D? Exploring Perceived Feasibility and Use Cases of 3D Sketch Mapping

Authors: Kevin Gonyop Kim, Tiffany C.K. Kwok, Sailin Zhong, Peter Kiefer, and Martin Raubal

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
Sketch mapping is a research technique that has been widely used to study what people think about the spatial layout of an environment. One of the limitations of the current practice of sketch mapping is that the interface (a pen on paper or digital tablets) forces people to draw on 2D surfaces even when the information to be represented is 3D. For the purpose of studying the 3D aspect of spatial understanding, the recent advancements in extended reality (XR) technologies including virtual reality, augmented reality, and mixed reality are interesting as they provide novel ways to create 3D sketches. In this paper, we investigate how the concept of 3D sketch mapping using XR is perceived by users and explore its potential feasibility and use cases. For this, we conducted semi-structured interviews with 27 participants from three domains: aviation, architecture, and wayfinding. Our findings show that the concept is well-perceived as an intuitive way to externalize the 3D aspect of spatial information, and it has the potential to be a research tool for human cognition research as well as a practical tool that can provide added value in different professional activities.
Cite as

Kevin Gonyop Kim, Tiffany C.K. Kwok, Sailin Zhong, Peter Kiefer, and Martin Raubal. Can You Sketch in 3D? Exploring Perceived Feasibility and Use Cases of 3D Sketch Mapping. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.COSIT.2024.3,
  author =	{Kim, Kevin Gonyop and Kwok, Tiffany C.K. and Zhong, Sailin and Kiefer, Peter and Raubal, Martin},
  title =	{{Can You Sketch in 3D? Exploring Perceived Feasibility and Use Cases of 3D Sketch Mapping}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.3},
  URN =		{urn:nbn:de:0030-drops-208186},
  doi =		{10.4230/LIPIcs.COSIT.2024.3},
  annote =	{Keywords: Sketch maps, spatial understanding, 3D sketching, extended reality, use cases, interviews}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2024.5
Spatial Nudging: Converging Persuasive Technologies, Spatial Design, and Behavioral Theories

Authors: Ayda Grisiute and Martin Raubal

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
This paper presents the Spatial Nudging framework - a theory-based framework that maps out nudging strategies in the mobility domain and refines its existing definitions. We link these strategies by highlighting the role of perceived affordances across physical and digital interventions based on the Nudge Theory and the Theory of Affordances. Furthermore, we propose to use graph representation techniques as a supportive methodology to better align perceived and actual environments, thereby enhancing the intervention strategies' effectiveness. We illustrate the applicability of the Spatial Nudging framework and the supportive methodology in the context of an E-bike City vision. This paper lays the foundation for future research on theoretically integrating physical and digital interventions to promote sustainable mobility.
Cite as

Ayda Grisiute and Martin Raubal. Spatial Nudging: Converging Persuasive Technologies, Spatial Design, and Behavioral Theories. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grisiute_et_al:LIPIcs.COSIT.2024.5,
  author =	{Grisiute, Ayda and Raubal, Martin},
  title =	{{Spatial Nudging: Converging Persuasive Technologies, Spatial Design, and Behavioral Theories}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.5},
  URN =		{urn:nbn:de:0030-drops-208206},
  doi =		{10.4230/LIPIcs.COSIT.2024.5},
  annote =	{Keywords: spatial nudging, active mobility, Nudge Theory, Theory of Affordances, cognitive graphs}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2024.29
Assessing Perceived Route Difficulty in Environments with Different Complexity (Short Paper)

Authors: Arvid Horned, Zoe Falomir, and Kai-Florian Richter

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
Today, anyone feeling lost in a city or unsure about how to navigate can use navigation services to look up routes to where they want to go. Current research investigating these services has primarily focused on how to find an appropriate route and how to best support navigation along it, and not how routes and the maps they are presented on are perceived. What makes one route look more difficult to navigate than another? And how does experience with using navigation services and maps in daily life influence how difficult a route is perceived to be? We explored these questions in a survey study where participants rated the perceived difficulty of pedestrian routes in ten different cities. The results show that routes in more complex urban environments were perceived as more complex than routes in easier environments. At least partly, perceived difficulty seems to follow earlier conceptualizations of route complexity, but open questions remain regarding the interplay of environmental structure, route properties, and the map representation.
Cite as

Arvid Horned, Zoe Falomir, and Kai-Florian Richter. Assessing Perceived Route Difficulty in Environments with Different Complexity (Short Paper). In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 29:1-29:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{horned_et_al:LIPIcs.COSIT.2024.29,
  author =	{Horned, Arvid and Falomir, Zoe and Richter, Kai-Florian},
  title =	{{Assessing Perceived Route Difficulty in Environments with Different Complexity}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{29:1--29:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.29},
  URN =		{urn:nbn:de:0030-drops-208444},
  doi =		{10.4230/LIPIcs.COSIT.2024.29},
  annote =	{Keywords: navigation complexity, perceived difficulty, route display, spatial cognition}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2024.30
Wheelchair Users Navigational Behavior: Insights from Eye Movement Data and Environment Legibility (Short Paper)

Authors: Sanaz Azimi, Mir Abolfazl Mostafavi, Angélique Lydia Montuwy, Krista Lynn Best, and Aurélie Dommes

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
This study aims to investigate how eye movement data and the legibility of the environment can help us to better understand the navigational behavior of wheelchair users (WCUs) in urban environments. For this purpose and through a field-based exploratory experiment, the legibility of a route was computed and compared with the visual behavior of two participants with different levels of wheelchair-using experience. The preliminary outcomes show the less experienced WCU has looked more intensively for information in the environment, while the more experienced one engaged in a deep cognitive process to maintain his safety. In addition, we have observed a correlation between the level of the legibility of the environment and the fixation duration and the frequency of saccades between fixations, likely leading to intensive cognitive processes in some situations. Based on these results and upcoming complementary experiments, we intend to better adapt the assistive navigation technologies for the mobility needs of WCU.
Cite as

Sanaz Azimi, Mir Abolfazl Mostafavi, Angélique Lydia Montuwy, Krista Lynn Best, and Aurélie Dommes. Wheelchair Users Navigational Behavior: Insights from Eye Movement Data and Environment Legibility (Short Paper). In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 30:1-30:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{azimi_et_al:LIPIcs.COSIT.2024.30,
  author =	{Azimi, Sanaz and Mostafavi, Mir Abolfazl and Montuwy, Ang\'{e}lique Lydia and Best, Krista Lynn and Dommes, Aur\'{e}lie},
  title =	{{Wheelchair Users Navigational Behavior: Insights from Eye Movement Data and Environment Legibility}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{30:1--30:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.30},
  URN =		{urn:nbn:de:0030-drops-208459},
  doi =		{10.4230/LIPIcs.COSIT.2024.30},
  annote =	{Keywords: Wheelchair users, Navigational behavior, Mobility, Eye-tracking, Legibility}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2024.1
Wayfinding Stages: The Role of Familiarity, Gaze Events, and Visual Attention

Authors: Negar Alinaghi and Ioannis Giannopoulos

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
Understanding the cognitive processes involved in wayfinding is crucial for both theoretical advances and practical applications in navigation systems development. This study explores how gaze behavior and visual attention contribute to our understanding of cognitive states during wayfinding. Based on the model proposed by Downs and Stea, which segments wayfinding into four distinct stages: self-localization, route planning, monitoring, and goal recognition, we conducted an outdoor wayfinding experiment with 56 participants. Given the significant role of spatial familiarity in wayfinding behavior, each participant navigated six different routes in both familiar and unfamiliar environments, with their eye movements being recorded. We provide a detailed examination of participants' gaze behavior and the actual objects of focus. Our findings reveal distinct gaze behavior patterns and visual attention, differentiating wayfinding stages while emphasizing the impact of spatial familiarity. This examination of visual engagement during wayfinding explains adaptive cognitive processes, demonstrating how familiarity influences navigation strategies. The results enhance our theoretical understanding of wayfinding and offer practical insights for developing navigation aids capable of predicting different wayfinding stages.
Cite as

Negar Alinaghi and Ioannis Giannopoulos. Wayfinding Stages: The Role of Familiarity, Gaze Events, and Visual Attention. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alinaghi_et_al:LIPIcs.COSIT.2024.1,
  author =	{Alinaghi, Negar and Giannopoulos, Ioannis},
  title =	{{Wayfinding Stages: The Role of Familiarity, Gaze Events, and Visual Attention}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.1},
  URN =		{urn:nbn:de:0030-drops-208161},
  doi =		{10.4230/LIPIcs.COSIT.2024.1},
  annote =	{Keywords: Eye-tracking, Wayfinding, Spatial Familiarity, Visual Attention, Gaze Behavior}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2024.18
Weighted Basic Parallel Processes and Combinatorial Enumeration

Authors: Lorenzo Clemente

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract
We study weighted basic parallel processes (WBPP), a nonlinear recursive generalisation of weighted finite automata inspired from process algebra and Petri net theory. Our main result is an algorithm of 2-EXPSPACE complexity for the WBPP equivalence problem. While (unweighted) BPP language equivalence is undecidable, we can use this algorithm to decide multiplicity equivalence of BPP and language equivalence of unambiguous BPP, with the same complexity. These are long-standing open problems for the related model of weighted context-free grammars. Our second contribution is a connection between WBPP, power series solutions of systems of polynomial differential equations, and combinatorial enumeration. To this end we consider constructible differentially finite power series (CDF), a class of multivariate differentially algebraic series introduced by Bergeron and Reutenauer in order to provide a combinatorial interpretation to differential equations. CDF series generalise rational, algebraic, and a large class of D-finite (holonomic) series, for which no complexity upper bound for equivalence was known. We show that CDF series correspond to commutative WBPP series. As a consequence of our result on WBPP and commutativity, we show that equivalence of CDF power series can be decided with 2-EXPTIME complexity. In order to showcase the CDF equivalence algorithm, we show that CDF power series naturally arise from combinatorial enumeration, namely as the exponential generating series of constructible species of structures. Examples of such species include sequences, binary trees, ordered trees, Cayley trees, set partitions, series-parallel graphs, and many others. As a consequence of this connection, we obtain an algorithm to decide multiplicity equivalence of constructible species, decidability of which was not known before. The complexity analysis is based on effective bounds from algebraic geometry, namely on the length of chains of polynomial ideals constructed by repeated application of finitely many, not necessarily commuting derivations of a multivariate polynomial ring. This is obtained by generalising a result of Novikov and Yakovenko in the case of a single derivation, which is noteworthy since generic bounds on ideal chains are non-primitive recursive in general. On the way, we develop the theory of WBPP series and CDF power series, exposing several of their appealing properties.
Cite as

Lorenzo Clemente. Weighted Basic Parallel Processes and Combinatorial Enumeration. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{clemente:LIPIcs.CONCUR.2024.18,
  author =	{Clemente, Lorenzo},
  title =	{{Weighted Basic Parallel Processes and Combinatorial Enumeration}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.18},
  URN =		{urn:nbn:de:0030-drops-207903},
  doi =		{10.4230/LIPIcs.CONCUR.2024.18},
  annote =	{Keywords: weighted automata, combinatorial enumeration, shuffle, algebraic differential equations, process algebra, basic parallel processes, species of structures}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2024.32
Minimising the Probabilistic Bisimilarity Distance

Authors: Stefan Kiefer and Qiyi Tang

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract
A labelled Markov decision process (MDP) is a labelled Markov chain with nondeterminism; i.e., together with a strategy a labelled MDP induces a labelled Markov chain. The model is related to interval Markov chains. Motivated by applications to the verification of probabilistic noninterference in security, we study problems of minimising probabilistic bisimilarity distances of labelled MDPs, in particular, whether there exist strategies such that the probabilistic bisimilarity distance between the induced labelled Markov chains is less than a given rational number, both for memoryless strategies and general strategies. We show that the distance minimisation problem is ∃ℝ-complete for memoryless strategies and undecidable for general strategies. We also study the computational complexity of the qualitative problem about making the distance less than one. This problem is known to be NP-complete for memoryless strategies. We show that it is EXPTIME-complete for general strategies.
Cite as

Stefan Kiefer and Qiyi Tang. Minimising the Probabilistic Bisimilarity Distance. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kiefer_et_al:LIPIcs.CONCUR.2024.32,
  author =	{Kiefer, Stefan and Tang, Qiyi},
  title =	{{Minimising the Probabilistic Bisimilarity Distance}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.32},
  URN =		{urn:nbn:de:0030-drops-208049},
  doi =		{10.4230/LIPIcs.CONCUR.2024.32},
  annote =	{Keywords: Markov decision processes, Markov chains}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2024.37
A Spectrum of Approximate Probabilistic Bisimulations

Authors: Timm Spork, Christel Baier, Joost-Pieter Katoen, Jakob Piribauer, and Tim Quatmann

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract
This paper studies various notions of approximate probabilistic bisimulation on labeled Markov chains (LMCs). We introduce approximate versions of weak and branching bisimulation, as well as a notion of ε-perturbed bisimulation that relates LMCs that can be made (exactly) probabilistically bisimilar by small perturbations of their transition probabilities. We explore how the notions interrelate and establish their connections to other well-known notions like ε-bisimulation.
Cite as

Timm Spork, Christel Baier, Joost-Pieter Katoen, Jakob Piribauer, and Tim Quatmann. A Spectrum of Approximate Probabilistic Bisimulations. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{spork_et_al:LIPIcs.CONCUR.2024.37,
  author =	{Spork, Timm and Baier, Christel and Katoen, Joost-Pieter and Piribauer, Jakob and Quatmann, Tim},
  title =	{{A Spectrum of Approximate Probabilistic Bisimulations}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.37},
  URN =		{urn:nbn:de:0030-drops-208099},
  doi =		{10.4230/LIPIcs.CONCUR.2024.37},
  annote =	{Keywords: Markov chains, Approximate bisimulation, Abstraction, Model checking}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.30
When Lawvere Meets Peirce: An Equational Presentation of Boolean Hyperdoctrines

Authors: Filippo Bonchi, Alessandro Di Giorgio, and Davide Trotta

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Fo-bicategories are a categorification of Peirce’s calculus of relations. Notably, their laws provide a proof system for first-order logic that is both purely equational and complete. This paper illustrates a correspondence between fo-bicategories and Lawvere’s hyperdoctrines. To streamline our proof, we introduce peircean bicategories, which offer a more succinct characterization of fo-bicategories.
Cite as

Filippo Bonchi, Alessandro Di Giorgio, and Davide Trotta. When Lawvere Meets Peirce: An Equational Presentation of Boolean Hyperdoctrines. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.MFCS.2024.30,
  author =	{Bonchi, Filippo and Di Giorgio, Alessandro and Trotta, Davide},
  title =	{{When Lawvere Meets Peirce: An Equational Presentation of Boolean Hyperdoctrines}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.30},
  URN =		{urn:nbn:de:0030-drops-205867},
  doi =		{10.4230/LIPIcs.MFCS.2024.30},
  annote =	{Keywords: relational algebra, hyperdoctrines, cartesian bicategories, string diagrams}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2024.23
Mirroring Call-By-Need, or Values Acting Silly

Authors: Beniamino Accattoli and Adrienne Lancelot

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

Abstract
Call-by-need evaluation for the λ-calculus can be seen as merging the best of call-by-name and call-by-value, namely the wise erasing behaviour of the former and the wise duplicating behaviour of the latter. To better understand how duplication and erasure can be combined, we design a degenerated calculus, dubbed call-by-silly, that is symmetric to call-by-need in that it merges the worst of call-by-name and call-by-value, namely silly duplications by-name and silly erasures by-value. We validate the design of the call-by-silly calculus via rewriting properties and multi types. In particular, we mirror the main theorem about call-by-need - that is, its operational equivalence with call-by-name - showing that call-by-silly and call-by-value induce the same contextual equivalence. This fact shows the blindness with respect to efficiency of call-by-value contextual equivalence. We also define a call-by-silly strategy and measure its length via tight multi types. Lastly, we prove that the call-by-silly strategy computes evaluation sequences of maximal length in the calculus.
Cite as

Beniamino Accattoli and Adrienne Lancelot. Mirroring Call-By-Need, or Values Acting Silly. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{accattoli_et_al:LIPIcs.FSCD.2024.23,
  author =	{Accattoli, Beniamino and Lancelot, Adrienne},
  title =	{{Mirroring Call-By-Need, or Values Acting Silly}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-203527},
  doi =		{10.4230/LIPIcs.FSCD.2024.23},
  annote =	{Keywords: Lambda calculus, intersection types, call-by-value, call-by-need}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.152
On Homomorphism Indistinguishability and Hypertree Depth

Authors: Benjamin Scheidt

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

Abstract
GC^k is a logic introduced by Scheidt and Schweikardt (2023) to express properties of hypergraphs. It is similar to first-order logic with counting quantifiers (C) adapted to the hypergraph setting. It has distinct sets of variables for vertices and for hyperedges and requires vertex variables to be guarded by hyperedge variables on every quantification. We prove that two hypergraphs G, H satisfy the same sentences in the logic GC^k with guard depth at most k if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of strict hypertree depth at most k. This lifts the analogous result for tree depth ≤ k and sentences of first-order logic with counting quantifiers of quantifier rank at most k due to Grohe (2020) from graphs to hypergraphs. The guard depth of a formula is the quantifier rank with respect to hyperedge variables, and strict hypertree depth is a restriction of hypertree depth as defined by Adler, Gavenčiak and Klimošová (2012). To justify this restriction, we show that for every H, the strict hypertree depth of H is at most 1 larger than its hypertree depth, and we give additional evidence that strict hypertree depth can be viewed as a reasonable generalisation of tree depth for hypergraphs.
Cite as

Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 152:1-152:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{scheidt:LIPIcs.ICALP.2024.152,
  author =	{Scheidt, Benjamin},
  title =	{{On Homomorphism Indistinguishability and Hypertree Depth}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{152:1--152: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.152},
  URN =		{urn:nbn:de:0030-drops-202958},
  doi =		{10.4230/LIPIcs.ICALP.2024.152},
  annote =	{Keywords: homomorphism indistinguishability, counting logics, guarded logics, hypergraphs, incidence graphs, tree depth, elimination forest, hypertree width}
}
Document
Survey
DOI: 10.4230/TGDK.2.1.3
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
DOI: 10.4230/LIPIcs.GIScience.2023.1
Do You Need Instructions Again? Predicting Wayfinding Instruction Demand

Authors: Negar Alinaghi, Tiffany C. K. Kwok, Peter Kiefer, and Ioannis Giannopoulos

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
The demand for instructions during wayfinding, defined as the frequency of requesting instructions for each decision point, can be considered as an important indicator of the internal cognitive processes during wayfinding. This demand can be a consequence of the mental state of feeling lost, being uncertain, mind wandering, having difficulty following the route, etc. Therefore, it can be of great importance for theoretical cognitive studies on human perception of the environment. From an application perspective, this demand can be used as a measure of the effectiveness of the navigation assistance system. It is therefore worthwhile to be able to predict this demand and also to know what factors trigger it. This paper takes a step in this direction by reporting a successful prediction of instruction demand (accuracy of 78.4%) in a real-world wayfinding experiment with 45 participants, and interpreting the environmental, user, instructional, and gaze-related features that caused it.
Cite as

Negar Alinaghi, Tiffany C. K. Kwok, Peter Kiefer, and Ioannis Giannopoulos. Do You Need Instructions Again? Predicting Wayfinding Instruction Demand. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alinaghi_et_al:LIPIcs.GIScience.2023.1,
  author =	{Alinaghi, Negar and Kwok, Tiffany C. K. and Kiefer, Peter and Giannopoulos, Ioannis},
  title =	{{Do You Need Instructions Again? Predicting Wayfinding Instruction Demand}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.1},
  URN =		{urn:nbn:de:0030-drops-188963},
  doi =		{10.4230/LIPIcs.GIScience.2023.1},
  annote =	{Keywords: Wayfinding, Navigation Instructions, Urban Computing, Gaze Analysis}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2022.14
3D Sketch Maps: Concept, Potential Benefits, and Challenges (Short Paper)

Authors: Kevin Gonyop Kim, Jakub Krukar, Panagiotis Mavros, Jiayan Zhao, Peter Kiefer, Angela Schwering, Christoph Hölscher, and Martin Raubal

Published in: LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022)

Abstract
Studying the 3D aspect of spatial information has become increasingly important due to changes in the way we interact with the surrounding environments as well as technological innovations. Current pen-and-paper approaches of sketch mapping have a limitation in investigating 3D spatial knowledge as they are forced to be drawn on 2D interfaces. In this paper, we propose the concept of 3D sketch mapping as a tool to study human spatial knowledge by externalizing the mental models of spatial information with 3D representations. The goal of this paper is to introduce the concept, discuss its potential importance and challenges, and share our vision for future research directions.
Cite as

Kevin Gonyop Kim, Jakub Krukar, Panagiotis Mavros, Jiayan Zhao, Peter Kiefer, Angela Schwering, Christoph Hölscher, and Martin Raubal. 3D Sketch Maps: Concept, Potential Benefits, and Challenges (Short Paper). In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 14:1-14:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.COSIT.2022.14,
  author =	{Kim, Kevin Gonyop and Krukar, Jakub and Mavros, Panagiotis and Zhao, Jiayan and Kiefer, Peter and Schwering, Angela and H\"{o}lscher, Christoph and Raubal, Martin},
  title =	{{3D Sketch Maps: Concept, Potential Benefits, and Challenges}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{14:1--14:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.14},
  URN =		{urn:nbn:de:0030-drops-168992},
  doi =		{10.4230/LIPIcs.COSIT.2022.14},
  annote =	{Keywords: Sketch maps, mental representations, spatial knowledge}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.8
Not Arbitrary, Systematic! Average-Based Route Selection for Navigation Experiments

Authors: Bartosz Mazurkiewicz, Markus Kattenbeck, Peter Kiefer, and Ioannis Giannopoulos

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Abstract
While studies on human wayfinding have seen increasing interest, the criteria for the choice of the routes used in these studies have usually not received particular attention. This paper presents a methodological framework which aims at filling this gap. Based on a thorough literature review on route choice criteria, we present an approach that supports wayfinding researchers in finding a route whose characteristics are as similar as possible to the population of all considered routes with a predefined length in a particular area. We provide evidence for the viability of our approach by means of both, synthetic and real-world data. The proposed method allows wayfinding researchers to justify their route choice decisions, and it enhances replicability of studies on human wayfinding. Furthermore, it allows to find similar routes in different geographical areas.
Cite as

Bartosz Mazurkiewicz, Markus Kattenbeck, Peter Kiefer, and Ioannis Giannopoulos. Not Arbitrary, Systematic! Average-Based Route Selection for Navigation Experiments. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mazurkiewicz_et_al:LIPIcs.GIScience.2021.I.8,
  author =	{Mazurkiewicz, Bartosz and Kattenbeck, Markus and Kiefer, Peter and Giannopoulos, Ioannis},
  title =	{{Not Arbitrary, Systematic! Average-Based Route Selection for Navigation Experiments}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.8},
  URN =		{urn:nbn:de:0030-drops-130437},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.8},
  annote =	{Keywords: Route Selection, Route Features, Human Wayfinding, Navigation, Experiments, Replicability}
}
  • Refine by Author
  • 6 Kiefer, Peter
  • 4 Giannopoulos, Ioannis
  • 4 Raubal, Martin
  • 2 Alinaghi, Negar
  • 2 Kiefer, Stefan
  • Show More...

  • Refine by Classification
  • 3 General and reference → Empirical studies
  • 2 Applied computing → Psychology
  • 2 Human-centered computing → Human computer interaction (HCI)
  • 2 Information systems → Geographic information systems
  • 2 Theory of computation → Finite Model Theory
  • Show More...

  • Refine by Keyword
  • 3 Wayfinding
  • 2 Eye-tracking
  • 2 Markov chains
  • 2 Sketch maps
  • 1 3D sketching
  • Show More...

  • Refine by Type
  • 19 document

  • Refine by Publication Year
  • 12 2024
  • 2 2019
  • 1 2017
  • 1 2018
  • 1 2020
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact