Search

Recent studies provide mixed results regarding whether the perception of facial attractiveness is increased or decreased by partial occlusion with a sanitary mask. One set of studies demonstrated that occluding the bottom half of a face increased facial attractiveness. This effect is thought to occur because the occluded area is interpolated by an average facial representation that is perceived as attractive. However, several groups of studies showed that partial occlusion can increase or decrease perceived attractiveness depending on the attractiveness of the original (unoccluded) face, due to regression to the mean. To reconcile this inconsistency, we propose that the occluded area is interpolated not by an average facial representation, but by a template of moderate attractiveness, shaped by the distribution of each viewer’s experience. This hypothesis predicts an interaction between occlusion and the attractiveness of the original face so that occluded attractive faces are rated as less attractive, while occluded unattractive faces are rated as more attractive. To examine this hypothesis, the present study used attractiveness-rating tasks with mask-free versus masked faces in own-race and other-races categories. Viewers were familiar with own-race faces and unfamiliar with other-races faces. If moderate-attractiveness interpolation were the explanatory factor, the interaction between the occlusion and the attractiveness of the original face should be found only in the rating of own-race faces. Consistent with this hypothesis, the interaction between the occlusion and the attractiveness of the original faces was significant only for the own-race faces. Specifically, wearing a sanitary mask decreased the facial attractiveness of attractive faces in the own-race, while it increased the attractiveness regardless of the level of facial attractiveness in other-races. These findings suggest that the occluded area of own-race faces is interpolated by a facial template of moderate attractiveness. The other-races template could be developed using familiar exemplars such as celebrities. Thus, interpolation by such a template should result in elevated attractiveness relative to that by an own-race template. Accordingly, the apparent inconsistency in the literature regarding the effect of partial occlusion on physical attractiveness can be explained in terms of differences in the template involving interpolation of the occluded area.

Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit $\mathrm{O}(n)$-bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with $n$ vertices over BDDs representing the binary strings in time polynomial in $n$. Moreover, our algorithms are extended to enumerate those with constraints on the maximum (bi)clique size and/or the number of edges., Accepted to the 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023)

We replicate our previous study (Ichimura & Ariga, 2020) to demonstrate the robustness of the distractor devaluation effect in response to internal attentional selection.

This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In general, a reconfiguration problem checks if there is a step-by-step transformation between two given feasible solutions (e.g., independent sets of an input graph) of a fixed search problem such that all intermediate results are also feasible and each step obeys a fixed reconfiguration rule (e.g., adding/removing a single vertex to/from an independent set). The solution space formed by all feasible solutions can be exponential in the input size, and indeed many reconfiguration problems are known to be PSPACE-complete. This paper shows that an algorithm in the proposed framework efficiently conducts the breadth-first search by compressing the solution space using ZDDs, and finds a shortest transformation between two given feasible solutions if exists. Moreover, the proposed framework provides rich information on the solution space, such as the connectivity of the solution space and all feasible solutions reachable from a specified one. We demonstrate that the proposed framework can be applied to various reconfiguration problems, and experimentally evaluate their performances.

Although visual and auditory inputs are initially processed in separate perception systems, studies have built on the idea that to maintain spatial information these modalities share a component of working memory. The present study used working memory navigation tasks to examine functional similarities and dissimilarities in the performance of updating tasks. Participants mentally updated the spatial location of a target in a virtual array in response to sequential pictorial and sonant directional cues before identifying the target's final location. We predicted that if working memory representations are modality-specific, mixed-modality cues would demonstrate a cost of modality switching relative to unimodal cues. The results indicate that updating performance using visual unimodal cues positively correlated with that using auditory unimodal cues. Task performance using unimodal cues was comparable to that using mixed modality cues. The results of a subsequent experiment involving updating of target traces were consistent with those of the preceding experiments and support the view of modality-nonspecific memory.

Decision-diagram-based solutions for discrete optimization have been persistently studied. Among these is the use of the zero-suppressed binary decision diagram, a compact graph-based representation for a specified family of sets. Such a diagram may work out combinatorial problems by efficient enumeration. In brief, an extension to the frontierbased search approach for zero-suppressed binary decision diagram construction is proposed. The modification allows for the inclusion of a class-determined constraint in formulation. Variations of the generalized directed rural postman problem, proven to be nondeterministic polynomial-time hard, are solved on some rapid transit systems as illustration. Lastly, results are juxtaposed against standard integer programming in establishing the relative superiority of the new technique.

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to in NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins., 17 pages, 10 figures

