Character encoding

Related publications (25)

Character Networks and Centrality

Yannick Rochat

A character network represents relations between characters from a text; the relations are based on text proximity, shared scenes/events, quoted speech, etc. Our project sketches a theoretical framework for character network analysis, bringing together narratology, both close and distant reading approaches, and social network analysis. It is in line with recent attempts to automatise the extraction of literary social networks (Elson, 2012; Sack, 2013) and other studies stressing the importance of character- systems (Woloch, 2003; Moretti, 2011). The method we use to build the network is direct and simple. First, we extract co-occurrences from a book index, without the need for text analysis. We then describe the narrative roles of the characters, which we deduce from their respective positions in the network, i.e. the discourse. As a case study, we use the autobiographical novel Les Confessions by Jean-Jacques Rousseau. We start by identifying co-occurrences of characters in the book index of our edition (Slatkine, 2012). Subsequently, we compute four types of centrality: degree, closeness, betweenness, eigenvector. We then use these measures to propose a typology of narrative roles for the characters. We show that the two parts of Les Confessions, written years apart, are structured around mirroring central figures that bear similar centrality scores. The first part revolves around the mentor of Rousseau; a figure of openness. The second part centres on a group of schemers, depicting a period of deep paranoia. We also highlight characters with intermediary roles: they provide narrative links between the societies in the life of the author. The method we detail in this complete case study of character network analysis can be applied to any work documented by an index.

University of Lausanne2014

Character network analysis of Émile Zola’s Les Rougon-Macquart

Yannick Rochat

In this work, we use network analysis methods to sketch a typology of fiction novels based on characters and their proximity in the narration. We construct character networks modelling the twenty novels composing Les Rougon-Macquart, written by Émile Zola. To categorise them, we rely on methods that track down major and minor characters relative to the character-systems. For that matter, we use centrality measures such as degree and eigenvector centrality. Eventually, with this analysis of a small corpus, we open the stage for a large-scale analysis of novels through their character networks.

2015

Supramolecular Self-Assembly Driven by Electrostatic Repulsion: The 1D Aggregation of Rubrene Pentagons on Au(111)

Alfonso Baldereschi, Wolf-Dieter Schneider, Massimiliano Stengel

At present, organic molecules are among the best candidate "building blocks" for the construction of self-assembling nanoscale devices based on metal substrates. Control of the formation of specific patterns In the submonolayer regime is usually achieved by appropriate choice and/or functionalization of the adsorbates. The effect of this intervention, though, is limited by the typically short-range character of the bonding. We present here a theoretical study on the system rubrene/gold to show that substrate-induced molecular charging can Instead determine the assembly on larger scales. OFT calculations and electrostatic considerations are used to discuss the charge transfer at the metal/organic Interface. This allows rationalization of previous puzzling experimental results and, in particular, of the unusual molecular gap broadening upon adsorption observed in STS spectra. The self-assembly process is further studied by means of classical molecular dynamics simulations. The charged adsorbates are modeled as mutually repulsive standing dipoles, with van der Waals interactions Intervening at short distances. The striking resemblance between the experimental STM images and the results of our MD simulations shows that this simple model is able to capture the key effects driving the assembly in this system. The competition between long-range repulsive Interactions and short-range attractive forces leads to characteristic and easily recognizable 1D patterns. We suggest that experimental evidence of the presence of similar patterns in other meta/organic systems can provide crucial information on the electronic level alignment at the interface, that is, on the occurrence of charge-transfer processes between metal and organic adsorbates.

2010

Exact Synthesis of Boolean Functions in Majority-of-five Forms

Zhufei Chu, Giovanni De Micheli, Winston Jason Haaswijk, Mathias Soeken

Recent studies show that majority-based logic synthesis is beneficial for both traditional and nanotechnology digital designs. However, most of the existing synthesis algorithms for majority logic generate majority-of-three (M-3) networks. The optimization opportunity for majority logic by using an arbitrary number of odd inputs still requires a large research effort. In this paper, we present an exact synthesis approach for computing Boolean functions in majority-of-five (M-5) forms with a minimum number of operations using Boolean satisfiability. By exploiting the symmetry properties of majority operators, we make use of symbolic encoding method to represent the node functionality and to reduce the number of variables. Moreover, we represent the M-5 forms by M-5-inverter graphs (M(5)IGs) for manipulation, which is an extension of majority-inverter graphs (MIGs). The experimental results on EPFL benchmark suites indicate the proposed method achieves 10.4 % improvement on size and 11.4 % on depth compared to the state-of-the-art exact synthesis method.

