DROPS

Volume

OASIcs, Volume 53

7th Workshop on Computational Models of Narrative (CMN 2016)

CMN 2016, July 11-12, 2016, Kraków, Poland

Editors: Ben Miller, Antonio Lieto, Rémi Ronfard, Stephen G. Ware, and Mark A. Finlayson

Volume

OASIcs, Volume 45

6th Workshop on Computational Models of Narrative (CMN 2015)

CMN 2015, May 26-28, 2015, Atlanta, USA

Editors: Mark A. Finlayson, Ben Miller, Antonio Lieto, and Remi Ronfard

Document

DOI: 10.4230/LIPIcs.FUN.2022.19

Wordle Is NP-Hard

Authors: Daniel Lokshtanov and Bernardo Subercaseaux

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

Wordle is a single-player word-guessing game where the goal is to discover a secret word w that has been chosen from a dictionary D. In order to discover w, the player can make at most 𝓁 guesses, which must also be words from D, all words in D having the same length k. After each guess, the player is notified of the positions in which their guess matches the secret word, as well as letters in the guess that appear in the secret word in a different position. We study the game of Wordle from a complexity perspective, proving NP-hardness of its natural formalization: to decide given a dictionary D and an integer 𝓁 if the player can guarantee to discover the secret word within 𝓁 guesses. Moreover, we prove that hardness holds even over instances where words have length k = 5, and that even in this case it is NP-hard to approximate the minimum number of guesses required to guarantee discovering the secret word. We also present results regarding its parameterized complexity and offer some related open problems.

Cite as

