检索结果-内蒙古大学图书馆

Lower bound for the length of synchronizing words in partially-synchronizing automata 1

34th conference on current trends in theory and practice of computer science

作者： Roman, Adam Forys, Wit Jagiellonian Univ Inst Comp Sci Krakow Poland

ISBN: (数字)9783540775669

ISBN: (纸本)9783540775652

We introduce the generalized notion of automata synchronization, so called partial synchronization, which holds for automata with partial transition function. We give a lower bound for the length of minimal synchronizing words for partial synchronizing automata. the difference, in comparison to the 'classical' synchronization, lies in the initial conditions: let A = (Q, A, delta) be an automaton representing the dynamics of a particular system. In case of partial synchronization we assume that initial conditions (initial state of the system) can be represented by some particular states, that is by some P C Q, not necessarily by all possible states from Q. At first glance the above assumption limits our room for manoeuvre for constructing possibly long minimal synchronizing words (because of the lower number of states at the beginning). Unexpectedly this assumption allows us to construct longer minimal synchronizing words than in a standard case. In our proof we use Sperner's theorem and some basic combinatorics.

关键词： Automata theory

来源：评论

学校读者我要写书评

暂无评论

Untangling a planar graph 1

引用

34th conference on current trends in theory and practice of computer science

作者： Spillner, Andreas Wolff, Alexander Univ E Anglia Sch Comp Sci Norwich Norfolk England Fact Wiskunde Informat Eindhoven Netherlands

ISBN: (数字)9783540775669

ISBN: (纸本)9783540775652

In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. the aim is to make the drawing plane as quickly as possible by moving vertices. Pach and Tardos have posed a related problem: can any straight-line drawing of any planar graph with n vertices be made plane by vertex moves while keeping Omega(n(epsilon)) vertices fixed for some absolute constant epsilon > 0? It is known that three vertices can always be kept (if n > 5). We still do not solve the problem of Pach and Tardos, but we report some progress. We prove that the number of vertices that can be kept actually grows with the size of the graph. More specifically, we give a lower bound of Omega(root log n/ log log n) on this number. By the same technique we show that in the case of outerplanar graphs we can keep a lot more, namely Omega(root n) vertices. We also construct a family of outerplanar graphs for which this bound is asymptotically tight.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Geometrie rates of approximation by neural networks

Geometrie rates of approximation by neural networks

引用

SOFSEM 2008 - 34th conference on current trends in theory and practice of computer science

作者： Kůrková, Věra Sanguineti, Marcello Institute of Computer Science Academy of Sciences of the Czech Republic Pod Vodárenskou věží 2 Prague 8 Czech Republic University of Genova Via Opera Pia 13 16145 Genova Italy

ISBN: (纸本)354077565X

Model complexity of feedforward neural networks is studied in terms of rates of variable-basis approximation. Sets of functions, for which the errors in approximation by neural networks with n hidden units converge to zero geometrically fast with increasing number n, are described. However, the geometric speed of convergence depends on parameters, which are specific for each function to be approximated. the results are illustrated by examples of estimates of such parameters for functions in infinite-dimensional Hulbert spaces. © Springer-Verlag Berlin Heidelberg 2008.

关键词： Approximation theory

来源：评论

学校读者我要写书评

暂无评论

Verifying parameterized taDOM+ lock managers 1

引用

SOFSEM 2008 - 34th conference on current trends in theory and practice of computer science

作者： Siirtola, Antti Valenta, Michal University of Oulu Department of Information Processing Science PL 3000 90014 Oulu Finland Czech Technical University in Prague Faculty of Electrical Engineering Department of Computer Science and Engineering Karlovo námesti 13 121 35 Prague 2 Czech Republic

ISBN: (数字)9783540775669

ISBN: (纸本)354077565X

taDOM* protocols are designed to provide lock-based approach to handle multiple access to XML databases. the notion of taDOM+ protocol is formalized and generalized and a formal model of taDOM+ lock manager that is parameterized in the number of transactions and in the size of database is represented. An important class of safety properties of taDOM+ lock managers were proven to be checked by examining just a small number of finite-state instances of the parameterized model. Our results were applied to prove a generalized mutual exclusion property, known as repeatable-read, of taDOM2+ and taDOM3+ lock managers by model-checking. © Springer-Verlag Berlin Heidelberg 2008.

关键词： Network protocols

来源：评论

学校读者我要写书评

暂无评论

Programming in groups: A progression learning scheme from the individual to the group

Programming in groups: A progression learning scheme from th...

引用

Frontiers in Education (FIE) conference

作者： thais Castro Hugo Fuks Alberto Castro Department of Informatics Catholic University of Rio de Janeiro Rio de Janeiro Brazil Computer Science Department Federal University of Amazonas Manaus Amazonas Brazil

the technical literature in cognitive science informs that working in groups reaps more benefits than working alone. We are seeing a variety of innovative group programming methodologies like the agile methods. this work examines the findings of a pilot study carried out during the first academic semester of 2007. the subjects were 110 freshmen computing and engineering students taking their first programming course at the Federal University of Amazonas. Based on these findings, it is proposed a programming progression learning scheme, from individual (current practice) to group programming (the desired practice based on the literature review). Such transition is necessary for students are not used to programming in groups. In order to evaluate such progression learning scheme a case study is outlined.

