Matematik til informatikfag

The evaluation of a logical formula can be viewed as a game played by two opponents, one trying to show that the formula is true and the other trying to prove it is false. This correspondence has been known for a very long time and has inspired numerous research directions. In this book, the author extends this connection between logic and games to the class of automatic structures, where relations are recognized by synchronous finite automata.In model-checking games for automatic structures, two coalitions play against each other with a particular kind of hierarchical imperfect information. The investigation of such games leads to the introduction of a game quantifier on automatic structures, which connects alternating automata with the classical model-theoretic notion of a game quantifier. This study is then extended, determining the memory needed for strategies in infinitary games on the one hand, and characterizing regularity-preserving Lindström quantifiers on the other. Counting quantifiers are investigated in depth: it is shown that all countable omega-automatic structures are in fact finite-word automatic and that the infinity and uncountability set quantifiers are definable in MSO over countable linear orders and over labeled binary trees.This book is based on the PhD thesis of Lukasz Kaiser, which was awarded with the E.W. Beth award for outstanding dissertations in the fields of logic, language, and information in 2009. The work constitutes an innovative study in the area of algorithmic model theory, demonstrating the deep interplay between logic and computability in automatic structures. It displays very high technical and presentational quality and originality, advances significantly the field of algorithmic model theory and raises interesting new questions, thus emerging as a fruitful and inspiring source for future research.

This book constitutes the refereed proceedings of the 16th Australasian Conference on Information Security and Privacy, ACISP 2011, held in Melbourne, Australia, in July 2011. The 24 revised full papers presented together with an invited talk and 9 poster papers were carefully reviewed and selected from 103 submissions. The papers are organized in topical sections on symmetric key cryptography, hash functions, cryptographic protocols, access control and security, and public key cryptography.

This book constitutes the joint refereed proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011, and the 15th International Workshop on Randomization and Computation, RANDOM 2011, held in Princeton, New Jersey, USA, in August 2011. The volume presents 29 revised full papers of the APPROX 2011 workshop, selected from 66 submissions, and 29 revised full papers of the RANDOM 2011 workshop, selected from 64 submissions. They were carefully reviewed and selected for inclusion in the book. In addition two abstracts of invited talks are included.APPROX focuses on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM is concerned with applications of randomness to computational and combinatorial problems.

This book constitutes the refereed proceedings of the 31st Annual International Cryptology Conference, CRYPTO 2011, held in Santa Barbara, CA, USA in August 2011. The 42 revised full papers presented were carefully reviewed and selected from 230 submissions. The volume also contains the abstract of one invited talk. The papers are organized in topical sections on randomness and its use; computer-assisted cryptographic proofs; outsourcing and delegatin computation; symmetric cryptanalysis and constructions; secure computation: leakage and side channels; quantum cryptography; lattices and knapsacks; public-key encryption; symmetric schemes; signatures; obilvious transfer and secret sharing; and multivariate and coding-based schemes.

This book constitutes the refereed proceedings of the 5th International Conference on Combinatorial Optimization and Applications, COCOA 2011, held in Zhangjiajie, China, in August 2011. The 43 revised full papers were carefully reviewed and selected from 65 submissions. The papers cover a broad range of topics in combinatorial optimization and applications focussing on experimental and applied research of general algorithmic interest and research motivated by real-world problems.

This book constitutes the refereed proceedings of the 5th International Conference on Network Optimization, INOC 2011, held in Hamburg, Germany, in June 2011. The 65 revised full papers presented were carefully reviewed and selected from numerous submissions. The papers highlight recent developments in network optimization and are organized in the following topical sections: theoretical problems, uncertainty, graph theory and network design; network flows; routing and transportation; and further optimization problems and applications (energy oriented network design, telecom applications, location, maritime shipping, and graph theory).

This book constitutes the thoroughly refereed post-conference proceedings of the 18th International Workshop on Fast Software Encryption, held in Lyngby, Denmark, in February 2011. The 22 revised full papers presented together with 1 invited lecture were carefully reviewed and selected from 106 initial submissions. The papers are organized in topical sections on differential cryptanalysis, hash functions, security and models, stream ciphers, block ciphers and modes, as well as linear and differential cryptanalysis.

This book constitutes the refereed proceedings of the 7th Conference on Computability in Europe, CiE 2011, held in Sofia, Bulgaria, in June/July 2011. The 22 revised papers presented together with 11 invited lectures were carefully reviewed and selected with an acceptance rate of under 40%.The papers cover the topics computability in analysis, algebra, and geometry; classical computability theory; natural computing; relations between the physical world and formal models of computability; theory of transfinite computations; and computational linguistics.