Daniel Lokshtanov and Bernardo Subercaseaux. Wordle Is NP-Hard. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 19:1-19:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.FUN.2022.19,
  author =	{Lokshtanov, Daniel and Subercaseaux, Bernardo},
  title =	{{Wordle Is NP-Hard}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{19:1--19:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.19},
  URN =		{urn:nbn:de:0030-drops-159893},
  doi =		{10.4230/LIPIcs.FUN.2022.19},
  annote =	{Keywords: wordle, np-hardness, complexity}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2022.83

Adaptive Massively Parallel Constant-Round Tree Contraction

Authors: MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, and Hsin-Hao Su

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

Miller and Reif’s FOCS'85 [Gary L. Miller and John H. Reif, 1989] classic and fundamental tree contraction algorithm is a broadly applicable technique for the parallel solution of a large number of tree problems. Additionally it is also used as an algorithmic design technique for a large number of parallel graph algorithms. In all previously explored models of computation, however, tree contractions have only been achieved in Ω(log n) rounds of parallel run time. In this work, we not only introduce a generalized tree contraction method but also show it can be computed highly efficiently in O(1/ε³) rounds in the Adaptive Massively Parallel Computing (AMPC) setting, where each machine has O(n^ε) local memory for some 0 < ε < 1. AMPC is a practical extension of Massively Parallel Computing (MPC) which utilizes distributed hash tables [MohammadHossein Bateni et al., 2017; Behnezhad et al., 2019; Raimondas Kiveris et al., 2014]. In general, MPC is an abstract model for MapReduce, Hadoop, Spark, and Flume which are currently widely used across industry and has been studied extensively in the theory community in recent years. Last but not least, we show that our results extend to multiple problems on trees, including but not limited to maximum and maximal matching, maximum and maximal independent set, tree isomorphism testing, and more.

Cite as

MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, and Hsin-Hao Su. Adaptive Massively Parallel Constant-Round Tree Contraction. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 83:1-83:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hajiaghayi_et_al:LIPIcs.ITCS.2022.83,
  author =	{Hajiaghayi, MohammadTaghi and Knittel, Marina and Saleh, Hamed and Su, Hsin-Hao},
  title =	{{Adaptive Massively Parallel Constant-Round Tree Contraction}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{83:1--83:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.83},
  URN =		{urn:nbn:de:0030-drops-156790},
  doi =		{10.4230/LIPIcs.ITCS.2022.83},
  annote =	{Keywords: Adaptive Massively Parallel Computation, Tree Contraction, Matching, Independent Set, Tree Isomorphism}
}

Document

DOI: 10.4230/LIPIcs.SNAPL.2017.9

Uncanny Valleys in Declarative Language Design

Authors: Mark S. Miller, Daniel von Dincklage, Vuk Ercegovac, and Brian Chin

Published in: LIPIcs, Volume 71, 2nd Summit on Advances in Programming Languages (SNAPL 2017)

Abstract

When people write programs in conventional programming languages, they over-specify how to solve the problem they have in mind. Over-specification prevents the language's implementation from making many optimization decisions, leaving programmers with this burden. In more declarative languages, programmers over-specify less, enabling the implementation to make more choices for them. As these decisions improve, programmers shift more attention from implementation to their real problems. This process easily overshoots. When under-specified programs almost always work well enough, programmers rarely need to think about implementation details. As their understanding of implementation choices atrophies, the controls provided so they can override these decisions become obscure. Our declarative language project, Yedalog, is in the midst of this dilemma. The improvements in question make our users more productive, so we cannot simply retreat back towards over-specification. To proceed forward instead, we must meet some of the expectations we prematurely provoked, and our implementation's behavior must help users learn expectations more aligned with our intended semantics. These are general issues. Discussing their concrete manifestation in Yedalog should help other declarative systems that come to face these issues.

Cite as

Mark S. Miller, Daniel von Dincklage, Vuk Ercegovac, and Brian Chin. Uncanny Valleys in Declarative Language Design. In 2nd Summit on Advances in Programming Languages (SNAPL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 71, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{miller_et_al:LIPIcs.SNAPL.2017.9,
  author =	{Miller, Mark S. and von Dincklage, Daniel and Ercegovac, Vuk and Chin, Brian},
  title =	{{Uncanny Valleys in Declarative Language Design}},
  booktitle =	{2nd Summit on Advances in Programming Languages (SNAPL 2017)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-032-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{71},
  editor =	{Lerner, Benjamin S. and Bod{\'\i}k, Rastislav and Krishnamurthi, Shriram},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2017.9},
  URN =		{urn:nbn:de:0030-drops-71299},
  doi =		{10.4230/LIPIcs.SNAPL.2017.9},
  annote =	{Keywords: Declarative logic programming language}
}

Document

Complete Volume

DOI: 10.4230/OASIcs.CMN.2016

OASIcs, Volume 53, CMN'16, Complete Volume

Authors: Ben Miller, Antonio Lieto, Rémi Ronfard, Stephen G. Ware, and Mark A. Finlayson

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

OASIcs, Volume 53, CMN'16, Complete Volume

Cite as

7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{miller_et_al:OASIcs.CMN.2016,
  title =	{{OASIcs, Volume 53, CMN'16, Complete Volume}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016},
  URN =		{urn:nbn:de:0030-drops-67545},
  doi =		{10.4230/OASIcs.CMN.2016},
  annote =	{Keywords: Knowledge Representation Formalisms and Methods, Artificial Intelligence, General/Cognitive simulation, Natural Language Processing, Simulation and Modeling, Problem Solving, Control Methods, and Search, Distributed Artificial Intelligence, Psychology, Literature}
}

Document

Front Matter

DOI: 10.4230/OASIcs.CMN.2016.0

Frontmatter, Table of Contents, Preface, List of Authors

Authors: Ben Miller, Antonio Lieto, Rémi Ronfard, Stephen G. Ware, and Mark A. Finlayson

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

Frontmatter, Table of Contents, Preface, List of Authors

Cite as

7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{miller_et_al:OASIcs.CMN.2016.0,
  author =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  title =	{{Frontmatter, Table of Contents, Preface, List of Authors}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.0},
  URN =		{urn:nbn:de:0030-drops-67015},
  doi =		{10.4230/OASIcs.CMN.2016.0},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, List of Authors}
}

Document

Invited Talk

DOI: 10.4230/OASIcs.CMN.2016.1

From Narrative to Visual Narrative to Audiovisual Narrative: the Multimodal Discourse Theory Connection (Invited Talk)

Authors: John A. Bateman

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

Models of narrative have been proposed from many perspectives and most of these nowadays promote further the notion that narrative is a transmedial phenomenon: i.e., stories can be told making use of distinct and multiple forms of expressions. This raises a range of theoretical and practical questions, as well as rendering the task of providing computational models of narrative both more interesting and more challenging. Central to this endeavour are issues concerned with the potential mutual conditioning of narrative forms and the media employed. Methods are required for isolating narrative properties and mechanisms that may be generalised across media, while at the same time appropriately respecting differences in medial affordances. In this discussion paper I set out a corresponding approach to characterising narrative that draws on a fine-grained formal characterisation of multimodal discourse developed on the basis of both functional and formal linguistic models of discourse, generalised to the multimodal case. After briefly setting out the theoretical principles on which the account builds, I position narrative with respect to the framework and give an example of how audiovisual narratives such as film are accounted for. It will be suggested that a common anchoring in a well specified notion of discourse as an intrinsically multimodal phenomenon offers beneficial new angles on how narratives can be modelled, as well as establishing bridges between humanistic understandings of narrative and complementary computational accounts of narratives involving communicative goal-based planning.

Cite as

John A. Bateman. From Narrative to Visual Narrative to Audiovisual Narrative: the Multimodal Discourse Theory Connection (Invited Talk). In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 1:1-1:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bateman:OASIcs.CMN.2016.1,
  author =	{Bateman, John A.},
  title =	{{From Narrative to Visual Narrative to Audiovisual Narrative: the Multimodal Discourse Theory Connection}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{1:1--1:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.1},
  URN =		{urn:nbn:de:0030-drops-67028},
  doi =		{10.4230/OASIcs.CMN.2016.1},
  annote =	{Keywords: Narrative, computational modelling, discourse, multimodality}
}

Document

DOI: 10.4230/OASIcs.CMN.2016.2

Trailer Brain: Neural and Behavioral Analysis of Social Issue Documentary Viewing with Low-Density EEG

Authors: Jason S. Sherwin, Corinne Brenner, and John S. Johnson

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

The effects of social issue documentaries are diverse. In particular, monetary donations and advocacy on social media are behavioral effects with public consequences. Conversely, information-seeking about an issue is potentially done in private. We designed a combined free-viewing and rapid perceptual decision-making experiment to simulate a real scenario confronted by otherwise uninformed movie-viewers, i.e., to determine what degree of support they will lend to a film based on its trailer. For a cohort of subjects with active video-streaming (e.g., Netflix) and social media accounts (e.g., Facebook), we recorded electroencephalography (EEG) and behavioral responses to trailers of social issue documentaries. We examined EEG using reliable component analysis (RCA), finding reliability within subjects across multiple viewings and across subjects within a given viewing of the same trailer. We found this reliability both over EEG captured from whole-movie viewing, as well as over 5-second movie segments. Behavioral responses following trailer viewing were not consistent from first to second viewings. Rather, support choices both tended towards extremes of support/non-support and were made faster upon second viewing. We hypothesized a relationship between reliability behavioral metrics, finding credible evidence for it in this dataset. Finally, we found that we could suitably train a naive classifier to categorize production value and narrative voice ratings given to the viewed movies from RCA-based metrics alone. In sum, our results show that EEG components during free-viewing of social issue documentary trailers can provide a useful tool to investigate viewers' neural responses during viewing, when coupled with a post hoc behavioral decision-making paradigm. The possibility of this tool being used by producers and filmmakers is also discussed.

Cite as

Jason S. Sherwin, Corinne Brenner, and John S. Johnson. Trailer Brain: Neural and Behavioral Analysis of Social Issue Documentary Viewing with Low-Density EEG. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sherwin_et_al:OASIcs.CMN.2016.2,
  author =	{Sherwin, Jason S. and Brenner, Corinne and Johnson, John S.},
  title =	{{Trailer Brain: Neural and Behavioral Analysis of Social Issue Documentary Viewing with Low-Density EEG}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{2:1--2:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.2},
  URN =		{urn:nbn:de:0030-drops-67034},
  doi =		{10.4230/OASIcs.CMN.2016.2},
  annote =	{Keywords: EEG, reliable components analysis, machine learning, documentary films}
}

Document

DOI: 10.4230/OASIcs.CMN.2016.3

Animation Motion in NarrativeML

Authors: Inderjeet Mani

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

This paper describes qualitative spatial representations relevant to cartoon motion incorporated into NarrativeML, an annotation scheme intended to capture some of the core aspects of narrative. These representations are motivated by linguistic distinctions drawn from cross-linguistic studies. Motion is modeled in terms of transitions in spatial configurations, using an expressive dynamic logic with the manner and path of motion being derived from a few basic primitives. The manner is elaborated to represent properties of motion that bear on character affect. Such representations can potentially be used to support cartoon narrative summarization and question-answering. The paper discusses annotation challenges, and the use of computer vision to help in annotation. Work is underway on annotating a cartoon corpus in terms of this scheme.

Cite as

Inderjeet Mani. Animation Motion in NarrativeML. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mani:OASIcs.CMN.2016.3,
  author =	{Mani, Inderjeet},
  title =	{{Animation Motion in NarrativeML}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{3:1--3:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.3},
  URN =		{urn:nbn:de:0030-drops-67042},
  doi =		{10.4230/OASIcs.CMN.2016.3},
  annote =	{Keywords: Cinematography, Motion, Qualitative Reasoning, Narrative, NarrativeML}
}

Document

DOI: 10.4230/OASIcs.CMN.2016.4

Steps Towards a Formal Ontology of Narratives Based on Narratology

Authors: Valentina Bartalesi, Carlo Meghini, and Daniele Metilli

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

Narrative is emerging as a notion that may enable overcoming the limitations of the discovery functionality (only ranked lists of objects) offered by information systems to their users. We present preliminary results on modelling narratives by means of formal ontology, by introducing a conceptualization of narratives and a mathematical expression of it. Our conceptualization tries to capture fundamental notions of narratives as defined in narratology, such as fabula, narration and plot. A validation of the conceptualization and of its mathematical specification is ongoing, based on the Semantic Web standards and on the CIDOC CRM ISO standard ontology.

Cite as

Valentina Bartalesi, Carlo Meghini, and Daniele Metilli. Steps Towards a Formal Ontology of Narratives Based on Narratology. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 4:1-4:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bartalesi_et_al:OASIcs.CMN.2016.4,
  author =	{Bartalesi, Valentina and Meghini, Carlo and Metilli, Daniele},
  title =	{{Steps Towards a Formal Ontology of Narratives Based on Narratology}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{4:1--4:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.4},
  URN =		{urn:nbn:de:0030-drops-67051},
  doi =		{10.4230/OASIcs.CMN.2016.4},
  annote =	{Keywords: Ontology, Narrative}
}

Document

DOI: 10.4230/OASIcs.CMN.2016.5

Exploring “Letters from the Future” by Visualizing Narrative Structure

Authors: Sytske Wiegersma, Anneke M. Sools, and Bernard P. Veldkamp

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

The growing supply of online mental health tools, platforms and treatments results in an enormous quantity of digital narrative data to be structured, analysed and interpreted. Natural Language Processing is very suitable to automatically extract textual and structural features from narratives. Visualizing these features can help to explore patterns and shifts in text content and structure. In this study, streamgraphs are developed for different types of "Letters from the Future", an online mental health promotion instrument. The visualizations show differences between as well as within the different letter types, providing directions for future research in both the visualization of narrative structure and in the field of narrative psychology. The method presented here is not limited to "Letters from the Future", the current object of study, but can in fact be used to explore any digital or digitalized textual source, like books, speech transcripts or email conversations.

Cite as

Sytske Wiegersma, Anneke M. Sools, and Bernard P. Veldkamp. Exploring “Letters from the Future” by Visualizing Narrative Structure. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wiegersma_et_al:OASIcs.CMN.2016.5,
  author =	{Wiegersma, Sytske and Sools, Anneke M. and Veldkamp, Bernard P.},
  title =	{{Exploring “Letters from the Future” by Visualizing Narrative Structure}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{5:1--5:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.5},
  URN =		{urn:nbn:de:0030-drops-67064},
  doi =		{10.4230/OASIcs.CMN.2016.5},
  annote =	{Keywords: Text visualization, NLP, Narrative structure}
}

Document

DOI: 10.4230/OASIcs.CMN.2016.6

Comparing Extant Story Classifiers: Results & New Directions

Authors: Joshua D. Eisenberg, W. Victor H. Yarlott, and Mark A. Finlayson

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

Having access to a large set of stories is a necessary first step for robust and wide-ranging computational narrative modeling; happily, language data - including stories - are increasingly available in electronic form. Unhappily, the process of automatically separating stories from other forms of written discourse is not straightforward, and has resulted in a data collection bottleneck. Therefore researchers have sought to develop reliable, robust automatic algorithms for identifying story text mixed with other non-story text. In this paper we report on the reimplementation and experimental comparison of the two approaches to this task: Gordon's unigram classifier, and Corman's semantic triplet classifier. We cross-analyze their performance on both Gordon's and Corman's corpora, and discuss similarities, differences, and gaps in the performance of these classifiers, and point the way forward to improving their approaches.

Cite as

Joshua D. Eisenberg, W. Victor H. Yarlott, and Mark A. Finlayson. Comparing Extant Story Classifiers: Results & New Directions. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{eisenberg_et_al:OASIcs.CMN.2016.6,
  author =	{Eisenberg, Joshua D. and Yarlott, W. Victor H. and Finlayson, Mark A.},
  title =	{{Comparing Extant Story Classifiers: Results \& New Directions}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{6:1--6:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.6},
  URN =		{urn:nbn:de:0030-drops-67079},
  doi =		{10.4230/OASIcs.CMN.2016.6},
  annote =	{Keywords: Story Detection, Machine Learning, Natural Language Processing, Perceptron Learning}
}

Document

DOI: 10.4230/OASIcs.CMN.2016.7

Learning a Better Motif Index: Toward Automated Motif Extraction

Authors: W. Victor H. Yarlott and Mark A. Finlayson

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

Motifs are distinctive recurring elements found in folklore, and are used by folklorists to categorize and find tales across cultures and track the genetic relationships of tales over time. Motifs have significance beyond folklore as communicative devices found in news, literature, press releases, and propaganda that concisely imply a large constellation of culturally-relevant information. Until now, folklorists have only extracted motifs from narratives manually, and the conceptual structure of motifs has not been formally laid out. In this short paper we propose that it is possible to automate the extraction of both existing and new motifs from narratives using supervised learning techniques and thereby possible to learn a computational model of how folklorists determine motifs. Automatic extraction would enable the construction of a truly comprehensive motif index, which does not yet exist, as well as the automatic detection of motifs in cultural materials, opening up a new world of narrative information for analysis by anyone interested in narrative and culture. We outline an experimental design, and report on our efforts to produce a structured form of Thompson's motif index, as well as a development annotation of motifs in a small collection of Russian folklore. We propose several initial computational, supervised approaches, and describe several possible metrics of success. We describe lessons learned and difficulties encountered so far, and outline our plan going forward.

Cite as

W. Victor H. Yarlott and Mark A. Finlayson. Learning a Better Motif Index: Toward Automated Motif Extraction. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 7:1-7:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yarlott_et_al:OASIcs.CMN.2016.7,
  author =	{Yarlott, W. Victor H. and Finlayson, Mark A.},
  title =	{{Learning a Better Motif Index: Toward Automated Motif Extraction}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{7:1--7:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.7},
  URN =		{urn:nbn:de:0030-drops-67088},
  doi =		{10.4230/OASIcs.CMN.2016.7},
  annote =	{Keywords: Text analysis, automated feature extraction, folklore, narrative, Russian folktales}
}

Document

DOI: 10.4230/OASIcs.CMN.2016.8

ProppML: A Complete Annotation Scheme for Proppian Morphologies

Authors: W. Victor H. Yarlott and Mark A. Finlayson

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract

We give a preliminary description of ProppML, an annotation scheme designed to capture all the components of a Proppian-style morphological analysis of narratives. This work represents the first fully complete annotation scheme for Proppian morphologies, going beyond previous annotation schemes such as PftML, ProppOnto, Bod et al., and our own prior work. Using ProppML we have annotated Propp's morphology on fifteen tales (18,862 words) drawn from his original corpus of Russian folktales. This is a significantly larger set of data than annotated in previous studies. This pilot corpus was constructed via double annotation by two highly trained annotators, whose annotations were then combined after discussion with a third highly trained adjudicator, resulting in gold standard data which is appropriate for training machine learning algorithms. Agreement measures calculated between both annotators show very good agreement (F_1>0.75, kappa>0.9 for functions; F_1>0.6 for moves; and F_1>0.8, kappa>0.6 for dramatis personae). This is the first robust demonstration of reliable annotation of Propp's system.

Cite as

W. Victor H. Yarlott and Mark A. Finlayson. ProppML: A Complete Annotation Scheme for Proppian Morphologies. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yarlott_et_al:OASIcs.CMN.2016.8,
  author =	{Yarlott, W. Victor H. and Finlayson, Mark A.},
  title =	{{ProppML: A Complete Annotation Scheme for Proppian Morphologies}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{8:1--8:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.8},
  URN =		{urn:nbn:de:0030-drops-67094},
  doi =		{10.4230/OASIcs.CMN.2016.8},
  annote =	{Keywords: Narrative structure, Computational folkloristics, Russian folktales}
}

42 Search Results for "Miller, Mark"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message