关键词： Programming profession Collaboration Problem-solving Educational products Informatics computer science Cognitive science Engineering students Education Psychology

来源：评论

学校读者我要写书评

暂无评论

Lecture Notes in computer science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics: Preface

Lecture Notes in Computer Science (including subseries Lectu...

引用

Lecture Notes in computer science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2008年 4910 LNCS卷 v-vi页

作者： Geffert, Viliam Karhumaki, Juhani Bertoni, Alberto Preneel, Bart Navrat, Pavol Bielikova, Maria

No abstract available

ISBN: (纸本)354077565X

No abstract available

关键词：

来源：评论

学校读者我要写书评

暂无评论

Work in progress-improving feedback using an automatic assessment tool

Work in progress-improving feedback using an automatic asses...

引用

Frontiers in Education (FIE) conference

作者： Daniel Jimenez-Gonzalez Carlos Alvarez David Lopez Joan-M. Parcerisa Javier Alonso Christian Perez Ruben Tous Pere Barlet Montse Fernandez Jordi Tubella Computer Architecture Department Technical University of Catalonia Spain

Students of computer science freshman year usually develop assembler programs to learn processor architecture. Homework exercises are done on paper, while those in lab sessions are solved with the aid of programming tools. Students perceive theory and lab as different subjects, so they donpsilat use lab tools to test their theory solved problems. Moreover, during lab sessions, students often tend to ask for the teacherpsilas guide and advice instead of using the debugging tools because these are new and unfriendly for them, and do not offer a quick and clear feedback. In this paper we present an automatic and friendly assessment tool, SISA-EMU, with a novel feature: exercise driven feedback with teacherpsilas expertise. It provides correctness information and clues to help the students solve their most common mistakes for each individual problem (and not typical generic debug information) without the physical support of a teacher. SISA-EMU is currently in pre-deploy phase via a Moodle learning platform and we will have first evaluation results by the end of the current term.

关键词： computer architecture Debugging computer science Testing State feedback Automatic programming Memory architecture Computational modeling Assembly systems Costs

来源：评论

学校读者我要写书评

暂无评论

Maximum finding in the symmetric radio networks with collision detection

Maximum finding in the symmetric radio networks with collisi...

引用

33rd conference on current trends in theory and practice of computer science

作者： Galcik, Frantisek Semanisin, Gabriel Safarik Univ Fac Sci Inst Comp Sci Kosice 04154 Slovakia

ISBN: (纸本)9783540695066

We consider a problem of computing the maximal value associated to the nodes of a network in the model of unknown symmetric radio network with availability of collision detection. We assume that the nodes have no initial knowledge about the network topology, number of nodes and even they have no identifiers. the network contains one distinguished node, called initiator, that starts the process of computing. We design a series of algorithms that result into an asymptotically optimal deterministic algorithm completing the task in theta(ecc + log Max) rounds, where ecc is the eccentricity of the initiator and Max is the maximal value among the integer values associated to the nodes. Some other utilisations of the developed algorithm are presented as well.

关键词： Computation theory

来源：评论

学校读者我要写书评

暂无评论

A model of an amorphous computer and its communication protocol

A model of an amorphous computer and its communication proto...

引用

33rd conference on current trends in theory and practice of computer science

作者： Petru, Lukas Wiedermann, Jiri Charles Univ Prague Fac Math & Phys Malostranske Namesti 25 CR-11800 Prague 1 Czech Republic Acad Sci Czech Republic Inst Comp Sci Prague 18207 Czech Republic

ISBN: (纸本)9783540695066

We design a formal model of an amorphous computer suitable for theoretical investigation of its computational properties. the model consists of a finite set of nodes created by RAMs with restricted memory, which are dispersed uniformly in a given area. Within a limited radius the nodes can communicate with their neighbors via a single-channel radio. the assumptions on low-level communication abilities are among the weakest possible: the nodes work asynchronously, there is no broadcasting collision detection mechanism and no network addresses. For the underlying network we design a randomized communication protocol and analyze its efficiency. the subsequent experiments and combinatorial analysis of random networks show that the expectations under which our protocol was designed are met by the vast majority of the instances of our amorphous computer model.

关键词： Network protocols

来源：评论

学校读者我要写书评

暂无评论

Partial vs. complete domination:: t-dominating set

Partial vs. complete domination:: <i>t</i>-dominating set

引用

33rd conference on current trends in theory and practice of computer science

作者： Kneis, Joachim Moelle, Daniel Rossmanith, Peter Univ Aachen Rhein Westfal TH Aachen Dept Comp Sci D-5100 Aachen Germany

ISBN: (纸本)9783540695066

We examine the parameterized complexity of t-DOMINATING SET, the problem of finding a set of at most k nodes that dominate at least t nodes of a graph G = (V, E). the classic NP-complete problem DOMINATING SET, which can be seen to be t-DOMINATING SET with the restriction that t = n, has long been known to be W[2]-complete when parameterized in k. Whereas this implies W[2]-hardness for t-DOMINATING SET and the parameter k, we are able to prove fixed-parameter tractability for t-DOMINATING SET and the parameter t. More precisely, we obtain a quintic problem kernel and a randomized O((4 + epsilon)(t) poly(n)) algorithm. the algorithm is based on the divide-and-color method introduced to the community earlier this year, rather intuitive and can be derandomized using a standard framework.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：