Supplemental material, sj-docx-1-qjp-10.1177_17470218221103253 for Processing symmetry between visual and auditory spatial representations in updating working memory by Tomoki Maezawa and Jun I Kawahara in Quarterly Journal of Experimental Psychology

In this paper, we propose a fast method for exactly enumerating a very large number of all lower cost solutions for various combinatorial problems. Our method is based on backtracking for a given decision diagram which represents all the feasible solutions. The main idea is to memoize the intervals of cost bounds to avoid duplicate search in the backtracking process. In contrast to usual pseudo-polynomial-time dynamic programming approaches, the computation time of our method does not directly depend on the total cost values, but is bounded by the input and output size of the decision diagrams. Therefore, it can be much faster if the cost values are large but the input/output decision diagrams are well-compressed. We demonstrate its practical efficiency by comparing our method to current available enumeration methods: for nontrivial size instances of the Hamiltonian path problem, our method succeeded in exactly enumerating billions of all lower cost solutions in a few seconds, which was hundred or much more times faster. Our method can be regarded as a novel search algorithm which integrates the two classical techniques, branch-and-bound and dynamic programming. This method would have many applications in various fields, including operations research, data mining, statistical testing, hardware/software system design, etc., Comment: Related work (Section 6) is added. Experimental results for another set of problem instances (simple path problem) are added in Section 5.2. Some other minor corrections are made. Style file is changed to LIPIcs format

Supplemental material, sj-docx-1-qjp-10.1177_17470218221103253 for Processing symmetry between visual and auditory spatial representations in updating working memory by Tomoki Maezawa and Jun I Kawahara in Quarterly Journal of Experimental Psychology

Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce the reallocation problem that models the scheduling in which products are with fixed cost, non-fungible, and reallocated in parallel, and comprehensively study the complexity of the problem under various settings of the transition time, product size, and capacities. We show that the problem can be solved in polynomial time for a fundamental setting where the product size and transition time are both uniform. We also show that the feasibility of the problem is NP-complete even for little more general settings, which implies that no polynomial-time algorithm constructs a feasible schedule of the problem unless P$=$NP. We then consider the relaxation of the problem, which we call the capacity augmentation, and derive a reallocation schedule feasible with the augmentation such that the completion time is at most the optimal of the original problem. When the warehouse capacity is sufficiently large, we design constant-factor approximation algorithms under all the settings. We also show the relationship between the reallocation problem and the bin packing problem when the warehouse and carry-in capacities are sufficiently large., Comment: 24 pages, 2 figures

Subgraph enumeration is a fundamental task in computer science. Since the number of subgraphs can be large, some enumeration algorithms exploit compressed representations for efficiency. One such representation is the Zero-suppressed Binary Decision Diagram (ZDD). ZDDs can represent the set of subgraphs compactly and support several poly-time queries, such as counting and random sampling. Researchers have proposed efficient algorithms to construct ZDDs representing the set of subgraphs under several constraints, which yield fruitful results in many applications. Recently, Zero-suppressed Sentential Decision Diagrams (ZSDDs) have been proposed as variants of ZDDs. ZSDDs can be smaller than ZDDs when representing the same set of subgraphs. However, efficient algorithms to construct ZSDDs are known only for specific types of subgraphs: matchings and paths. We propose a novel framework to construct ZSDDs representing sets of subgraphs under given constraints. Using our framework, we can construct ZSDDs representing several sets of subgraphs such as matchings, paths, cycles, and spanning trees. We show the bound of sizes of constructed ZSDDs by the branch-width of the input graph, which is smaller than that of ZDDs by the path-width. Experiments show that our methods can construct ZSDDs faster than ZDDs and that the constructed ZSDDs are smaller than ZDDs when representing the same set of subgraphs., LIPIcs, Vol. 160, 18th International Symposium on Experimental Algorithms (SEA 2020), pages 9:1-9:14