This book constitutes the refereed proceedings of the 9th International Conference on Applied Cryptography and Network Security, ACNS 2011, held in Nerja, Spain, in June 2011. The 31 revised full papers included in this volume were carefully reviewed and selected from 172 submissions. They are organized in topical sessions on malware and intrusion detection; attacks, applied crypto; signatures and friends; eclectic assortment; theory; encryption; broadcast encryption; and security services.

The three-volume set LNCS 6675, 6676 and 6677 constitutes the refereed proceedings of the 8th International Symposium on Neural Networks, ISNN 2011, held in Guilin, China, in May/June 2011. The total of 215 papers presented in all three volumes were carefully reviewed and selected from 651 submissions. The contributions are structured in topical sections on computational neuroscience and cognitive science; neurodynamics and complex systems; stability and convergence analysis; neural network models; supervised learning and unsupervised learning; kernel methods and support vector machines; mixture models and clustering; visual perception and pattern recognition; motion, tracking and object recognition; natural scene analysis and speech recognition; neuromorphic hardware, fuzzy neural networks and robotics; multi-agent systems and adaptive dynamic programming; reinforcement learning and decision making; action and motor control; adaptive and hybrid intelligent systems; neuroinformatics and bioinformatics; information retrieval; data mining and knowledge discovery; and natural language processing.

This book constitutes the refereed proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2011, held in Tallinn, Estonia, in May 2011.The 31 papers, presented together with 2 invited talks, were carefully reviewed and selected from 167 submissions. The papers are organized in topical sections on lattice-base cryptography, implementation and side channels, homomorphic cryptography, signature schemes, information-theoretic cryptography, symmetric key cryptography, attacks and algorithms, secure computation, composability, key dependent message security, and public key encryption.

This book constitutes the refereed proceedings of the 14th International Conference on Formal Grammar 2009, held in Bordeaux, France, in July 2009. The 13 revised full papers presented, including two invited talks, were carefully reviewed and selected from 26 submissions. These articles in this book give an overview of new and original research on formal grammar, mathematical linguistics and the application of formal and mathematical methods to the study of natural language.

The sequencing of the genomes of humans and other organisms is inspiring the developmentofnew statisticalandbioinformatics tools that we hope canmodify the current understanding of human diseases and therapies. As our knowledge about the human genome increases so does our belief that to fully grasp the mechanisms of diseases we need to understand their genetic basis and the p- teomicsbehind them and to integratethe knowledgegeneratedin thelaboratory in clinical settings. The new genetic and proteomic data has brought forth the possibility of developing new targets and therapies based on these ?ndings, of implementing newly developed preventive measures, and also of discovering new research approaches to old problems. To fully enhance our understanding of disease processes, to develop more and better therapies to combat and cure diseases, and to develop strategies to prevent them, there is a need for synergy of the disciplines involved, medicine, molecular biology, biochemistry and computer science, leading to more recent ?elds such as bioinformatics and biomedical informatics. The 6th International Symposium on Biological and Medical Data Analysis aimed to become a place where researchersinvolved in these diversebut incre- ingly complementary areas could meet to present and discuss their scienti?c results. The papers in this volume discuss issues from statistical models to arc- tectures and applications to bioinformatics and biomedicine. They cover both practical experience and novel research ideas and concepts.

The Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) is a leading international conference in the area of data mining and knowledge discovery. It provides an international forum for researchers and industry practitioners to share their new ideas, original research results and practical development experiences from all KDD-related areas including data mining, data warehousing, machine learning, databases, statistics, knowledge acquisition and automatic scientific discovery, data visualization, causality induction, and knowledge-based systems. This year's conference (PAKDD 2005) was the ninth of the PAKDD series, and carried the tradition in providing high-quality technical programs to facilitate research in knowledge discovery and data mining. It was held in Hanoi, Vietnam at the Melia Hotel, 18-20 May 2005. We are pleased to provide some statistics about PAKDD 2005. This year we received 327 submissions (a 37% increase over PAKDD 2004), which is the highest number of submissions since the first PAKDD in 1997) from 28 countries/regions: Australia (33), Austria (1), Belgium (2), Canada (11), China (91), Switzerland (2), France (9), Finland (1), Germany (5), Hong Kong (11), Indonesia (1), India (2), Italy (2), Japan (21), Korea (51), Malaysia (1), Macau (1), New Zealand (3), Poland (4), Pakistan (1), Portugal (3), Singapore (12), Taiwan (19), Thailand (7), Tunisia (2), UK (5), USA (31), and Vietnam (9). The submitted papers went through a rigorous reviewing process. Each submission was reviewed by at least two reviewers, and most of them by three or four reviewers.

