Matematisk datateori

This book constitutes the refereed proceedings of the 19th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG which took place in La Jolla, USA, during May 20-21, 2022. The 18 full papers included in this book were carefully reviewed and selected from 28 submissions. The papers were organized in topical sections on evolution; phylogenetics; homology and reconciliation; genome rearrangements; metagenomics; and genomic sequencing.

This book constitutes the proceedings of the 26th Annual Conference on Research in Computational Molecular Biology, RECOMB 2022, held in San Diego, CA, USA in May 2022. The 17 regular and 23 short papers presented were carefully reviewed and selected from 188 submissions. The papers report on original research in all areas of computational molecular biology and bioinformatics.

This book constitutes the refereed proceedings of the 10th European Conference on Artificial Intelligence in Music, Sound, Art and Design, EvoMUSART 2022, held as part of Evo* 2022, in April 2022, co-located with the Evo* 2022 events, EvoCOP, EvoApplications, and EuroGP. The 20 full papers and 6 short papers presented in this book were carefully reviewed and selected from 66 submissions. They cover a wide range of topics and application areas, including generative approaches to music and visual art, deep learning, and architecture.

The Marktoberdorf Summer School 1995 'Logic of Computation' was the 16th in a series of Advanced Study Institutes under the sponsorship of the NATO Scientific Affairs Division held in Marktoberdorf. Its scientific goal was to survey recent progress on the impact of logical methods in software development. The courses dealt with many different aspects of this interplay, where major progress has been made. Of particular importance were the following. ¿ The proofs-as-programs paradigm, which makes it possible to extract verified programs directly from proofs. Here a higher order logic or type theoretic setup of the underlying language has developed into a standard. ¿ Extensions of logic programming, e.g. by allowing more general formulas and/or higher order languages. ¿ Proof theoretic methods, which provide tools to deal with questions of feasibility of computations and also to develop a general mathematical understanding of complexity questions. ¿ Rewrite systems and unification, again in a higher order context. Closely related is the now well-established Grabner basis theory, which recently has found interesting applications. ¿ Category theoretic and more generally algebraic methods and techniques to analyze the semantics of programming languages. All these issues were covered by a team of leading researchers. Their courses were grouped under the following headings.

Concurrent design, or co-design of hardware and software is extremely important for meeting design goals, such as high performance, that are the key to commercial competitiveness. Hardware/Software Co-Design covers many aspects of the subject, including methods and examples for designing: (1) general purpose and embedded computing systems based on instruction set processors; (2) telecommunication systems using general purpose digital signal processors as well as application specific instruction set processors; (3) embedded control systems and applications to automotive electronics. The book also surveys the areas of emulation and prototyping systems with field programmable gate array technologies, hardware/software synthesis and verification, and industrial design trends. Most contributions emphasize the design methodology, the requirements and state of the art of computer aided co-design tools, together with current design examples.

Network Function Virtualization (NFV) has recently attracted considerable attention from both research and industrial communities. Numerous papers have been published regarding solving the resource- allocation problems in NFV, from various perspectives, considering different constraints, and adopting a range of techniques. However, it is difficult to get a clear impression of how to understand and classify different kinds of resource allocation problems in NFV and how to design solutions to solve these problems efficiently.This book addresses these concerns by offering a comprehensive overview and explanation of different resource allocation problems in NFV and presenting efficient solutions to solve them. It covers resource allocation problems in NFV, including an introduction to NFV and QoS parameters modelling as well as related problem definition, formulation and the respective state-of-the-art algorithms.This book allows readers to gain a comprehensive understanding of and deep insights into the resource allocation problems in NFV. It does so by exploring (1) the working principle and architecture of NFV, (2) how to model the Quality of Service (QoS) parameters in NFV services, (3) definition, formulation and analysis of different kinds of resource allocation problems in various NFV scenarios, (4) solutions for solving the resource allocation problem in NFV, and (5) possible future work in the respective area.