IEEE2019

Generating, animating, and rendering varied individuals for real-time crowds

Jonathan Maim

To simulate realistic crowds of virtual humans in real time, three main requirements need satisfaction. First of all, quantity, i.e., the ability to simulate thousands of characters. Secondly, quality, because each virtual human composing a crowd needs to look unique in its appearance and animation. Finally, efficiency is paramount, for an operation usually efficient on a single virtual human, becomes extremely costly when applied on large crowds. Developing an architecture able to manage all three aspects is a challenging problem that we have addressed in our research. Our first contribution is an efficient and versatile architecture called YaQ, able to simulate thousands of characters in real time. This platform, developed at EPFL-VRLab, results from several years of research and integrates state-of-the-art techniques at all levels: YaQ aims at providing efficient algorithms and real-time solutions for populating globally and massively large-scale empty environments. YaQ thus fits various application domains, such as video games and virtual reality. Our architecture is especially efficient in managing the large quantity of data that is used to simulate crowds. In order to simulate large crowds, many instances of a small set of human templates have to be generated. From this starting point, if no care is taken to vary each character individually, many clones appear in the crowd. We present several algorithms to make each individual unique in the crowd. Firstly, we introduce a new method to distinguish body parts of a human and apply detailed color variety and patterns to each one of them. Secondly, we present two techniques to modify the shape and profile of a virtual human: a simple and efficient method for attaching accessories to individuals, and efficient tools to scale the skeleton and mesh of an instance. Finally, we also contribute to varying individuals' animation by introducing variations to the upper body movements, thus allowing characters to make a phone call, have a hand in their pocket, or carry heavy accessories, etc. To achieve quantity in a crowd, levels of detail need to be used. We explore the most adequate solutions to simulate large crowds with levels of detail, while avoiding disturbing switches between two different representations of a virtual human. To do so, we develop solutions to make most variety techniques scalable to all levels of detail.

EPFL2009

Compile-Time Type-Driven Data Representation Transformations in Object-Oriented Languages

Vlad Ureche

High-level languages allow programmers to express data structures and algorithms that abstract over the type of data they handle. This improves code reuse and makes it possible to develop general-purpose libraries. Yet, data abstractions slow down program execution, as they require low-level indirection. In this thesis we explore three compile-time approaches that leverage type systems to reduce the cost of data abstractions, thus improving program performance. In the first part of the thesis we present miniboxing, a compile-time transformation that replaces generic classes by more efficient variants, optimized to handle primitive types. These variants use the miniboxed data encoding, producing speedups of up to 20x compared to generic classes. The miniboxing transformation is the main result of this thesis and motivates the other techniques. Generalizing miniboxing, we show the Late Data Layout (LDL) mechanism, which uses the type system to guide performance-oriented program rewritings. It can be instantiated to perform a host of transformations, such as miniboxing generics, inlining value classes and unboxing primitive types. The LDL mechanism has many desirable properties, such as provable correctness in handling different data representations, reduced number of conversions and built-in support for the object-oriented paradigm. Finally, we show Data-centric Metaprogramming, a technique that allows programmers to go beyond standard compiler optimizations by defining custom representations to be used for their data. These representations are then automatically introduced by the compiler when translating programs. This technique, similar in spirit to metaprogramming, opens new directions in programmer-driven optimizations and shows encouraging results, with speedups of up to 25x. Under the hood, Data-centric Metaprogramming uses the Late Data Layout mechanism.

EPFL2015

SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism

Giovanni De Micheli, Winston Jason Haaswijk, Mathias Soeken

Exact synthesis is a versatile logic synthesis technique with applications to logic optimization, technology mapping, synthesis for emerging technologies, and cryptography. In recent years, advances in SAT solving have lead to a heightened research effort into SAT-based exact synthesis. Advantages of exact synthesis include the use of various constraints (e.g. synthesis of emerging technology circuits). However, although progress has been made, its runtime remains unpredictable. This paper identifies two key points as hurdles to further progress. First, there are open questions regarding the design and implementation of exact synthesis systems, due to the many degrees of freedom. For example, there are different CNF encodings, different symmetry breaks to choose from, and different encodings may be suitable for different domains. Second, SAT-based exact synthesis is difficult to parallelize. Indeed, this is a common drawback of logic synthesis algorithms. This paper proposes four ways to close some open questions and to reduce runtime: (i) quantifying differences between CNF encoding schemes and their impacts on runtime, (ii) demonstrating impact of symmetry breaking constraints, (iii) showing how DAG topology information can be used to decrease runtime, (iv) showing how topology information can be used to leverage parallelism.