This volume contains the proceedings of the 15th Annual International Sym- sium on Algorithms and Computation (ISAAC 2004), held in Hong Kong, 20-22 December, 2004. In the past, it has been held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), Vancouver (2002), and Kyoto (2003). ISAAC is an annual international symposium that covers a wide range of topics,namelyalgorithmsandcomputation.Themainpurposeofthesymposium is to provide a forum for researchers working in the active research community of algorithms and the theory of computation to present and exchange new ideas. In response to our call for papers we received 226 submissions. The task of selectingthepapersinthisvolumewasdonebyourprogramcommitteeandother referees. After a thorough review process the committee selected 76 papers, the decisions being based on originality and relevance to the ?eld of algorithms and computation. We hope all accepted papers will eventually appear in scienti?c journals in a more polished form. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications, with selected papers from ISAAC 2004 are in preparation. Thebeststudentpaperawardwillbegivenfor"Geometricoptimizationpr- lems over sliding windows" by Bashir S. Sadjad and Timothy M. Chan from the University of Waterloo. Two eminent invited speakers, Prof. Erik D. Demaine, MIT, and Prof. David M. Mount, University of Maryland, also contributed to this volume.

This book provides an introduction to practical formal modelling techniques in the context of object-oriented system design. It is aimed at both practising software engineers with some prior experience of object-oriented design/programming and at intermediate or advanced students studying object-oriented design or modelling in a short course. The following features make this book particularly attractive to potential instructors: § The relationship with UML and object-oriented programming makes it easy to integrate with the mainstream computing curriculum. Although the book is about formal methods, it does not have to be treated as a specialist topic. § The use of tools and an accessible modelling language improves student motivation. § The industry-based examples and case studies add to the credibility of the approach. § The light touch approach means that the material appeals to students with a wider range of abilities than is the case in a conventional formal methods text. § Support materials as listed above.

This book constitutes the proceedings of the International Symposium on Neural N- works (ISNN 2004) held in Dalian, Liaoning, China duringAugust 19-21, 2004. ISNN 2004 received over 800 submissions from authors in ?ve continents (Asia, Europe, North America, South America, and Oceania), and 23 countries and regions (mainland China, Hong Kong, Taiwan, South Korea, Japan, Singapore, India, Iran, Israel, Turkey, Hungary, Poland, Germany, France, Belgium, Spain, UK, USA, Canada, Mexico, - nezuela, Chile, andAustralia). Based on reviews, the Program Committee selected 329 high-quality papers for presentation at ISNN 2004 and publication in the proceedings. The papers are organized into many topical sections under 11 major categories (theo- tical analysis; learning and optimization; support vector machines; blind source sepa- tion,independentcomponentanalysis,andprincipalcomponentanalysis;clusteringand classi?cation; robotics and control; telecommunications; signal, image and time series processing; detection, diagnostics, and computer security; biomedical applications; and other applications) covering the whole spectrum of the recent neural network research and development. In addition to the numerous contributed papers, ?ve distinguished scholars were invited to give plenary speeches at ISNN 2004. ISNN 2004 was an inaugural event. It brought together a few hundred researchers, educators,scientists,andpractitionerstothebeautifulcoastalcityDalianinnortheastern China. It provided an international forum for the participants to present new results, to discuss the state of the art, and to exchange information on emerging areas and future trends of neural network research. It also created a nice opportunity for the participants to meet colleagues and make friends who share similar research interests.

The natural mission of Computational Science is to tackle all sorts of human problems and to work out intelligent automata aimed at alleviating the b- den of working out suitable tools for solving complex problems. For this reason ComputationalScience,thoughoriginatingfromtheneedtosolvethemostch- lenging problems in science and engineering (computational science is the key player in the ?ght to gain fundamental advances in astronomy, biology, che- stry, environmental science, physics and several other scienti?c and engineering disciplines) is increasingly turning its attention to all ?elds of human activity. In all activities, in fact, intensive computation, information handling, kn- ledge synthesis, the use of ad-hoc devices, etc. increasingly need to be exploited and coordinated regardless of the location of both the users and the (various and heterogeneous) computing platforms. As a result the key to understanding the explosive growth of this discipline lies in two adjectives that more and more appropriately refer to Computational Science and its applications: interoperable and ubiquitous. Numerous examples of ubiquitous and interoperable tools and applicationsaregiveninthepresentfourLNCSvolumescontainingthecontri- tions delivered at the 2004 International Conference on Computational Science and its Applications (ICCSA 2004) held in Assisi, Italy, May 14-17, 2004.