Given graphs $G$ and $H$, we propose a method to implicitly enumerate topological-minor-embeddings of $H$ in $G$ using decision diagrams. We show a useful application of our method to enumerating subgraphs characterized by forbidden topological minors, that is, planar, outerplanar, series-parallel, and cactus subgraphs. Computational experiments show that our method can find all planar subgraphs in a given graph at most five orders of magnitude faster than a naive backtracking-based method.

Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. There are many subclasses of unigraphs such as threshold graphs, split matrogenic graphs, matroidal graphs, and matrogenic graphs. Unigraphs and these subclasses are well studied in the literature. Nevertheless, there are few results on superclasses of unigraphs. In this paper, we introduce two types of generalizations of unigraphs: $k$-unigraphs and $k$-strong unigraphs. We say that a graph $G$ is a $k$-unigraph if $G$ can be partitioned into $k$ unigraphs. $G$ is a $k$-strong unigraph if not only each subgraph is a unigraph but also the whole graph can be uniquely determined up to isomorphism, by using the degree sequences of all the subgraphs in the partition. We describe a relation between $k$-strong unigraphs and the subgraph isomorphism problem. We show some properties of $k$-(strong) unigraphs and algorithmic results on calculating the minimum $k$ such that a graph $G$ is a $k$-(strong) unigraph. This paper will open many other research topics.

The present study examined whether observers are able to establish multiple attentional sets to concurrently monitor two different spatial locations. Observers identified a target letter in red or cyan among nontarget letters of other heterogeneous colours during a temporal feature search. A peripheral distractor display consisted of one item of either the same colour as the current target, and the other potential target colour, or an irrelevant colour that could never be the target. They identified an odd-ball colour letter among homogenous colours during a singleton search. The results revealed that observers maintained multiple attentional sets for detecting two singletons or for targets involving two (or three) features. However, they were unable to maintain a mixture of sets. Moreover, exposure to a distractor containing feature that corresponded to a feature of the current target was advantageous for target identification. The presence or absence of this set-specific capture depended on top-down knowledge and did not occur automatically in the singleton-detection stream. These results demonstrate a limitation in the flexibility of attentional sets. Although two singleton detections were possible, multiple attentional templates for a more complex attentional set could not be maintained concurrently when monitoring multiple rapid serial visual presentations.

We investigated whether attentional set is available at the beginning of a trial or whether it develops gradually within a trial. Thus, we manipulated the time from the onset of a trial to a target and observers’ search strategy. We also observed the effect of the presence or absence of distractors as an index of the temporal development of attentional set. Participants identified a target letter embedded in a stream of rapidly presented nontargets while ignoring peripheral distractors. Baseline accuracy when no peripheral distractor was presented increased as the target appeared later in the stream, suggesting attentional awakening. Identification accuracy was impaired by the presence of peripheral distractors (i.e., attentional capture) early in the stream only when observers adopted the feature search mode. The magnitude of attentional capture increased over the course of the first 1,000 ms of a trial under the singleton detection and feature search modes. These results suggest that singleton detection mode requires time for a bottom-up signal to be effective in capturing attention, whereas the feature search mode does not require such a warm-up period to be effective and is available from the beginning of viewing the stream.

We propose a general method performed over multivalued decision diagrams that enumerates all subgraphs of an input graph that are characterized by input forbidden induced subgraphs. Our method combines elaborations of classical set operations and the developing construction technique, called the frontier based search, for multivalued decision diagrams. Using the algorithm, we enumerated all the chordal graphs of size at most 10 on multivalued decision diagrams.

Partitioning a graph into balanced components is important for several applications. For multi-objective problems, it is useful not only to find one solution but also to enumerate all the solutions with good values of objectives. However, there are a vast number of graph partitions in a graph, and thus it is difficult to enumerate desired graph partitions efficiently. In this paper, an algorithm to enumerate all the graph partitions such that all the weights of the connected components are at least a specified value is proposed. To deal with a large search space, we use zero-suppressed binary decision diagrams (ZDDs) to represent sets of graph partitions and we design a new algorithm based on frontier-based search, which is a framework to directly construct a ZDD. Our algorithm utilizes not only ZDDs but also ternary decision diagrams (TDDs) and realizes an operation which seems difficult to be designed only by ZDDs. Experimental results show that the proposed algorithm runs up to tens of times faster than an existing state-of-the-art algorithm.