This book constitutes the refereed proceedings of the 12th International Symposium, ISICA 2021, held in Guangzhou, China, during November 19-21, 2021.  The 48 full papers included in this book were carefully reviewed and selected from 99 submissions. They were organized in topical sections as follows: new frontier of multi-objective evolutionary algorithms; intelligent multi-media; data modeling and application of artificial intelligence; exploration of novel intelligent optimization algorithm; and intelligent application of industrial production.

This book presents thoughts and pathways to build revolutionary machine learning models with the new paradigm of machine learning to adapt behaviorism. It focuses on two aspects - one focuses on architecting a choice process to lead users on the certain choice path while the second focuses on developing machine learning models based on choice paradigm. This book is divided in three parts where part one deals with human choice and choice architecting models with stories of choice architects. Second part closely studies human choosing models and deliberates on developing machine learning models based on the human choice paradigm. Third part takes you further to look at machine learning based choice architecture. The proposed pioneering choice-based paradigm for machine learning presented in the book will help readers to develop products - help readers to solve problems in a more humanish way and to negotiate with uncertainty in a more graceful but in an objective way. It will help to create unprecedented value for business and society. Further, it will unveil a new paradigm for modern intelligent businesses to embark on the new journey; the journey of transition from shackled feature rich and choice poor systems to feature flexible and choice rich natural behaviors.

The 5G technology has been commercialized worldwide and is expected to provide superior performance with enhanced mobile broadband, ultra-low latency transmission, and massive IoT connections. Meanwhile, the edge computing paradigm gets popular to provide distributed computing and storage resources in proximity to the users. As edge services and applications prosper, 5G and edge computing will be tightly coupled and continuously promote each other forward.Embracing this trend, however, mobile users, infrastructure providers, and service providers are all faced with the energy dilemma. On the user side, battery-powered mobile devices are much constrained by battery life, whereas mobile platforms and apps nowadays are usually power-hungry. At the infrastructure and service provider side, the energy cost of edge facilities accounts for a large proportion of operating expenses and has become a huge burden.This book provides a collection of most recent attempts to tackle the energy issues in mobile edge computing from new and promising perspectives. For example, the book investigates the pervasive low-battery anxiety among modern mobile users and quantifies the anxiety degree and likely behavior concerning the battery status. Based on the quantified model, a low-power video streaming solution is developed accordingly to save mobile devices' energy and alleviate users' low-battery anxiety. In addition to energy management for mobile users, the book also looks into potential opportunities to energy cost saving and carbon emission reduction at edge facilities, particularly the 5G base stations and geo-distributed edge datacenters.

Machine learning heavily relies on optimization algorithms to solve its learning models. Constrained problems constitute a major type of optimization problem, and the alternating direction method of multipliers (ADMM) is a commonly used algorithm to solve constrained problems, especially linearly constrained ones. Written by experts in machine learning and optimization, this is the first book providing a state-of-the-art review on ADMM under various scenarios, including deterministic and convex optimization, nonconvex optimization, stochastic optimization, and distributed optimization. Offering a rich blend of ideas, theories and proofs, the book is up-to-date and self-contained. It is an excellent reference book for users who are seeking a relatively universal algorithm for constrained problems. Graduate students or researchers can read it to grasp the frontiers of ADMM in machine learning in a short period of time.

