A theory of one-tape linear-time Turing machines is quite different from its polynomial-time counterpart. this paper discusses the computational complexity of one-tape Turing machines of various machine types (determi...
详细信息
this book constitutes the refereed proceedings of the 40th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2014, held in Nový Smokovec, Slovakia, in January 2014. the...
详细信息
ISBN:
(数字)9783319042985
ISBN:
(纸本)9783319042978
this book constitutes the refereed proceedings of the 40th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2014, held in Nový Smokovec, Slovakia, in January 2014. the 40 revised full papers presented in this volume were carefully reviewed and selected from 104 submissions. the book also contains 6 invited talks. the contributions covers topics as: Foundations of computerscience, Software and Web Engineering, as well as Data, Information and Knowledge Engineering and Cryptography, Security and Verification.
this paper covers an international collaborative teaching project involving the design of a state-of-the-art microprocessor and embedded system between the University of New South Wales, Manchester University and the ...
详细信息
We introduce restarting automata as two-way automata in order to obtain a more general model which is closer to our linguistic motivations. We study the notion of j-monotonicity to show the advantages of this model. W...
详细信息
this paper considers a game in which a single cop and a single robber take turns moving along the edges of a given graph G. If there exists a strategy for the cop which enables it to be positioned at the same vertex a...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
this paper considers a game in which a single cop and a single robber take turns moving along the edges of a given graph G. If there exists a strategy for the cop which enables it to be positioned at the same vertex as the robber eventually, then G is called cop-win, and robber-win otherwise. In contrast to previous work, we study this classical combinatorial game on edge-periodic graphs. these are graphs with an infinite lifetime comprised of discrete time steps such that each edge e is assigned a bit pattern of length le, with a 1 in the i-th position of the pattern indicating the presence of edge e in the i-th step of each consecutive block of le steps. Utilising the known framework of reachability games, we obtain an O(LCM(L) . n(3)) time algorithm to decide if a given n-vertex edge-periodic graph Gt is cop-win or robber-win as well as compute a strategy for the winning player (here, L is the set of all edge pattern lengths le, and LCM(L) denotes the least common multiple of the set L). For the special case of edge-periodic cycles, we prove an upper bound of 2 . l . LCM(L) on the minimum length required of any edge-periodic cycle to ensure that it is robber-win, where l = 1 if LCM(L) = 2 . maxL, and l = 2 otherwise. Furthermore, we provide constructions of edge-periodic cycles that are cop-win and have length 1.5 . LCM(L) in the l = 1 case and length 3 . LCM(L) in the l = 2 case.
the rise of social media encouraged customers to share information more frequently and to larger extent. Previous work primarily focused on how and why customers share information in online social commerce sites. In t...
详细信息
ISBN:
(纸本)9781634396943
the rise of social media encouraged customers to share information more frequently and to larger extent. Previous work primarily focused on how and why customers share information in online social commerce sites. In the current study, we distinguish between the two types of users: sellers and non-sellers in social commerce sites. Drawing on the goal theory, we empirically examine intrinsic and extrinsic benefits as the key direct antecedents, and explore the moderating role of sellers/non-sellers in the relationship between intrinsic and extrinsic benefits and information sharing behavior. Analyzing survey data (n=1170) in the first phase collected from a popular social commerce site, we found that intention to share information among sellers and nonsellers are indeed different. this study can advance the understandings of information sharing literature by revealing the differences between different types of users. the results offer important and interesting insights to IS research and practice.
the predominant paradigm in evolutionary game theory and more generally online learning in games is based on a clear distinction between a population of dynamic agents that interact given a fixed, static game. In this...
详细信息
ISBN:
(纸本)9781577358664
the predominant paradigm in evolutionary game theory and more generally online learning in games is based on a clear distinction between a population of dynamic agents that interact given a fixed, static game. In this paper, we move away from the artificial divide between dynamic agents and static games, to introduce and analyze a large class of competitive settings where boththe agents and the games they play evolve strategically over time. We focus on arguably the most archetypal game-theoretic setting-zero-sum games (as well as network generalizations)-and the most studied evolutionary learning dynamic-replicator, the continuous-time analogue of multiplicative weights. Populations of agents compete against each other in a zero-sum competition that itself evolves adversarially to the current population mixture. Remarkably, despite the chaotic coevolution of agents and games, we prove that the system exhibits a number of regularities. First, the system has conservation laws of an information-theoretic flavor that couple the behavior of all agents and games. Secondly, the system is Poincare recurrent, with effectively all possible initializations of agents and games lying on recurrent orbits that come arbitrarily close to their initial conditions infinitely often. thirdly, the time-average agent behavior and utility converge to the Nash equilibrium values of the time-average game. Finally, we provide a polynomial time algorithm to efficiently predict this time-average behavior for any such coevolving network game.
the proceedings contain 22 papers. the special focus in this conference is on System Design, Testing Related theory, Parallel Systems and Vision. the topics include: Conformance testing techniques for timed systems;co...
ISBN:
(纸本)354000145X
the proceedings contain 22 papers. the special focus in this conference is on System Design, Testing Related theory, Parallel Systems and Vision. the topics include: Conformance testing techniques for timed systems;counter-constrained finite state machines;a new model for component protocols with resource-dependencies;equivalence-checking with infinite-state systems;database support for multisource multiresolution scientific data;semantic annotation and indexing of news and sports videos;interactive indexing and retrieval of multimedia content;a model-based approach to semantic-based retrieval of visual information;bipolarity in possibilistic logic and fuzzy rules;data management challenges for grid computing;Hungarian speech synthesis using a phase exact HNM approach;modelling resource transitions in constraint-based scheduling;a specification framework for real- time scheduling;validation and decomposition of partially occluded images;solving conflicts of agent knowledge states in multiagent systems;specification and verification of secure business transaction systems;agent- oriented model of simulated evolution;the reconstruction of some 3d convex polyominoes from orthogonal projections and the complexity of probabilistic versus quantum finite automata.
For a fixed graph H, the H-CONTRACTIBILITY problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. the computational complexity classification of tins problem is s...
详细信息
ISBN:
(纸本)9783642112652
For a fixed graph H, the H-CONTRACTIBILITY problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. the computational complexity classification of tins problem is still open. So far, H has a dominating vertex in all cases known to be polynomially solvable, whereas H does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-CONTRACTIBILITY is NP-complete. We also present a new class of graphs H for which H-CONTRACTIBILITY is polynomially solvable. Furthermore, we study the (H,v)-CONTRACTIBILITY problem, where v is a vertex of H. the input of this problem is a graph G and an integer k. the question is whether G is H-contractible such that the "bag" of G corresponding to v contains at least k vertices. We show that this problem is NP-complete whenever H is connected and v is not a dominating vertex of H.
暂无评论