2020

Decoding Choice Encodings

We study two encodings of the asynchronous pi-calculus with input-guarded choice into its choice-free fragment. One encoding is divergence-free, but refines the atomic commitment of choice into gradual commitment. The other preserves atomicity, but introduces divergence. The divergent encoding is fully abstract with respect to weak bisimulation, but the more natural divergence-free encoding is not. Instead, we show that it is fully abstract with respect to coupled simulation, a slightly coarser-but still coinductively defined-equivalence that does not enforce bisimilarity of internal branching decisions. The correctness proofs for the two choice encodings introduce a novel proof technique exploiting the properties of explicit decodings from translations to source terms.

2000

Qualitative Spatial and Temporal Reasoning with Answer Set Programming

Jingshi Li

Representing and reasoning spatial and temporal information is a key research issue in Computer Science and Artificial Intelligence. In this paper, we introduce tools that produce three novel encodings which translate problems in qualitative spatial and temporal reasoning into logic programs for answer set programming solvers. Each encoding reflects a different type of modeling abstraction. We evaluate our approach with two of the most well known qualitative spatial and temporal reasoning formalisms, the Interval Algebra and Region Connection Calculus. Our results show some surprising findings, including the strong performance of the solver for disjunctive logic programs over the non-disjunctive ones on our benchmark problems.

2012

Multi-Tone Signaling and ADC-Based Digital Receiver for High-Speed Wireline Serial Links

Gain Kim

The exponential growth of Internet traffic and related demands for higher communication speed pushes processor-to-processor and processor-to-memory interconnects to provide further higher data-rate. Often time, processor-to-memory interconnectsâ speed is limited by reflections due to their multi-drop bus (MDB) channel nature, and processor-to-processor interconnectsâ speed is limited by inter-symbol interference due to the slowly-decaying channel pulse response and the operating speed and/or power efficiency of the equalization circuits. For the data-rate to continue its exponential growth, more complex modulation and equalization techniques should be employed in the transmitter (TX) and receiver (RX) circuits, given the power and silicon area budget. This thesis presents a signaling scheme designed to overcome equalization challenges related to reflection-limited interfaces such as MDB interfaces. By shaping the spectrum of the transmitted signal appropriately to the channelâs frequency characteristics, the proposed signaling enables minimization of energy-loss due to reflections. While the data-rate of conventional non-return-to-zero (NRZ) signaling over MDB is limited by its first notch frequency unless power-hungry decision-feedback equalizer (DFE) is employed, the proposed signaling scheme allows overcoming such limitation by simple encoding and decoding. Analogmulti-tone (AMT) signaling with single-sideband (SSB) radio-frequency (RF)-bands for efficient bandwidth usage is proposed for lossy point-to-point interfaces. The mutually orthogonal RF sub-bands feature self-equalization throughout the propagation through the communication medium and down-conversion at the RX, without necessitating the presence of conventional equalizers. To enable communication with higher modulation order for more efficient bandwidth utilization, an analog-to-digital converter (ADC)-based discrete multi-tone (DMT) RX is designed and implemented. Thanks to the high bandwidth efficiency of approximately 5.33 bits/Hz (including the cyclic prefix of DMT symbol) using 64-level quadrature amplitude modulation (64-QAM), the implemented RX undergoes less channel attenuation as compared to its 4-level pulse amplitude modulation (PAM-4) counterpart given target communication speed through the same channel. Moreover, the inherently parallel RX architecture of DMT signaling allows the RX digital signal processing (DSP) elements to be designed in semi-custom style without stringent timing constraints. Finally, a PAM-4 RX based on ADC with fully-digital equalization is presented. With register-transfer level (RTL) modeling of the designed digital equalizer, the results demonstrate the feasibility of frequency-domain equalization of the time-domain signal using Fourier transform and its inversion. The proposed frequency-domain equalization technique removes the necessity of symbol-by-symbol feedback loop in DSP that is present in DFE, relaxing critical timing constraints in DSP synthesis.

EPFL2018