Erzeugende Funktionen sind ein wichtiges Werkzeug in der Kombinatorik und der Theoretischen Informatik. Das Buch zeigt an vielen Beispielen, wie man dieses Werkzeug verwendet, mit dem eine Folge reeller Zahlen durch eine einzige Funktion reprasentiert wird. Es wird eine Einfuhrung in die Technik der Gewinnung und der Manipulation erzeugender Funktionen gegeben; wichtige Folgen und ihre korrespondierenden Funktionen werden behandelt.

Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nachsten Nachbarn? Wie findet man schnell alle Stadte in einem rechteckigen Kartenausschnitt? Wie misst man die Ahnlichkeit von zwei Kurven?Mit solchen Fragen beschaftigt sich die Algorithmische Geometrie. Dieses Buch gibt eine Einfuhrung in algorithmische Techniken wie Sweep, Divide-and-Conquer, randomisierte inkrementelle Konstruktion, Dynamisierung, amortisierte Kostenanalyse und kompetitive Analyse. Es stellt wichtige geometrische Strukturen, wie konvexe Hulle, Voronoi-Diagramm und Delaunay-Triangulation sowie effiziente Datenstrukturen vor.Diese dritte Auflage wurde grundlich uberarbeitet und erweitert. Sie bietet Dozent*innen die Moglichkeit, fur Vorlesungen und Seminare eine individuelle Stoffauswahl zu treffen, auch zu weiterfuhrenden Themen wie zum Beispiel ausgewogene hoherdimensionale Suchbaume, schnelle Triangulierung, Vapnik-Chervonenkis Dimension, Ahnlichkeitsberechnung von Kurven, Bewegungsplanung und Inzidenzen geometrischer Objekte.

This practical new book offers the distributed-computing fundamental knowledge for individuals to connect with one another in a more secure and efficient way than with traditional blockchains. These new forms of secure, scalable blockchains promise to replace centralized institutions to connect individuals without the risks of user manipulations or data extortions.The techniques taught herein consist of enhancing blockchain security and making blockchain scalable by relying on the observation that no blockchain can exist without solving the consensus problem. First, the state-of-the-art of consensus protocols are analyzed, hence motivating the need for a new family of consensus protocols offering strong (deterministic) guarantees. Second, a didactic series of classic blockchain vulnerabilities is presented to illustrate the importance of novel designs better suited for the adversarial environment of open networks.These cutting-edge solutions are illustrated through the Redbelly blockchain design, which solves a different problem from the classic Byzantine consensus problem of 1982 and which delivers-in the modern blockchain context-high performance at large scale.Topics and features:Covers the combination of security and distributed computing to devise the new generation of blockchainsShows how blockchain has shed new light on decades of research in distributed systemsProvides instruction on the security needed by the industry to use blockchains in productionExplains didactically the necessary ingredients to make blockchain efficient at large scaleHelps fill the gap of knowledge in the highly demanded blockchain sectorThis unique volume contains the building blocks to design secure and scalable blockchains. As such, it is dedicated to developers, application designers, and computer scientists and requires only a minimal undergraduate level in mathematics and computer science.Vincent Gramoli is an Australian Research Council Future Fellow at the University of Sydney and the Chief Technology Officer of Redbelly Network. He teaches the Blockchain Scalability course on Coursera.

This book constitutes selected papers from the refereed proceedings of the 14th International Workshop on Rewriting Logic and Its Applications, WRLA 2022, held in Munich, Germany, in April 2022.The 9 full papers included in this book were carefully reviewed and selected from 13 submissions. They focus on topics in rewriting logic and its applications. The book also contains 2 invited papers, 2 invited tutorials and an experience report.

Knowledge of automata theory and formal languages is crucial for understanding human-computer interaction, as well as for understanding the various processes that take place when manipulating knowledge if that knowledge is, indeed, expressed as sentences written in a suitably formalized language. In particular, it is at the basis of the theory of parsing, which plays an important role in language translation, compiler construction, and knowledge manipulation in general.Presenting basic notions and fundamental results, this concise textbook is structured on the basis of a correspondence that exists between classes of automata and classes of languages. That correspondence is established by the fact that the recognition and the manipulation of sentences in a given class of languages can be done by an automaton in the corresponding class of automata. Four central chapters center on: finite automata and regular languages; pushdown automata and context-free languages; linear bounded automata and context-sensitive languages; and Turing machines and type 0 languages.  The book also examines decidable and undecidable problems with emphasis on the case for context-free languages.Topics and features:Provides theorems, examples, and exercises to clarify automata-languages correspondencesPresents some fundamental techniques for parsing both regular and context-free languagesClassifies subclasses of decidable problems, avoiding focus on the theory of complexityExamines finite-automata minimalization and characterization of their behavior using regular expressionsIllustrates how to derive grammars of context-free languages in Chomsky and Greibach normal formsOffers supplementary material on counter machines, stack automata, and abstract language familiesThis highly useful, varied text/reference is suitable for undergraduate and graduate courses on automata theory and formal languages, and assumes no prior exposure to these topics nor any training in mathematics or logic.Alberto Pettorossi is professor of theoretical computer science at the University of Rome Tor Vergata, Rome, Italy.