Poly(3,4-ethylenedioxythiophene): polystyrene sulfonate (PEDOT:PSS) is an organic mixed ion-electron conducting polymer. The PEDOT phase transports holes and is redox-active, whereas the PSS phase transports ions. When PEDOT is redox-switched between its semiconducting and conducting state, the electronic and optical properties of its bulk are controlled. Therefore, it is appealing to use this transition in electrochemical devices and to integrate those into large-scale circuits, such as display or memory matrices. Addressability and memory functionality of individual devices, within these matrices, are typically achieved by nonlinear current-voltage characteristics and bistability-functions that can potentially be offered by the semiconductor-conductor transition of redox polymers. However, low conductivity of the semiconducting state and poor bistability, due to self-discharge, make fast operation and memory retention impossible. We report that a ferroelectric polymer layer, coated along the counter electrode, can control the redox state of PEDOT. The polarization switching characteristics of the ferroelectric polymer, which take place as the coercive field is overcome, introduce desired nonlinearity and bistability in devices that maintain PEDOT in its highly conducting and fast-operating regime. Memory functionality and addressability are demonstrated in ferro-electrochromic display pixels and ferro-electrochemical transistors. Funding Agencies|Advanced Functional Materials Center at Linkoping University; Onnesj Foundation; Knut and Alice Wallenberg Foundation; Swedish Foundation for Strategic Research; Swedish Governmental Agency for Innovation Systems (VINNOVA) [2015-04859]; Swedish Research Council [2016-03979]

application/pdf, 論文(Article)

When two targets are presented in a rapid stream of distractors, the accuracy of identifying the second target is impaired when the temporal lag between the targets is brief (attentional blink; AB). When the second target is presented immediately after the first target, the AB deficit is considerably reduced, a phenomenon called Lag-1 sparing. A recent study (Kristjansson & Nakayama, 2002) however, reported that Lag-1 sparing did not occur when multiple distractor streams were presented, although it had occurred in other studies (e.g., Peterson & Juola, 2000). The present study found that specific target attributes were the key for this inconsistency. When two targets in the same stream appear to be similar and are distinctive from the distractors, the first target is masked by the second. This masking of the first target increases the AB deficit, and Lag-1 sparing does not occur.

Electrically conducting polymers were discovered in the late 1970s. This finding generated a whole new research area named organic electronics, an area which has attracted great interest and tremendous achievements, in terms of devices and applications, have been reached by different research groups all over the world. Replacing inorganic materials by their organic counterparts in various kinds of electronic devices provides novel device functionalities as well as new opportunities in device manufacturing. One of the major advantages of utilizing organic materials in electronic devices is the high degree of freedom regarding fabrication methods. Since organic materials can be processed from solution various printing, coating and lamination techniques can be used to manufacture entire electronic systems on flexible carriers and substrates in a truly reel-to-reel fashion. The main theme of this thesis relates to exploring novel device architectures to enable easy manufacturing of flexible electrochromic displays based on organic materials. After the introduction, the second part of the thesis treats some of the fundamentals of conducting polymers, and the third part explains the building blocks of matrix-addressed electrochromic displays: those systems combine electrochemical transistors and electrochromic display pixels. A brief introduction to printed electronics is also given in the fourth section. Then, active matrix addressed displays utilizing electronic vias manufactured through the substrate, which enable to use the substrate more efficiently in the resulting three-dimensional architecture, are presented in the fifth section. This novel system arrangement results in a matrix-addressed display with a relatively high fill-factor since its subcomponents are located on opposite sides of the substrate. The sixth section of the thesis is related to the achievement of passive matrix addressed displays. The architecture and the manufacturing process of these electrochromic displays are both very simple: an electrolyte is sandwiched in between the counter and the pixel electrode layers. The electrode materials chosen results in a non-linear current versus voltage characteristics, which enables matrix addressability also without the transistors. At last, in the seventh section, nanofibrillated cellulose (NFC) is used as the scaffold for either an electroactive polymer or the electrolyte. Various components, such as electrochromic pixels and electrochemical transistors, can be built from the resulting solid films thanks to the stable, soft and tacky properties of the hybridized NFC layer. Hence, a new concept for integration and reconfiguration of electronic systems consisting of electrochemical devices is achieved.