The natural mission of Computational Science is to tackle all sorts of human problems and to work out intelligent automata aimed at alleviating the b- den of working out suitable tools for solving complex problems. For this reason ComputationalScience,thoughoriginatingfromtheneedtosolvethemostch- lenging problems in science and engineering (computational science is the key player in the ?ght to gain fundamental advances in astronomy, biology, che- stry, environmental science, physics and several other scienti?c and engineering disciplines) is increasingly turning its attention to all ?elds of human activity. In all activities, in fact, intensive computation, information handling, kn- ledge synthesis, the use of ad-hoc devices, etc. increasingly need to be exploited and coordinated regardless of the location of both the users and the (various and heterogeneous) computing platforms. As a result the key to understanding the explosive growth of this discipline lies in two adjectives that more and more appropriately refer to Computational Science and its applications: interoperable and ubiquitous. Numerous examples of ubiquitous and interoperable tools and applicationsaregiveninthepresentfourLNCSvolumescontainingthecontri- tions delivered at the 2004 International Conference on Computational Science and its Applications (ICCSA 2004) held in Assisi, Italy, May 14-17, 2004.

Crypto 2003, the 23rd Annual Crypto Conference, was sponsored by the Int- national Association for Cryptologic Research (IACR) in cooperation with the IEEE Computer Society Technical Committee on Security and Privacy and the Computer Science Department of the University of California at Santa Barbara. The conference received 169 submissions, of which the program committee selected 34 for presentation. These proceedings contain the revised versions of the 34 submissions that were presented at the conference. These revisions have not been checked for correctness, and the authors bear full responsibility for the contents of their papers. Submissions to the conference represent cutti- edge research in the cryptographic community worldwide and cover all areas of cryptography. Many high-quality works could not be accepted. These works will surely be published elsewhere. The conference program included two invited lectures. Moni Naor spoke on cryptographic assumptions and challenges. Hugo Krawczyk spoke on the 'SI- and-MAc'approachtoauthenticatedDi?e-HellmananditsuseintheIKEpro- cols. The conference program also included the traditional rump session, chaired by Stuart Haber, featuring short, informal talks on late-breaking research news. Assembling the conference program requires the help of many many people. To all those who pitched in, I am forever in your debt. I would like to ?rst thank the many researchers from all over the world who submitted their work to this conference. Without them, Crypto could not exist. I thank Greg Rose, the general chair, for shielding me from innumerable logistical headaches, and showing great generosity in supporting my e?orts.

Computational Science is becoming a vital part of many scienti?c investi- tions, impacting researchers and practitioners in areas ranging from aerospace andautomotiveto chemistry,electronics,geosciences,?nance,mathematics,and physics. Due to the sheer size of many challenges in computational science, the use of supercomputing, parallel processing, and sophisticated algorithms is - evitable. This volume contains the proceedings of The 2003 International Conference on Computational Science and Its Applications (ICCSA 2003), held in M- treal, Canada in May 2003. The papers presented here re?ect the aim of the programcommittee to bring together researchersand scientists from mathem- ics and computer science, the basic computing disciplines, and researchers from various application areas who are pioneering advanced application of compu- tional methods to sciences such as physics, chemistry, life sciences, engineering, arts, and the humanities, along with software developers and vendors, to d- cuss problems and solutions in the area, identify new issues, and shape future directions for research, as well as help industrial users apply various advanced computational techniques. Our outstanding invited speakers outlined the theme for the Conference, consideringsophisticatednumericalcomputationalmethods,emergingcompu- tional solutions, and problems and applications pushing the bounds of advanced computing techniques and hardware. This Conference was held as the ?rst in its series, with an emphasis on C- putational Science and the application of computational science. Interest from researchers and practitioners in this interdisciplinary area has been overwhe- ing, and we are looking forward to future events in this Conference series.

This volume spans the whole field of computational logic seen from the point of view of logic programming. The topics addressed range from issues concerning the development of programming languages in logic and the application of computational logic to real-life problems, to philosophical studies of the field at the other end of the spectrum. The articles presented cover the contributions of computational logic to databases and artificial intelligence with particular emphasis on automated reasoning, reasoning about actions and change, natural languages, and learning.Together with its companion volume, LNAI 2407, this book commemorates the 60th birthday of Bob Kowalski as one of the founders of and contributors to computational logic.

This volume introduces recent developments of Partial Differential Equations (PDEs) in the field of Geometric Design. The text is written with a particular emphasis on computer based design and analysis involving the geometry of physical objects.