This book constitutes the refereed post-conference proceedings of the 17th International Conference on Advances in Computer Games, ACG 2021, which was held as a virtual event during November 23-25, 2021. The 22 full papers included in this book were carefully reviewed and selected from 34 submissions. They were organized in topical sections as follows: learning in games; search in games; solving games; chess patterns; player modelling; and game systems.

Reverse mathematics studies the complexity of proving mathematical theorems and solving mathematical problems. Typical questions include: Can we prove this result without first proving that one? Can a computer solve this problem? A highly active part of mathematical logic and computability theory, the subject offers beautiful results as well as significant foundational insights.This text provides a modern treatment of reverse mathematics that combines computability theoretic reductions and proofs in formal arithmetic to measure the complexity of theorems and problems from all areas of mathematics. It includes detailed introductions to techniques from computable mathematics, Weihrauch style analysis, and other parts of computability that have become integral to research in the field. Topics and features:Provides a complete introduction to reverse mathematics, including necessary background from computability theory, second order arithmetic, forcing, induction, and model constructionOffers a comprehensive treatment of the reverse mathematics of combinatorics, including Ramsey's theorem, Hindman's theorem, and many other resultsProvides central results and methods from the past two decades, appearing in book form for the first time and including preservation techniques and applications of probabilistic argumentsIncludes a large number of exercises of varying levels of difficulty, supplementing each chapterThe text will be accessible to students with a standard first year course in mathematical logic. It will also be a useful reference for researchers in reverse mathematics, computability theory, proof theory, and related areas.Damir D. Dzhafarov is an Associate Professor of Mathematics at the University of Connecticut, CT, USA. Carl Mummert is a Professor of Computer and Information Technology at Marshall University, WV, USA.

This book constitutes the refereed proceedings of the 12th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2022, held in Helsinki, Finland, in June 2022. The 13 full papers presented were carefully reviewed and selected from 21 submissions. The papers address various topics such as  information and knowledge systems, including submissions that apply ideas, theories or methods from specific disciplines to information andknowledge systems. Examples of such disciplines are discrete mathematics, logic and algebra, model theory, databases, information theory, complexity theory, algorithmics and computation, statistics and optimization.

This book constitutes the thoroughly refereed post-conference proceedings of the 16th International Workshop on Coalgebraic Methods in Computer Science, CMCS 2022, colocated with ETAPS 2022, held in Munich, Germany, in April 2022. The 9 revised full papers were carefully reviewed and selected from 12 submissions. The papers cover a wide range of topics in the theory, logics, and applications of coalgebras.

Computation theory is a discipline that uses mathematical concepts and tools to expose the nature of "e;computation"e; and to explain a broad range of computational phenomena: Why is it harder to perform some computations than others?  Are the differences in difficulty that we observe inherent, or are they artifacts of the way we try to perform the computations?  How does one reason about such questions?This unique textbook strives to endow students with conceptual and manipulative tools necessary to make computation theory part of their professional lives. The work achieves this goal by means of three stratagems that set its approach apart from most other texts on the subject.For starters, it develops the necessary mathematical concepts and tools from the concepts' simplest instances, thereby helping students gain operational control over the required mathematics. Secondly, it organizes development of theory around four "e;pillars,"e; enabling students to see computational topics that have the same intellectual origins in physical proximity to one another. Finally, the text illustrates the "e;big ideas"e; that computation theory is built upon with applications of these ideas within "e;practical"e; domains in mathematics, computer science, computer engineering, and even further afield.Suitable for advanced undergraduate students and beginning graduates, this textbook augments the "e;classical"e; models that traditionally support courses on computation theory with novel models inspired by "e;real, modern"e; computational topics,such as  crowd-sourced computing, mobile computing, robotic path planning, and volunteer computing.Arnold L. Rosenberg is Distinguished Univ. Professor Emeritus at University of Massachusetts, Amherst, USA. Lenwood S. Heath is Professor at Virgina Tech, Blacksburg, USA.            