Recently, the problems of evaluating performances of switches and routers have been formulated as online problems, and a great amount of results have been presented. In this paper, we focus on managing outgoing packets (called {\em egress traffic}) on switches that support Quality of Service (QoS), and analyze the performance of one of the most fundamental scheduling policies {\em Priority Queuing} ($PQ$) using competitive analysis. We formulate the problem of managing egress queues as follows: An output interface is equipped with $m$ queues, each of which has a buffer of size $B$. The size of a packet is unit, and each buffer can store up to $B$ packets simultaneously. Each packet is associated with one of $m$ priority values $\alpha_{j}$ ($1 \leq j \leq m$), where $\alpha_{1} \leq \alpha_{2} \leq \cdots \leq \alpha_{m}$, $\alpha_{1} = 1$, and $\alpha_{m} = \alpha$ and the task of an online algorithm is to select one of $m$ queues at each scheduling step. The purpose of this problem is to maximize the sum of the values of the scheduled packets. For any $B$ and any $m$, we show that the competitive ratio of $PQ$ is exactly $2 - \min_{x \in [1, m-1] } \{ \frac{ \alpha_{x+1} }{ \sum_{j = 1}^{x+1} \alpha_{j} } \}$. That is, we conduct a complete analysis of the performance of $PQ$ using worst case analysis. Moreover, we show that no deterministic online algorithm can have a competitive ratio smaller than $1 + \frac{ \alpha^3 + \alpha^2 + \alpha }{ \alpha^4 + 4 \alpha^3 + 3 \alpha^2 + 4 \alpha + 1 }$., Comment: 20 pages

The present study investigated phonological assembly in the Japanese language. Twenty-eight native Japanese speakers were presented with CVCVCV-structured words and nonwords in hiragana. Participants were asked to make lexical decisions for 25 words and 25 nonwords. In the assembly condition, meaningful words were anagrammed so that participants had to assemble apparently nonsensical morae into a meaningful unit in order to make a lexical decision. The reaction times for the assembly condition were substantially slower (a difference of 1770 ms) than those for the control condition. This result suggests that phonological assembly for three hiragana morae is involved in identifing meaningful words from the Japanese lexicon.

The present study investigated the effects of phrase length and scrambling in the processing of Japanese sentences. Reading times of short phrases, long phrases, verbs, and whole sentences, measured by the method of self-paced reading, did not differ in terms of phrase-length order and scrambling. In addition, four types of sentences constructed on the basis of phrase-length order and scrambling did not affect duration times of correctness decision-making for sentences. However, error rates differed between canonical and scrambled sentences regardless of phrase-length order. This result implies that scrambled sentences were harder to judge as correct sentences than canonical sentences. Thus, scrambling affects the appropriate integration of information, whereas phrase-length order is simply an indication of preference and not of cognitive processing. To explain the present result, the authors propose the “configurational structure without movement," which predicts no difference in speed between the processing of canonical and scrambled sentences, apart from error rates.

There is little extistent literature that has investigated the process involved in writing Japanese two-morpheme (kanji) compound words. One reason for this scarcity has been the difficulty in devising instruments to measure latencies for writing behaviour. To asnwere this problem, we developed software that enabled us to present auditory stimuli, to measure writing latencies, to track trajectories during the writing of kanji characters, and to assist data analysis. This software runs on the Microsoft Windows 98 Operating System with a commercially available pen-tablet. Technical details of this software will be explained in this paper.

During the identification of a target embedded in a rapid serial visual presentation sequence, observers frequently miss a target when it appears early in the sequence as compared to when it appears later. This phenomenon, called attentional awakening, reflects a gradual modulation of temporal attention for a rapid sequence. In this study, we inserted a temporal gap (0, 100, 500, or 1000ms) in the sequence and measured the critical conditions that destroyed the modulated state of temporal attention. The results showed that the correct identifications of the target were impaired immediately after the 1000-ms gap (Experiments 1). However, this impairment was eliminated by superimposing a continuous sequence of random dots so that the sequences temporally separated by the gap could be encapsulated as a single event (Experiment 2). These findings suggested that the temporally modulated attention could be maintained within a single event., Summary of Awarded Presentation at the 26th Annual Meeting

2012年3月20日-23日 岡山大学 C-1-11, 本文データは学協会の許諾に基づきCiNiiから複製したものである