This book constitutes the refereed conference proceedings of the 29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022, held in Paderborn, Germany, in June 2022. The 16 full papers presented in this book were carefully reviewed and selected from 30 submissions. SIROCCO is devoted to the study of the interplay between structural knowledge, communication, and computing in decentralized systems of multiple communicating entities. Special emphasis is given to innovative approaches leading to better understanding of the relationship between computing and communication.

Lattice rules are a powerful and popular form of quasi-Monte Carlo rules based on multidimensional integration lattices. This book provides a comprehensive treatment of the subject with detailed explanations of the basic concepts and the current methods used in research. This comprises, for example, error analysis in reproducing kernel Hilbert spaces, fast component-by-component constructions, the curse of dimensionality and tractability, weighted integration and approximation problems, and applications of lattice rules.

This book constitutes the refereed proceedings of the 15th International Conference on Graph Transformation, ICGT 2022, which took place Nantes, France in July 2022.The 10 full papers and 1 tool paper presented in this book were carefully reviewed and selected from 19 submissions. The conference focuses on describing new unpublished contributions in the theory and applications of graph transformation as well as tool presentation papers that demonstrate main new features and functionalities of graph-based tools.

This book constitutes the refereed proceedings of the Third International Conference on Next Generation Arithmetic, CoNGA 2022, which was held in Singapore, during March 1-3, 2022.  The 8 full papers included in this book were carefully reviewed and selected from 12 submissions. They deal with emerging technologies for computer arithmetic focusing on the demands of both AI and high-performance computing. 

This monograph provides a comprehensive and rigorous exposition of the basic concepts and most important modern research results concerning blockchain and its applications. The book includes the required cryptographic fundamentals underpinning the blockchain technology, since understanding of the concepts of cryptography involved in the design of blockchain is necessary for mastering the security guarantees furnished by blockchain. It also contains an introduction to cryptographic primitives, and separate chapters on bitcoin, ethereum and smart contracts, public blockchain, private blockchain, cryptocurrencies, and blockchain applications.This volume is of great interest to active researchers who are keen to develop novel applications of blockchain in the field of their investigatio. Further, it is also beneficial for  industry practitioners as well as undergraduate students in computing and information technology.

This book constitutes the refereed proceedings of the 14th International Conference on Reversible Computation, RC 2022, which was held in Urbino, Italy, during July 5-6, 2021.The 10 full papers and 6 short papers included in this book were carefully reviewed and selected from 20 submissions.  They were organized in topical sections named: Reversible and Quantum Circuits;  Applications of quantum Computing; Foundations and Applications.

This book constitutes the refereed proceedings of the 42nd IFIP WG 6.1 International Conference on Formal Techniques for Distributed Objects, Components, and Systems, FORTE 2022, held in Lucca, Italy, in June 2022, as part of the 17th International Federated Conference on Distributed Computing Techniques, DisCoTec 2022.The 12 regular papers presented were carefully reviewed and selected from 28 submissions. They cover topics such as: software quality, reliability, availability, and safety; security, privacy, and trust in distributed and/or communicating systems; service-oriented, ubiquitous, and cloud computing systems; component-and model-based design; object technology, modularity, and software adaptation; self-stabilisation and self-healing/organising; and verification, validation, formal analysis, and testing of the above.

This book constitutes the proceedings of the 19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2022, which was held in Los Angeles, CA, USA, in June 2022.The 28 regular papers presented were carefully reviewed and selected from a total of 60 submissions. The conference program included a Master Class on the topic "e;Bridging the Gap between Machine Learning and Optimization"e;.