Mathematical theory of computation Books

Book SynopsisThe two-volume set LNCS 14461 and LNCS 14462 constitutes the refereed proceedings of the 17th International Conference on Combinatorial Optimization and Applications, COCOA 2023, held in Hawaii, HI, USA, during December 15–17, 2023. The 73 full papers included in the proceedings were carefully reviewed and selected from 117 submissions. They were organized in topical sections as follows: Part I: Optimization in graphs; scheduling; set-related optimization; applied optimization and algorithm; Graph planer and others;Part II: Modeling and algorithms; complexity and approximation; combinatorics and computing; optimization and algorithms; extreme graph and others; machine learning, blockchain and others.Table of ContentsModeling and Algorithms.- ​Differentiable Discrete Optimization using Dataless Neural Networks.- When Advertising meets Assortment Planning: Joint Advertising and Assortment Optimization under Multinomial Logit Model.- Twin-treewidth: A single-exponential logic-based approach.- Highway Preferential Attachment Models for Geographic Routing.- Complexity and Approximation.- Restricted Holant Dichotomy on Domains 3 and 4.- Earliest Deadline First is a $2$-approximation for DARP with Time Windows.- Improved approximation for broadcasting in k-Path Graphs.- The fine-grained complexity of approximately counting proper connected colorings (extended abstract).- Combinatorics and Computing.- Strong edge coloring of subquartic graphs.- Two multicolor Ramsey numbers involving bipartite graphs.- Mechanism Design for Time-Varying Value Tasks in High-Load Edge Computing Markets.- Computing random r-orthogonal Latin squares.- Optimization and Algorithms.- A Two-stage Seeds Algorithm for Competitive Influence Maximization considering User Demand.- Practical Attribute-Based Multi-Keyword Search Scheme with Sensitive Information Hiding for Cloud Storage Systems.- Testing Higher-order Clusterability on graphs.- The $2$-mixed-center color spanning problem.- A Dynamic Parameter Adaptive Path Planning Algorithm.- On the Mating Between a Polygonal Curve and a Convex Polygon.- A Faster Parameterized Algorithm for Bipartite 1-Sided Vertex Explosion.- Multi-Winner Approval Voting with Grouped Voters.- EFX Allocation to Chores Over Small Graph.- Extreme Graph and Others.- Zero-visibility Cops and Robber game on Cage graph.- Online Facility Assignment for General Layout of Servers on a Line.- Guarding Precise and Imprecise Polyhedral Terrains with Segments.- The Bag-Based Search: A meta-algorithm to construct tractable logical circuits for graphs based on tree decomposition.- On Problems Related to Absent Subsequences.- Some Combinatorial Algorithms on the Dominating Number of Anti-Rank k Hypergraphs.- Parameterized and exact-exponential algorithms for the read-once integer refutation problem in UTVPI constraints.- Critical $(P_5,dart)$-Free Graphs.- Graph Clustering through Users' Properties and Social Influence.- Machine Learning, Blockchain and Others.- Incorporating Neural Point Process-based Temporal Feature for Rumor Detection.- Improving Contraction Hierarchies by Combining with All-Pairs Shortest Paths Problem Algorithms.- Information Theory of Blockchain Systems.- Machine Learning with Low Resource Data from Psychiatric Clinics.- Single Image Dehazing Based on Dynamic Convolution and Transformer.- Reinforcement Learning for Combating Cyberbullying in Online Social Networks.

Read more less

Book SynopsisThis book constitutes the proceedings of the 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, held in Cochem, Germany, in February 2024. The 33 full papers presented in this book were carefully reviewed and selected from 81 submissions. The book also contains one invited talk in full paper length. They focus on original research and challenges in foundations of computer science including algorithms, AI-based methods, computational complexity, and formal models.Table of ContentsThe Information Extraction Framework of Document Spanners - A Very Informal Survey.- Generalized Distance Polymatrix Games.- Relaxed agreement forests.- On the Computational Complexity of Generalized Common Shape Puzzles.- Fractional Bamboo Trimming and Distributed Windows Scheduling.- New support size bounds and proximity bounds for integer linear programming.- On the Parameterized Complexity of Minus Domination.- Exact and Parameterized Algorithms for Choosability.- Parameterized Algorithms for Covering by Arithmetic Progressions.- Row-column combination of Dyck words.- Group Testing in Arbitrary Hypergraphs and Related Combinatorial Structures.- On the parameterized complexity of the Perfect Phylogeny problem.- Data reduction for directed feedback vertex set on graphs without long induced cycles.- Visualization of Bipartite Graphs in Limited Window Size.- Outerplanar and Forest Storyplans.- The Complexity of Cluster Vertex Splitting and Company.- Morphing Graph Drawings in the Presence of Point Obstacles.- Word-Representable Graphs from a Word’s Perspective.- Removable Online Knapsack with Bounded Size Items.- The Complexity of Online Graph Games.- Faster Winner Determination Algorithms for (Colored) Arc Kayles.- Automata Classes Accepting Languages Whose Commutative Closure is Regular.- Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching.- Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages.- Apportionment with Thresholds: Strategic Campaigns Are Easy in the Top-Choice But Hard in the Second-Chance Mode.- Local Certification of Majority Dynamics.- Complexity of Spherical Equations in Finite Groups.- Positive Characteristic Sets for Relational Pattern Languages.- Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs.- The Weighted HOM-Problem over Fields.- Combinatorics of block-parallel automata networks.- On the piecewise complexity of words and periodic words.- Distance Labeling for Families of Cycles.- On the induced problem for fixed-template CSPs.

Read more less

Book Synopsis

Read more less

Book Synopsis

Read more less

Book Synopsis

Read more less

Book SynopsisVerification and testing: Enabling behaviour tree verification via a translation to BIP.- Verified fault handling for modern board management controllers.- Testing compositionality. Formal models: Correct pattern-based development through refinements and weakest preconditions calculus.- Coq formalization of orientation representation: matrix, Euler angles, axis-angle and quaternion.- Reactive graphs in action. Security and blockchain: Extracting formal smart-contract specifications from natural language with LLMs.- How do asynchronous communication models impact the composability of information flow security?

Read more less

Book Synopsis

Read more less

Book SynopsisAutomata, Languages, and Learning.- Well Behaved (Co)algebraic Semantics of Regular Expressions in Dafny.- Jump Complexity of Deterministic Finite Automata with Translucent Letters.- Learning Closed Signal Flow Graphs.- Dual Adjunction Between $Omega$ Automata and Wilke Algebra Quotients.- On Concurrent Program Algebra and Demonic Automata.- Bisimulations and Logics for Higher Dimensional Automata.- Algorithms and Complexity.- Maximizing Weighted Dominance in the Plane.- Generalized Parikh Matrices For Tracking Subsequence Occurrences.- Card Based Protocols with Single Card Encoding.- Graphs and Games.- Winning Strategy Templates for Stochastic Parity Games towards Permissive and Resilient Control.- Disconnection Rules are Complete for Chemical Reactions.- Verification with Common Knowledge of Rationality for Graph Games.- Process Calculi.- Reversibility in Process Calculi with Nondeterminism and Probabilities.- A T

Read more less

Book SynopsisMathematical Programming.- Hybrid Method for Linear ProgrammingHybrid Method for Linear Programming.- An Equilibrium Dynamic Traffic Assignment Model with Linear Programming Formulation.- Singular optimization problems and p-factor approach for their analysis.- On the Application of Composite Penalty Functions Obtained by Gluing of External Penalties with Barrier Ones in Linear Programming.- Nesterov's Method of Dichotomy via Order Oracle: The Problem of Optimizing a Two-Variable Function on a Square.- Piecewise Linear Approximations in the Balanced Identification of Models with Differential Equations.- Extragradient Sliding for Composite Non-Monotone Variational Inequalities.- Global Optimization.- A Three-Stage Numerical Approach to the Study of Extra-Large Atomic-Molecular Clusters.- Comparative Efficiency of Machine Learning Models for Enhancing Algorithms in Solving Multiextremal Multicriteria Problems.- Automated Multi-Criteria Optimization of Parallel Robots.- Optimal Selection of Feedback Coefficients in the Problem of Stabilizing a Chain of Three Integrators.- Optimal Control.- On Some Sufficient Condition for Quadraticity of a Degenerate Optimization Problem with Inequality Constraints.- A Maximum Principle for a State-Constrained Optimal Control Problem Whose Data Is Measurable in the Time-variable.- Game Theory and Mathematical Economics.- Nash and Stackelberg Equilibria in Differential Games with Functionals in the Form of the Minimum Antagonistic and Partial Criteria.- A Model of Investment Policy of Firms.- Optimization in Economics and Finance.- The Ramsey's Conjecture for the Model with Non-Liquid Capital.- A Nonlinear Input-Output-Based Model for Medium-Term Macroeconomic Risks Analysis for a Restructuring Economy with Limited Capacities.- Optimal Timing of Investment and Debt Payment in Production Expansion with the Use of External Financing.- Identification of an Endogenous Production Function for the U.S. Economy.- An Ecological and Economic Model of Carbon Neutrality.- Applications.- Optimal Control Problem in Treatment Strategies for Breast Tumors.- The Use of Both Temperature Field and Heat Fluxes to Identify the Thermal Conductivity and Volumetric Heat Capacity.- Maximising the Discounted Accumulated Income in the Model with Two Gas Fields.- Modeling and Optimization of Controlled Conveyor Systems Using Intelligent Controllers.

Read more less

Book SynopsisIntroduction.- Multistability and Intrinsic Antifragility.- Inherited Antifragility.- Induced Antifragility.- Conclusions and Open Research Questions.

Read more less

Book Synopsis.- An Invited Talk about B..- Neurosymbolic Learning Systems: Artificial Intelligence and Formal Methods..- Mathematical Proofs and Moving Trains: The Double Life of Atelier B..- Behavioural Theory of Reflective Parallel Algorithms..- Using Symbolic Model Execution to Detect Vulnerabilities of Smart Contracts..- Safely Encoding B Proof Obligations in SMT-LIB..- On Writing Alloy Models: Metrics and a new Dataset..- On Quantitative Solution Iteration in QAlloy..- Proof Semantics of Railway Interlocking..- Translating Event-B models and development proofs to TLA..- The Proved Construction of a Protocol with an Example..- Insider Threat Simulation Through Ant Colonies and ProB..- Developing safe exception recovery mechanisms for CHERI capability hardware using UML-B formal analysis..- Case Study: Safety Controller for Autonomous Driving on Highways..- Safety enforcement for autonomous driving on a simulated highway using Asmeta models@run.time..- Enhancing Decision-making Safety in Autonomous Driving Through Online Model Checking..- Polychronous RSS in a Process-Algebraic Framework - A Case Study in Autonomous Driving Safety..- On The Road Again (Safely): Modelling and Analysis of Autonomous Driving with extsc{Stark}..- Modelling and Verification of Highway Car Control with KeYmaera X..- State-Based Modelling with a Concept DSL..- Towards an End-to-End Tool Chain for Traceable and Verifiable Railway Signalling Specifications..- A reasoning and explicit algebraic theory for BBSL in Event-B: EB4BBSL framework..- Model-Based Testing of Non-Deterministic Systems..- Weakening Goals in Logical Specifications..- Formal modelling and reasoning on Assurance Cases expressed with GSN in Event-B.

Read more less

Book SynopsisChapter 1. Introduction.- Chapter 2. Illustrating UMAP on some simple data sets.- Chapter 3. Metrics and Riemannian manifolds.- Chapter 4.  Merging fuzzy simplicial sets and metric spaces: A category theoretical approach.- Chapter 5. UMAP.- Chapter 6.  IsUMap: An alternative to the UMAP embedding.

Read more less

Book SynopsisThe Białowieża workshops on Geometric Methods in Physics are among the most important meetings in the field. Every year some 80 to 100 participants from both mathematics and physics join to discuss new developments and to interchange ideas. This volume contains contributions by selected speakers at the XXX meeting in 2011 as well as additional review articles and shows that the workshop remains at the cutting edge of ongoing research. The 2011 workshop focussed on the works of the late Felix A. Berezin (1931–1980) on the occasion of his 80th anniversary as well as on Bogdan Mielnik and Stanisław Lech Woronowicz on their 75th and 70th birthday, respectively. The groundbreaking work of Berezin is discussed from today’s perspective by presenting an overview of his ideas and their impact on further developments. He was, among other fields, active in representation theory, general concepts of quantization and coherent states, supersymmetry and supermanifolds. Another focus lies on the accomplishments of Bogdan Mielnik and Stanisław Lech Woronowicz. Mielnik’s geometric approach to the description of quantum mixed states, the method of quantum state manipulation and their important implications for quantum computing and quantum entanglement are discussed as well as the intricacies of the quantum time operator. Woronowicz’ fruitful notion of a compact quantum group and related topics are also addressed.

Read more less

Book SynopsisAdapted from a modular undergraduate course on computational mathematics, Concise Computer Mathematics delivers an easily accessible, self-contained introduction to the basic notions of mathematics necessary for a computer science degree. The text reflects the need to quickly introduce students from a variety of educational backgrounds to a number of essential mathematical concepts. The material is divided into four units: discrete mathematics (sets, relations, functions), logic (Boolean types, truth tables, proofs), linear algebra (vectors, matrices and graphics), and special topics (graph theory, number theory, basic elements of calculus). The chapters contain a brief theoretical presentation of the topic, followed by a selection of problems (which are direct applications of the theory) and additional supplementary problems (which may require a bit more work). Each chapter ends with answers or worked solutions for all of the problems.Trade ReviewFrom the reviews:“The book is ideally suited as an adjunct to a course in computer mathematics or as a refresher for someone with some background in computer mathematics. … The book fulfills its purpose of providing a distilled treatment of the mathematics most commonly used in computer science. It is of most value to computer science students who need a place to find a succinct treatment of the topics covered.” (Marlin Thomas, Computing Reviews, April, 2014)“Each of the chapters opens with a short summary followed by a set of essential problems and then a set of supplementary problems. … it would be very useful for someone that needs a quick and effective review that includes problems.” (Charles Ashbacher, MAA Reviews, January, 2014)Table of ContentsSets and NumbersRelations and DatabasesFunctionsBoolean Algebra, Logic and QuantifiersNormal Forms, Proof and ArgumentVectors and Complex NumbersMatrices and ApplicationsMatrix Transformations for Computer GraphicsElements of Graph TheoryElements of Number Theory and CryptographyElements of CalculusElementary Numerical Methods

Read more less

Book SynopsisThis text aims to provide graduate students with a self-contained introduction to topics that are at the forefront of modern algebra, namely, coalgebras, bialgebras and Hopf algebras. The last chapter (Chapter 4) discusses several applications of Hopf algebras, some of which are further developed in the author’s 2011 publication, An Introduction to Hopf Algebras. The book may be used as the main text or as a supplementary text for a graduate algebra course. Prerequisites for this text include standard material on groups, rings, modules, algebraic extension fields, finite fields and linearly recursive sequences.The book consists of four chapters. Chapter 1 introduces algebras and coalgebras over a field K; Chapter 2 treats bialgebras; Chapter 3 discusses Hopf algebras and Chapter 4 consists of three applications of Hopf algebras. Each chapter begins with a short overview and ends with a collection of exercises which are designed to review and reinforce the material. Exercises range from straightforward applications of the theory to problems that are devised to challenge the reader. Questions for further study are provided after selected exercises. Most proofs are given in detail, though a few proofs are omitted since they are beyond the scope of this book.Trade Review“The goal of the book under review is to introduce graduate students to some basic results on coalgebras, bialgebras, Hopf algebras, and their applications. The book may be used as the main text or as a supplementary text for a graduate course. … This book should be very useful as a first introduction for someone who wants to learn about Hopf algebras and their applications.” (Jörg Feldvoss, zbMATH 1341.16034, 2016)Table of ContentsPreface.- Notation.- 1. Algebras and Coalgebras.- 2. Bialgebras.- 3. Hopf Algebras.- 4. Applications of Hopf Algebras.- Bibliography.

Read more less

Book SynopsisFor over two decades, this comprehensive manual has been the standard introduction and complete reference for writing articles and books containing mathematical formulas. If the reader requires a streamlined approach to learning LaTeX for composing everyday documents, Grätzer’s © 2014 Practical LaTeX may also be a good choice.In this carefully revised fifth edition, the Short Course has been brought up to date and reflects a modern and practical approach to LaTeX usage. New chapters have been added on illustrations and how to use LaTeX on an iPad.Key features: An example-based, visual approach and a gentle introduction with the Short Course A detailed exposition of multiline math formulas with a Visual Guide A unified approach to TeX, LaTeX, and the AMS enhancements A quick introduction to creating presentations with formulas From earlier reviews:Grätzer’s book is a solution. —European Mathematical Society NewsletterThere are several LaTeX guides, but this one wins hands down for the elegance of its approach and breadth of coverage.—Amazon.com, Best of 2000, Editor’s choiceA novice reader will be able to learn the most essential features of LaTeX sufficient to begin typesetting papers within a few hours of time… An experienced TeX user, on the other hand, will find a systematic and detailed discussion of LaTeX features.—Report on Mathematical PhysicsA very helpful and useful tool for all scientists and engineers. —Review of Astronomical ToolsTrade Review“George Grätzer’s books have been nearly as successful and enduring as the amazing software they are devoted to. This well known manual provides a reliable and thorough introduction and comprehensive reference for everyone who does not want to depend on various resources available online.” (C. Baxa, Monatshefte für Mathematik, Vol. 192 (2), 2020)Table of ContentsForeword.-Preface to the fifth Edition.-Introduction.-I. Mission Impossible.-1. Short course.-2. And a few more things....-II. Text and Math.-3. Typing text.-4. Text environments.-5. Typing math.-6. More math.-7. Multiline math displays.-III. Document Structure.-8. Documents.-9. The AMS article document class.-10. Legacy documents.-IV. PDF Documents.-11. The PDF file format.-12. Presentations.-13. Illustrations.-V. Customization.-14. Commands and environments.-VI. Long Documents.-15. BibTeX.-16. MakeIndex.-17. Books in LaTeX.-A. Math symbol tables.-B. Text symbol tables.-C. Some background.-D. LaTeX and the internet.-E. Postscript fonts.-F. LaTeX localized.-G. LaTeX on the iPad.-H. Final thoughts.-Bibliography.-Index.

Read more less

Book SynopsisPresenting a comprehensive resource for the mastery of network analysis in R, the goal of Network Analysis with R is to introduce modern network analysis techniques in R to social, physical, and health scientists. The mathematical foundations of network analysis are emphasized in an accessible way and readers are guided through the basic steps of network studies: network conceptualization, data collection and management, network description, visualization, and building and testing statistical models of networks. As with all of the books in the Use R! series, each chapter contains extensive R code and detailed visualizations of datasets. Appendices will describe the R network packages and the datasets used in the book. An R package developed specifically for the book, available to readers on GitHub, contains relevant code and real-world network datasets as well.Table of ContentsIntroducing Network Analysis in R.- The Network Analysis "5 Number Summary".- Network Data Management in R.- Basic Network Plotting and Layout.- Effective Network Graphic Design.- Advanced Network Graphics.- Actor Prominence.- Subgroups.- Affiliation Networks.- Random Network Models.- Statistical Network Models.- Dynamic Network Models.- Simulations.

Read more less

Book SynopsisThis must-read text/reference provides a practical guide to processes involved in the development and application of dynamic simulation models, covering a wide range of issues relating to testing, verification and validation. Illustrative example problems in continuous system simulation are presented throughout the book, supported by extended case studies from a number of interdisciplinary applications. Topics and features: provides an emphasis on practical issues of model quality and validation, along with questions concerning the management of simulation models, the use of model libraries, and generic models; contains numerous step-by-step examples; presents detailed case studies, often with accompanying datasets; includes discussion of hybrid models, which involve a combination of continuous system and discrete-event descriptions; examines experimental modeling approaches that involve system identification and parameter estimation; offers supplementary material at an associated website.Table of ContentsAn Introduction to Simulation Models and the Modelling ProcessConcepts of Simulation Model Testing, Verification and ValidationMeasures of Quality for Model ValidationSensitivity Analysis for Model EvaluationExperimental Data for Model ValidationMethods of Model VerificationMethods for the Invalidation/Validation of Simulation ModelsManagement Issues within Simulation Model Development and TestingCase Study: Development and Testing of a Simulation Model of Two Interconnected VesselsCase Study: Model Validation and Experiment Design for Helicopter Simulation Model Development and ApplicationsCase Study: Compartmental Models of the Gas-Exchange Processes of the Human LungsCase Study: Modelling of Elements of the Neuromuscular Systems Involved in the Regulation of Posture and Control of MovementFurther Discussion

Read more less

Book SynopsisThese lecture notes provide a systematic introduction to matrix models of quantum field theories with non-commutative and fuzzy geometries. The book initially focuses on the matrix formulation of non-commutative and fuzzy spaces, followed by a description of the non-perturbative treatment of the corresponding field theories. As an example, the phase structure of non-commutative phi-four theory is treated in great detail, with a separate chapter on the multitrace approach. The last chapter offers a general introduction to non-commutative gauge theories, while two appendices round out the text. Primarily written as a self-study guide for postgraduate students – with the aim of pedagogically introducing them to key analytical and numerical tools, as well as useful physical models in applications – these lecture notes will also benefit experienced researchers by providing a reference guide to the fundamentals of non-commutative field theory with an emphasis on matrix models and fuzzy geometries.Trade Review“The book collects almost all that has been achieved on the topic within the recent years, including all major results of many authors. As such, it is a nice reference work for graduate students and beginning researchers who want to pursue research in this area. Having all the results and different approaches collected in one place, together with the exhaustive list of references make this a valuable compendium to everyone working on noncommutative models of quantum field theory.” (Andrzej Sitarz, zbMATH 1371.81013, 2017)Table of ContentsPreface.- Introductory Remarks.- The Non-Commutative Moyal-Weyl Spaces Rd.- The Fuzzy Sphere.- Quantum Non-Commutative Phi-Four.- The Multitrace Approach.- Non-Commutative Gauge Theory.- Appendix A - The Landau States.- Appendix B - The Traces TrtAtB and TrtAtBtCtD.- Index.

Read more less

Book SynopsisThis book constitutes the refereed proceedings of the 20th Brazilian Symposium on Formal Methods, SBMF 2017, which took place in Recifel, Brazil, in November/December 2017.The 16 papers presented together with three invited talks were carefully reviewed and selected from 37 submissions. They are organized in the following topical sections: formal methods integration and experience reports; model checking; refinement and verification; and semantics and languages.The chapter 'Rapidly Adjustable Non-Intrusive Online Monitoring for Multi-core Systems' is published open access under a CC BY 4.0 license.Table of ContentsFormal methods integration and experience reports.- Model checking.- Refinement and verification.- Semantics and languages.

Read more less

Book SynopsisThis book celebrates the work of Don Pigozzi on the occasion of his 80th birthday. In addition to articles written by leading specialists and his disciples, it presents Pigozzi’s scientific output and discusses his impact on the development of science. The book both catalogues his works and offers an extensive profile of Pigozzi as a person, sketching the most important events, not only related to his scientific activity, but also from his personal life. It reflects Pigozzi's contribution to the rise and development of areas such as abstract algebraic logic (AAL), universal algebra and computer science, and introduces new scientific results. Some of the papers also present chronologically ordered facts relating to the development of the disciplines he contributed to, especially abstract algebraic logic. The book offers valuable source material for historians of science, especially those interested in history of mathematics and logic.Table of ContentsA Mathematical Life; Pigozzi, Don.- Assertional logics, truth-equational logics, and the hierarchiesof abstract algebraic logic; Albuquerque, Hugo, Font, Josep Maria, Jansana, Ramon, and Moraschini, Tommaso.- Deduction-Detachment Theorem and Gentzen-Style Deductive Systems; Babenyshev, Sergey.- Introducing Boolean Semilattices; Bergman, Clifford.- The Equationally-Defined Commutator in Quasivarieties Generated by Two-Element Algebras; Czelakowski, Janusz.- A short overview of Hidden Logic; Ferreirim, Isabel and Martins, Manuel A.- Absorption and directed J´onsson terms; Kazda, Alexandr, Kozik, Marcin, McKenzie, Ralph and Moore, Matthew.- Relatively congruence modular quasivarieties of modules; Kearnes, Keith A. - The computational complexity of deciding whether a finite algebra generates a minimal variety; McNulty, George F.- Characterization of protoalgebraic k-deductive systems; Palasinska; Katarzyna.- Diagrammatic duality; Romanowska, Anna B. and Smith, Jonathan D.H.- Boolean product representations of algebras via binary polynomials; Salibra, Antonino, Ledda, Antonio, and Paoli, Francesco.- Paraconsistent constructive logic with strong negation as a contraction-free relevant logic; Spinks, Matthew and Veroff, Robert.- Possible classification of finite-dimensional compact Hausdorfftopological algebras; Taylor, Walter.- Categorical Abstract Algebraic Logic: Compatibility Operators and Correspondence Theorems; Voutsadakis; George.

Read more less

Book Synopsis1 Einführung und mathematische Grundlagen.- 1.1 Einführung in die Fragestellung.- 1.2 Allgemeine mathematische Grundbegriffe.- 1.3 Berechenbarkeit.- 1.4 Erzeugungssysteme, Termmengen.- 2 Aussagenlogik.- 2.1 Aussagenlogische Formeln, die Syntax.- 2.2 Interpretationen und Belegungen.- 2.3 Tautologien und logische Äquivalenz.- 2.4 Ausdrucksstärke, Normalformen, Kompaktheitssatz.- 3 Prädikatenlogik.- 3.1 Einleitung.- 3.2 Syntax der Prädikatenlogik.- 3.3 Semantik und logische Grundbegriffe.- 3.4 Formalisierung des logischen Schließens.- 3.5 Normalformen prädikatenlogischer Formeln.- 3.6 Herbrand-Strukturen, Kompaktheit und rekursive Aufzählbarkeit der logischen Konsequenz.- 3.7 Die Unentscheidbarkeit der Prädikatenlogik.- 3.8 Prädikatenlogik mit Gleichheit.- 3.9 Theorien.- 3.10 Ausdrucksstärke der Prädikatenlogik 1. Stufe.- 4 Grundlagen der Logischen Programmierung.- 4.1 Logik-Programme.- 4.2 Unifikation.- 4.3 Berechnungen von Logik-Programmen.- 4.4 Korrektheit und Vollständigkeit des Resolutionsverfahrens.- 5 Modale Aussagenlogik.- 5.1 Einführung in die Modallogik.- 5.2 Entscheidbarkeit.- 5.3 Von der Modallogik zur Temporären Logik.- Übungsaufgaben.- Das Griechische Alphabet.- Verzeichnis der verwendeten Symbole.- Stichwort- und Namensverzeichnis.Table of Contents1 Einführung und mathematische Grundlagen.- 1.1 Einführung in die Fragestellung.- 1.2 Allgemeine mathematische Grundbegriffe.- 1.3 Berechenbarkeit.- 1.4 Erzeugungssysteme, Termmengen.- 2 Aussagenlogik.- 2.1 Aussagenlogische Formeln, die Syntax.- 2.2 Interpretationen und Belegungen.- 2.3 Tautologien und logische Äquivalenz.- 2.4 Ausdrucksstärke, Normalformen, Kompaktheitssatz.- 3 Prädikatenlogik.- 3.1 Einleitung.- 3.2 Syntax der Prädikatenlogik.- 3.3 Semantik und logische Grundbegriffe.- 3.4 Formalisierung des logischen Schließens.- 3.5 Normalformen prädikatenlogischer Formeln.- 3.6 Herbrand-Strukturen, Kompaktheit und rekursive Aufzählbarkeit der logischen Konsequenz.- 3.7 Die Unentscheidbarkeit der Prädikatenlogik.- 3.8 Prädikatenlogik mit Gleichheit.- 3.9 Theorien.- 3.10 Ausdrucksstärke der Prädikatenlogik 1. Stufe.- 4 Grundlagen der Logischen Programmierung.- 4.1 Logik-Programme.- 4.2 Unifikation.- 4.3 Berechnungen von Logik-Programmen.- 4.4 Korrektheit und Vollständigkeit des Resolutionsverfahrens.- 5 Modale Aussagenlogik.- 5.1 Einführung in die Modallogik.- 5.2 Entscheidbarkeit.- 5.3 Von der Modallogik zur Temporären Logik.- Übungsaufgaben.- Das Griechische Alphabet.- Verzeichnis der verwendeten Symbole.- Stichwort- und Namensverzeichnis.

Read more less

Book SynopsisDrei Ziele haben Stoffauswahl und Darstellung dieses Buches: Studierende erlernen die Codierung von Algorithmen mit MODULA-2, einer modernen imperativen Programmiersprache, die so einfach und sauber ist, dass die Grundbegriffe der Programmierung klar und systematisch eingeführt werden können, die sich aber andererseits auch in der Praxis bewährt. Wichtig ist auch die Möglichkeit, in MODULA-2 den Objektbegriff vorzubereiten. Theoretische Aspekte, z.B. Berechenbarkeit, Grammatiken, Semantik und Programmierverifikation, werden ganz überwiegend im Zusammenhang mit konkreten Problemen der Programmierung behandelt, so dass der praktische Nutzen jederzeit erkennbar bleibt.Trade Review"Das mit vielen vollständigen Programmbeispielen aufgelockerte Skript eignet sich daher für Studiengänge der Hauptfach-, Nebenfach-, oder sogenannten Bindestrich-Informatik, in denen Konzepte und Praxis der Programmierung nicht separat, sondern gegenseitig stützend entwickelt werden sollen." RKW - BücherdienstTable of Contents1. Grundlagen.- 1.1 Algorithmus und Berechenbarkeit.- 1.1.1 Algorithmus.- 1.1.2 Turing-Maschine.- 1.1.3 Berechenbarkeit.- 1.2 Sprache und Grammatik.- 1.2.1 Sprache.- 1.2.2 Grammatik.- 1.3 Rechner.- 1.3.1 Von-Neumann-Rechnerarchitektur.- 1.3.2 Rechnersysteme.- 1.4 Informatik als Wissenschaft.- 2. Imperative Programmierung — die Sprache Modula-2.- 2.1 Syntaxdarstellungen.- 2.2 Elementare funktionale Modula-2-Programme.- 2.2.1 Eine Modula-2-Teilsprache.- 2.2.2 Programmverzweigungen.- 2.2.3 Funktionen und Prozeduren.- 2.2.4 Elementare Datentypen, Aufzählungs- und Bereichstypen.- 2.2.5 Eingabevariablen.- 2.2.6 Rekursive Funktionen und Prozeduren.- 2.2.7 Nachteile funktional-rekursiver Programme.- 2.3 Iterative Programme.- 2.3.1 Wertzuweisungen und Referenzparameter.- 2.3.2 Gültigkeitsbereich und Lebensdauer.- 2.3.3 Anweisungen zur Iteration.- 2.3.4 Vergleich iterativer und rekursiver Lösungen.- 2.3.5 Sprunganweisungen.- 2.3.6 Prozedurtypen.- 2.4 Komplexe Datentypen.- 2.4.1 Mengen (Sets).- 2.4.1.1 Darstellung und Manipulation von Mengen.- 2.4.1.2 Ein Beispiel für Sets.- 2.4.2 Arrays (Felder).- 2.4.3 Records (Verbunde).- 2.4.3.1 Einfache Records.- 2.4.3.2 Records mit Varianten.- 2.4.4 Zeiger (Pointer) und dynamische Variablen.- 2.4.4.1 Die Speicherung auf der Halde.- 2.4.4.2 Operationen auf Zeigern.- 2.4.4.3 Verkettete Listen.- 2.4.4.4 Anwendungen und Probleme dynamischer Variablen.- 2.4.5 Dateien (Files).- 2.4.5.1 Eigenschaften und formale Beschreibung.- 2.4.5.2 Dateien in Pascal.- 2.4.5.3 Dateien in Modula-2.- 3. Abstraktion.- 3.1 Abstraktionskonzepte in Programmiersprachen.- 3.2 Abstraktion in Modula-2.- 3.2.1 Das Prinzip der separaten Übersetzung.- 3.2.2 Modularisierung eines Programms.- 3.2.3 Datenkapselung.- 3.2.4 Abstrakte Datentypen.- 3.2.4.1 Das Prinzip des Abstrakten Datentyps.- 3.2.4.2 Abstrakte Datentypen Schlange und Stack.- 3.2.4.3 Abstrakter Datentyp für große Zahlen.- 3.2.4.4 Abstrakter Datentyp für komplexe Zahlen.- 4. Semantik, Verifikation und Test.- 4.1 Konzepte für eine Semantikdefinition.- 4.1.1 Semantik: Begriff und Motivation.- 4.1.2 Grundprinzipien von Semantiknotationen.- 4.1.3 Ein Beispiel für die operationale Semantik.- 4.2 Spezifikation und Verifikation von Programmen.- 4.2.1 Vor-und Nachbedingungen.- 4.2.2 Schwächste Vorbedingungen.- 4.2.3 Die Verifikation.- 4.2.4 Beschreibung einer Schleife durch eine Invariante.- 4.2.5 Konstruktion iterativer Programme.- 4.2.6 Zusammenfassung.- 4.3 Test.- 4.3.1 Begriffsbildung und Prinzipien.- 4.3.1.1 Begriffliche Abgrenzung.- 4.3.1.2 Aufgabenteilung und Zielsetzung.- 4.3.1.3 Material und Resultate des Tests.- 4.3.2 Grenzen des Testens.- 4.3.3 Die Konstruktion von Testdaten.- 4.3.4 Zusammenfassung.- 5. Programmierparadigmen und -sprachen.- 5.1 Programmierparadigmen.- 5.1.1 Imperatives Programmieren.- 5.1.2 Funktionales Programmieren.- 5.1.3 Logik-basiertes Programmieren.- 5.1.4 Objektorientiertes Programmieren.- 5.1.5 Regel-basiertes Programmieren.- 5.1.6 Programmierung von Mehrprozessor-Systemen.- 5.2 Übersicht über Programmiersprachen.- 6. Datenstrukturen und Algorithmen.- 6.1 Komplexität und Effizienz.- 6.1.1 Motivation und Begriffsbildung.- 6.1.2 Effizienz und Komplexität von Algorithmen.- 6.1.3 Komplexität von Funktionen und Sprachen.- 6.2 Graphen und Bäume.- 6.2.1 Graphen.- 6.2.2 Bäume.- 6.3 Suchen in gegebenen Datenstrukturen.- 6.3.1 Suchen in Tabellen.- 6.3.2 Suchen von Zeichenketten.- 6.4 Datenorganisationen für effizientes Suchen.- 6.4.1 Suchverfahren auf Bäumen.- 6.4.1.1 Binäre Suchbäume.- 6.4.1.2 AVL-Bäume.- 6.4.1.3 Optimale Suchbäume.- 6.4.1.4 B-Bäume.- 6.4.1.5 Weitere balancierte Suchbäume.- 6.4.2 Hashing.- 6.4.2.1 Begriffsbildung und Anforderungen.- 6.4.2.2 Perfektes Hashing.- 6.4.2.3 Kollisionsbehandlung.- 6.4.2.4 Löschen in Hash-Tabellen.- 6.4.2.5 Aufwandsabschätzung.- 6.4.2.6 Implementierung von Kollisionsbehandlungen.- 6.5 Sortieren.- 6.5.1 Klassifizierung und allgemeine Betrachtungen.- 6.5.2 Interne Sortierverfahren.- 6.5.2.1 Einfache Sortierverfahren.- 6.5.2.2 Schnelle Sortierverfahren.- 6.5.2.3 Implementierung ausgewählter Sortierverfahren.- 6.5.2.4 Aufwandsvergleich der Sortierverfahren.- 6.5.2.5 Sortieren durch Streuen und Sammeln.- 6.5.3 Externe Sortierverfahren.- 6.5.3.1 Direktes Mischen.- 6.5.3.2 Natürliches Mischen.- 6.5.3.3 Mehrwege-Mischen.- 6.6 Speicherverwaltung.- 6.6.1 Algorithmische Konzepte.- 6.6.2 Implementierung von Stacks.- Anhang A: Mathematische Grundbegriffe und Formeln.- Anhang B: Syntaxdiagramme für Modula-2.- Literatur.- Abkürzungsverzeichnis.- Modula-2-Index.

Read more less

Book SynopsisDer Student erhält eine zuverlässige und detaillierte Übersicht über das konkrete Studienangebot der Fachhochschule. Gleichzeitig bekommt er konkrete Praktikums- und Karriereoptionen aufgezeigt: Mit spannenden Praktikerportraits und über 70 Firmenprofilen solcher Unternehmen, die die Vorzüge des FH-Studiums für das eigene Unternehmen zu schätzen wissen. Das neue Werk versteht sich als aktuelles und umfassendes Servicehandbuch, Übersicht und Orientierungshilfe für Studienbewerber, Studienanwärter, Fachhochschulstudenten und -absolventen. Es bietet einen detaillierten Einblick in das Studium der IT-Studiengänge an der Fachhochschule und die damit verbundenen Berufs- und Karrierechancen. Trade Review"Angesichts des Bedarfs gerade von FH-Absolventen dürfte der Führer auf breites Interesse stoßen." (ekz-Bibliotheksdienst, ID 29/02)Table of ContentsBildungsauftrag der Fachhochschule - Gestaltung der Praxisnähe - FH-Professoren: Erreichbare Coaches - IT-Studiengänge an der Fachhochschule - Praktika, Persönliche Qualifizierung - Tipps für Studium und Berufseinstieg - Erfolgs-Stories von IT-Praktikern mit FH-Abschluss - Fachhochschulen stellen sich vor - Unternehmen stellen sich vor

Read more less

Book SynopsisTable of Contents1. Algorithmen.- 1.1 Was ist ein Algorithmus?.- Euklidischer Algorithmus.- Die Fähigkeiten des Computers.- 1.2 Lineare Anweisungsfolge.- Variable und Konstante.- Name von Variablen.- Wertzuweisung.- Programmablaufplan.- Hilfsvariable.- Ein- und Ausgabe von Daten.- Die Zahlenmengen der EDV.- Abschneiden und Runden.- Abschneiden.- Runden.- 1.3 Bedingte Anweisungen (Verzweigungen).- Sortierprobleme.- Zusammengesetzte Bedingungen.- 1.4 Schleifen.- Laufanweisungen.- Auflösen von Laufanweisungen.- Schleifen mit Bedingungen.- Ineinandergeschachtelte Schleifen.- 1.5 Felder.- Sortieren eines Feldes.- Tabellen.- Äquidistante Schlüsselwerte.- Sequentielles Suchen und Interpolieren in geordneten Tabellen.- Binäres Suchen.- Doppelt indizierte Felder.- 1.6 Funktionen.- Funktionen mit mehreren Parametern.- 1.7 Unterprogramme.- 2. Algol.- 2.1 Was ist eine Programmiersprache?.- 2.2 Lineare Anweisungsfolge.- Abschneiden.- Runden.- Die Programmierung von Termen.- 2.3 Bedingte Anweisungen (Verzweigungen).- Sortierprobleme.- Zusammengesetzte Bedingungen.- 2.4 Schleifen.- Auflösen der Laufanweisung.- Schleifen mit Bedingung.- Ineinandergeschachtelte Laufanweisungen.- 2.5 Felder.- Sortieren eines Feldes.- Tabellen.- Äquidistante Tabellen.- Sequentielles Suchen in geordneten Tabellen.- Binäres Suchen.- Doppelt indizierte Felder.- 2.6 Funktionen.- Standardfunktionen.- Funktionen mit mehreren Parametern.- 2.7 Unterprogramme.- Zusammenfassung der ALGOL-Begriffe.- 3. Fortran.- 3.1 Was ist eine Programmiersprache?.- 3.2 Die Programmierung einer linearen Anweisungsfo1ge.- Erläuternde Kommentare zu einem FORTRAN-Programm.- Ausgabe von Text.- Die Programmierung von Termen.- Abschneiden und Runden.- 3.3 Bedingte Anweisungen (Verzweigungen).- Sortierprobleme.- Zusammengesetzte Bedingungen.- 3.4 Schleifen.- Aufgelöste Schleifenanweisung.- Schleifen mit Bedingung.- Ineinandergeschachtelte Schleifenanweisung.- 3.5 Felder.- Suchen und Interpolieren in Tabellen.- Tabellen mit äquidistanten Schlüsselwerten.- Tabellen mit geordneten Schlüsselwerten.- Doppelt indizierte Felder.- 3.6 Funktionen.- Standardfunktionen.- Funktionen mit mehreren Parametern.- 3.7 Unterprogramme.- Zusammenfassung der Grundbegriffe der Programmiersprache FORTRAN.- 4. Aufgaben.- E Aufgaben aus elementaren Stoffgebieten.- M Aufgaben aus der Mengenlehre.- Z Aufgaben mit ganzen Zahlen (Zahlentheorie).- S Aufgaben mit Gesamtheiten reeller Zahlen (Statistik, Tabellen).- G Aufgaben mit Gleichungen und Ungleichungen.- F Aufgaben über Funktionen.- A Aufgaben über Vektoren und analytische Geometrie.- T Aufgaben aus der Trigonometrie.- R Aufgaben über Folgen und Reihen.- N Näherungsmethoden.- I Aufgaben aus der Integralrechnung.- V Verschiedenes.- Geschichtlicher Überblick.- Weiterführende Literatur.- Stichwortverzeichnis.

Read more less

Book SynopsisGegenstand dieses Werkes sind die Theorie und Praxis der modernen funktionalen Programmierung. Dabei betrachten die Autoren aber nicht nur das, was mittels der heute implementierten Sprachen wie HASKELL, OPAL, ML usw. machbar ist, sondern weisen auch auf aktuelle Entwicklungen hin. Zum einen werden fortgeschrittene Programmiertechniken vorgestellt, wie z.B. die Verwendung unendlicher Datenstrukturen, Parser als Funktionen höherer Ordnung, Approximations-Algorithmen, Lösung von Gleichungssystemen usw. Zum anderen werden aber auch Sprachkonzepte diskutiert, wie z.B. eine systematische Form der Modularisierung oder besonders ausdrucksstarke und flexible Formen der Typisierung. Ein besonderes Gewicht wird generell auf die Integration verschiedener Paradigmen gelegt, wie etwa die Verbindung mit Konzepten der objektorientierten, der nebenläufigen oder der Constraint-basierten Programmierung. In diesem Zusammenhang wird speziell auch die Bedeutung von Monaden analysiert und kritisch hinterfragt.Trade ReviewAus den Rezensionen: "Bei diesem Titel … werden … fortgeschrittene Leser angesprochen, die mit den Grundlagen der funktionalen Programmierung vertraut sind. … ‘Im Vordergrund stehen Ideen und Konzepte einer eleganten, sicheren und produktiven Form des Programmierens‘, wobei der Blick in die Zukunft gerichtet ist und Konzepte und Methoden vorgestellt werden, die erst in den Sprachen der nächsten Generation verfügbar sein werden. Geeignet für Bibliotheken … an Hochschulstandorten … Das Lehrbuch kann noch weiter genutzt werden." (Isigkeit, in: ekz-Informationsdienst, 2006)Table of ContentsElementare Funktionale Programmierung Eine Wiederholung.- Das Strittigste vorab: Notationen.- Grundlagen der Funktionalen Programmierung.- Faulheit währt unendlich.- Parser als Funktionen höherer Ordnung.- Strukturierung von Programmen.- Gruppen: Die Basis der Modularisierung.- Operatoren auf Gruppen (Morphismen).- Die Idee der Typisierung.- Typen.- Subtypen (Vererbung).- Polymorphe und abhängige Typen.- Spezifikationen und Typklassen: Wie Typen typisiert werden.- Beispiel: Berechnung von Fixpunkten.- Beispiel: Monaden.- Datenstrukturen.- Netter stack und böse Queue.- Compilertechniken für funktionale Datenstrukturen.- Funktionale Arrays und Numerische Mathematik.- Map: Wenn Funktionen zu Daten werden.- Beispiel: Synthese von Programmen.- Integration von Paradigmen.- Zeit und Zustand in der funktionalen Welt.- Objekte und Ein-/Ausgabe.- Agenten und Prozesse.- Graphische Schnittstellen (GUIs).- Massiv parallele Programme.- Integration von Konzepten anderer Programmierparadigmen.

Read more less

Book SynopsisTesting is the primary hardware and software verification technique used by industry today. Usually, it is ad hoc, error prone, and very expensive. In recent years, however, many attempts have been made to develop more sophisticated formal testing methods. This coherent book provides an in-depth assessment of this emerging field, focusing on formal testing of reactive systems. This book is based on a seminar held in Dagstuhl Castle, Germany, in January 2004. It presents 19 carefully reviewed and revised lectures given at the seminar in a well-balanced way ensuring competent complementary coverage of all relevant aspects. An appendix provides a glossary for model-based testing and basics on finite state machines and on labelled transition systems. The lectures are presented in topical sections on testing of finite state machines, testing of labelled transition systems, model-based test case generation, tools and case studies, standardized test notation and execution architectures, and beyond testing.Table of ContentsTesting of Finite State Machines.- I. Testing of Finite State Machines.- 1 Homing and Synchronizing Sequences.- 2 State Identification.- 3 State Verification.- 4 Conformance Testing.- II. Testing of Labeled Transition Systems.- Testing of Labeled Transition Systems.- 5 Preorder Relations.- 6 Test Generation Algorithms Based on Preorder Relations.- 7 I/O-automata Based Testing.- 8 Test Derivation from Timed Automata.- 9 Testing Theory for Probabilistic Systems.- III. Model-Based Test Case Generation.- Model-Based Test Case Generation.- 10 Methodological Issues in Model-Based Testing.- 11 Evaluating Coverage Based Testing.- 12 Technology of Test-Case Generation.- 13 Real-Time and Hybrid Systems Testing.- IV. Tools and Case Studies.- Tools and Case Studies.- 14 Tools for Test Case Generation.- 15 Case Studies.- V. Standardized Test Notation and Execution Architecture.- Standardized Test Notation and Execution Architecture.- 16 TTCN-3.- 17 UML 2.0 Testing Profile.- VI. Beyond Testing.- Beyond Testing.- 18 Run-Time Verification.- 19 Model Checking.- VII. Appendices.- Appendices.- 20 Model-Based Testing – A Glossary.- 21 Finite State Machines.- 22 Labelled Transition Systems.

Read more less

Book SynopsisThis is a thoroughly revised and enlarged second edition that presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. The book is written in such a way that the respective parts on model theory and descriptive complexity theory may be read independently.Table of ContentsPreliminaries.- The Ehrenfeucht-Fraïssé Method.- More on Games.- 0-1 Laws.- Satisfiability in the Finite.- Finite Automata and Logic: A Microcosm of Finite Model Theory.- Descriptive Complexity Theory.- Logics with Fixed-Point Operators.- Logic Programs.- Optimization Problems.- Logics for PTIME.- Quantifiers and Logical Reductions.

Read more less

Book SynopsisThis book constitutes the refereed proceedings of the 7th International Symposium, Latin American Theoretical Informatics, LATIN 2006, held in March 2006. The 66 revised full papers presented together with seven invited papers were carefully reviewed and selected from 224 submissions. The papers presented are devoted to a broad range of topics in theoretical computer science with a focus on algorithmics and computations related to discrete mathematics as well as on cryptography, data compression and Web applications.Table of ContentsKeynotes.- Algorithmic Challenges in Web Search Engines.- RNA Molecules: Glimpses Through an Algorithmic Lens.- Squares.- Matching Based Augmentations for Approximating Connectivity Problems.- Modelling Errors and Recovery for Communication.- Lossless Data Compression Via Error Correction.- The Power and Weakness of Randomness in Computation.- Regular Contributions.- A New GCD Algorithm for Quadratic Number Rings with Unique Factorization.- On Clusters in Markov Chains.- An Architecture for Provably Secure Computation.- Scoring Matrices That Induce Metrics on Sequences.- Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams.- The Complexity of Diffuse Reflections in a Simple Polygon.- Counting Proportions of Sets: Expressive Power with Almost Order.- Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets.- Relations Among Notions of Security for Identity Based Encryption Schemes.- Optimally Adaptive Integration of Univariate Lipschitz Functions.- Classical Computability and Fuzzy Turing Machines.- An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees.- An Algorithm for a Generalized Maximum Subsequence Problem.- Random Bichromatic Matchings.- Eliminating Cycles in the Discrete Torus.- On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions.- Pattern Matching Statistics on Correlated Sources.- Robust Model-Checking of Linear-Time Properties in Timed Automata.- The Computational Complexity of the Parallel Knock-Out Problem.- Reconfigurations in Graphs and Grids.- -Varieties, Actions and Wreath Product.- Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges.- An Efficient Approximation Algorithm for Point Pattern Matching Under Noise.- Oblivious Medians Via Online Bidding.- Efficient Computation of the Relative Entropy of Probabilistic Automata.- A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences.- De Dictionariis Dynamicis Pauco Spatio Utentibus.- Customized Newspaper Broadcast: Data Broadcast with Dependencies.- On Minimum k-Modal Partitions of Permutations.- Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm.- Maximizing Throughput in Queueing Networks with Limited Flexibility.- Network Flow Spanners.- Finding All Minimal Infrequent Multi-dimensional Intervals.- Cut Problems in Graphs with a Budget Constraint.- Lower Bounds for Clear Transmissions in Radio Networks.- Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata.- Lower Bounds for Geometric Diameter Problems.- Connected Treewidth and Connected Graph Searching.- A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs.- The Committee Decision Problem.- Common Deadline Lazy Bureaucrat Scheduling Revisited.- Approximate Sorting.- Stochastic Covering and Adaptivity.- Algorithms for Modular Counting of Roots of Multivariate Polynomials.- Hardness Amplification Via Space-Efficient Direct Products.- The Online Freeze-Tag Problem.- I/O-Efficient Algorithms on Near-Planar Graphs.- Minimal Split Completions of Graphs.- Design and Analysis of Online Batching Systems.- Competitive Analysis of Scheduling Algorithms for Aggregated Links.- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains.- On Sampling in Higher-Dimensional Peer-to-Peer Systems.- Mobile Agent Rendezvous in a Synchronous Torus.- Randomly Colouring Graphs with Girth Five and Large Maximum Degree.- Packing Dicycle Covers in Planar Graphs with No K 5–e Minor.- Sharp Estimates for the Main Parameters of the Euclid Algorithm.- Position-Restricted Substring Searching.- Rectilinear Approximation of a Set of Points in the Plane.- The Branch-Width of Circular-Arc Graphs.- Minimal Eulerian Circuit in a Labeled Digraph.- Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization.- RISOTTO: Fast Extraction of Motifs with Mismatches.- Minimum Cost Source Location Problems with Flow Requirements.- Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms.- Constructions of Approximately Mutually Unbiased Bases.- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In.

Read more less

Book SynopsisThe workshop on Computability and Complexity in Analysis, CCA 2000, was hosted by the Department of Computer Science of the University of Wales Swansea, September 17{19, 2000. It was the fourth workshop in a successful series of workshops: CCA’95 in Hagen, Germany, CCA’96 in Trier, Germany, and CCA’98 in Brno, Czech Republic. About 40 participants from the countries United Kingdom, Germany, Japan, Italy, Russia, France, Denmark, Greece, and Ireland contributed to the success of this meeting. Altogether, 28 talkswere p- sented in Swansea. These proceedings include 23 papers which represent a cro- section through recent research on computability and complexity in analysis. The workshop succeeded in bringing together people interested in computability and complexity aspects of analysis and in exploring connections with nume- cal methods, physics and, of course, computer science. It was rounded o by a number of talks and papers on exact computer arithmetic and by a competition of v e implemented systems. A report on this competition has been included in these proceedings. We would like to thank the authors for their contributions and the referees for their careful work, and we hope for further inspiring and constructive meetings of the same kind. April 2001 Jens Blanck Vasco Brattka Peter Hertling Organization CCA2000was hosted by the Department of Computer Science of the University of Wales Swansea and took place on September 17{19, 2000.Table of ContentsComputability and Complexity in Analysis.- Effectivity of Regular Spaces.- The Degree of Unsolvability of a Real Number.- A Survey of Exact Arithmetic Implementations.- Standard Representations of Effective Metric Spaces.- Banach-Mazur Computable Functions on Metric Spaces.- A Generic Root Operation for Exact Real Arithmetic.- Effective Contraction Theorem and Its Application.- Polynomially Time Computable Functions over p-Adic Fields.- On the Computational Content of the Krasnoselski and Ishikawa Fixed Point Theorems.- Formalisation of Computability of Operators and Real-Valued Functionals via Domain Theory.- Computing a Required Absolute Precision from a Stream of Linear Fractional Transformations.- ?-Approximable Functions.- Computabilities of Fine-Continuous Functions.- The iRRAM: Exact Arithmetic in C++.- The Uniformity Conjecture.- Admissible Representations of Limit Spaces.- Characterization of the Computable Real Numbers by Means of Primitive Recursive Functions.- Effective Fixed Point Theorem over a Non-Computably Separable Metric Space.- Computational Dimension of Topological Spaces.- Some Properties of the Effective Uniform Topological Space.- On Computable Metric Spaces Tietze-Urysohn Extension Is Computable.- Is the Linear Schrödinger Propagator Turing Computable?.- A Computable Spectral Theorem.- Report on Competition.- Exact Real Arithmetic Systems: Results of Competition.

Read more less

Book Synopsisto the Encyclopaedia Subseries on Operator Algebras and Non-Commutative Geometry The theory of von Neumann algebras was initiated in a series of papers by Murray and von Neumann in the 1930's and 1940's. A von Neumann algebra is a self-adjoint unital subalgebra M of the algebra of bounded operators of a Hilbert space which is closed in the weak operator topology. According to von Neumann's bicommutant theorem, M is closed in the weak operator topology if and only if it is equal to the commutant of its commutant. Afactor is a von Neumann algebra with trivial centre and the work of Murray and von Neumann contained a reduction of all von Neumann algebras to factors and a classification of factors into types I, II and III. C* -algebras are self-adjoint operator algebras on Hilbert space which are closed in the norm topology. Their study was begun in the work of Gelfand and Naimark who showed that such algebras can be characterized abstractly as involutive Banach algebras, satisfying an algebraic relation connecting the norm and the involution. They also obtained the fundamental result that a commutative unital C* -algebra is isomorphic to the algebra of complex valued continuous functions on a compact space - its spectrum. Since then the subject of operator algebras has evolved into a huge mathematical endeavour interacting with almost every branch of mathematics and several areas of theoretical physics.Trade ReviewFrom the reviews:"... These notes [by E.Stormer] describe the main approaches to noncommutative entropy, together with several ramifications and variants. The notion of generator and variational principle are used to give applications to subfactors and C*-algebra formalism of quantum statistical mechanics. The author considers the most frequently studied examples, including Bernoulli shifts, Bogolyubov automorphisms, dual automorphisms on crossed products, shifts on infinite free products, and binary shifts on the CAR-algebra. The mathematical techniques and ideas are beautifully exposed, and the whole paper is a rich resource on the subject, either for the expert or the beginner. ..."V.Deaconu, Mathematical Reviews 2004"... the author gives a clear presentation of the dramatic developments in the classification theory for simple C*-algebras that have taken place over the past 25 years or so. ... As there is such a large amount of literature on the subject, this monograph article is particularly useful to the relative novice who wants to know the fundamental results in the theory without wading through a massive amount of detail. ...This monograph-length article is extremely well-written, filled with concrete examples, and has an exhaustive bibliography. I recommend it as an excellent introduction to graduate students and other mathematicians who want to bring themselves up-to-date on the subject. .."J.A.Packer, Mathematical Reviews 2004“Both contributions to this volume are high-end, excellently written research reviews, reflecting very thoroughly the current status in the respectively treated subbranches of the quickly evolving complex field of C* algebra theory. They both give a beautiful lay-out of the vast research program in the field which has been going on for decades … as well as to the standard works. … an excellent, very thorough, concise and needed overview for the researcher who is active in this field.” (Mark Sioen, Bulletin of the Belgian Mathematical Society, 2007) Table of ContentsI. Classification of Nuclear, Simple C*-algebras.- II. A Survey of Noncommutative Dynamical Entropy.

Read more less

Book SynopsisThis monograph covers the recent major advances in various areas of set theory. From the reviews: "One of the classical textbooks and reference books in set theory....The present ‘Third Millennium’ edition...is a whole new book. In three parts the author offers us what in his view every young set theorist should learn and master....This well-written book promises to influence the next generation of set theorists, much as its predecessor has done." --MATHEMATICAL REVIEWSTrade ReviewFrom the reviews of the third edition: "Thomas Jech’s text has long been considered a classic survey of the state of the set theory … . As every logician will know, this is a work of extraordinary scholarship, essential for any graduate logician who needs to know where the current boundaries of research are situated. Each chapter ends with a valuable historical survey and there is an extensive bibliography. This will continue to be the bible for set theorists in the new century." (Gerry Leversha, The Mathematical Gazette, March, 2005) "The book does masterly what it is supposed to do. … every mathematician who wishes to refresh his knowledge of set theory will read it with pleasure. … They will also find historical notes, and precise references … . A very comprehensive bibliography, and detailed indexes complete the work. This book fills a serious gap in the literature and there is no doubt that it will become a standard reference … . One can strongly recommend its acquisition for any mathematical library." (Jean-Roger Roisin, Bulletin of the Belgian Mathematical Society, Vol. 11 (3), 2004) "One of the classical textbooks and reference books in set theory is Jech’s Set Theory. … The present ‘Third Millennium’ edition … is a whole new book. In three parts the author offers us what in his view every young set theorist should learn and master. … This well-written book promises to influence the next generation of set theorists, much as its predecessor has done over the last quarter of a century." (Eva Coplakova, Mathematical Reviews, 2004 g) "Jech’s book, ‘Set Theory’ has been a standard reference for over 25 years. This ‘Third Millennium Edition’, not only includes all the materials in the first two editions, but also covers recent developments of set theory during the last 25 years. We believe that this new version will become a standard reference on set theory for the next few years." (Guohua Wu, New Zealand Mathematical Society Newsletter, April, 2004) "Jech’s classic monograph has been a standard reference for a generation of set theorists. Though … labeled ‘The Third Millennium Edition’, the present work is in fact a new book. ... Even sections presenting older results have been rewritten and modernized. Exercises have been moved to the end of each section. The bibliography, the section on notation, and the index have been considerably expanded as well. This new edition will certainly become a standard reference on set theory for years to come." (Jörg D. Brendle, Zentralblatt MATH, Vol. 1007, 2003) "Thomas Jech’s Set Theory contains the most comprehensive treatment of the subject in any one volume. The present third edition is a revised and expanded version … . The third edition has three parts. The first, Jech says, every student of set theory should learn, the second every set theorist should master and the third consists of various results reflecting ‘the state of the art of set theory at the turn of the new millennium’. This last part especially contains a lot of new material." (Martin Bunder, The Australian Mathematical Society Gazette, Vol. 30 (2), 2003)Table of ContentsBasic Set Theory.- Axioms of Set Theory.- Ordinal Numbers.- Cardinal Numbers.- Real Numbers.- The Axiom of Choice and Cardinal Arithmetic.- The Axiom of Regularity.- Filters, Ultrafilters and Boolean Algebras.- Stationary Sets.- Combinatorial Set Theory.- Measurable Cardinals.- Borel and Analytic Sets.- Models of Set Theory.- Advanced Set Theory.- Constructible Sets.- Forcing.- Applications of Forcing.- Iterated Forcing and Martin’s Axiom.- Large Cardinals.- Large Cardinals and L.- Iterated Ultrapowers and L[U].- Very Large Cardinals.- Large Cardinals and Forcing.- Saturated Ideals.- The Nonstationary Ideal.- The Singular Cardinal Problem.- Descriptive Set Theory.- The Real Line.- Selected Topics.- Combinatorial Principles in L.- More Applications of Forcing.- More Combinatorial Set Theory.- Complete Boolean Algebras.- Proper Forcing.- More Descriptive Set Theory.- Determinacy.- Supercompact Cardinals and the Real Line.- Inner Models for Large Cardinals.- Forcing and Large Cardinals.- Martin’s Maximum.- More on Stationary Sets.

Read more less

Book SynopsisThis volume contains selected papers for the Parcella '88, the Fourth International Workshop on "Parallel Processing by Cellular Automata and Arrays" held in Berlin from October 17 to 21, 1988. The profile of the Parcella workshop series is focused on problems of processing by regular structures, i.e. their "flexibilization" or adapting to "irregular" algorithms and, closely related to this, on the "regularization" of algorithms for their embedding into regular structures. It seems that these problems will have an increasing priority within the list of central problems in parallelization and will determine the profile of Parcella for the next years.Table of ContentsMultiprocessor arrays: Topology, efficiency and fault-tolerance.- Unsolved theoretical problems in homogeneous structures.- On simultaneous realizations of boolean functions, with applications.- Parallel microprogramming as a tool for multi-microprocessor systems.- A survey of parallel computational geometry algorithms.- Parallel memories for straight line and rectangle access.- Programming with active data.- Prolog implementations for cellular architectures.- Modular highly-parallel computation and architectures.- Parallel computation and supercomputers and applications.- Fast parallel algorithms and the complexity of parallelism (basic issues and recent advances).- Process-structured architectures to transform information flowing through.- Basic research for cellular processing.- Parallel algorithms in image processing.- VLSI arrays implementing parallel line-drawing algorithms.- Parallel conflict-free optimal access to complete extended q-ary trees.- Systolic preconditioning algorithms for the jacobi iterative solution of sparse linear systems.- Multiprocessor systems for large numerical applications.- Systolic array for eigenvalue of jacobi matrix.- A transitive closure algorithm for a 16-state cellprocessor.- Control of sensory processing — A hypothesis on and simulation of the architecture of an elementary cortical processor.- Bounds for l-selection and related problems on grids of processors.- Recursive design of communication schemes for parallel computation with relacs.- Solution of dense systems of linear equations using cellular processors.- Running order statistics on a bit-level systolic array.- Realization of sets of permutations by permutation networks.- Simulation of learning networks.- Given's rotation on an instruction systolic array.- Worst case analysis for reducing algorithms on instruction systolic arrays with simple instruction sets.- Self-checking processing elements in cellular arrays.- Cellular diagnostic in parallel systems.- Reliable networks for boolean functions with small complexity.- Pipeline-automata — A model for acyclic systolic systems.

Read more less

Book SynopsisThis book is written for those who are interested in a fonnalization of human reasoning, especially in order to build "intelligent" computer systems. Thus, it is mainly designed for the Artificial Intelligence community, both students and researchers, although it can be useful for people working in related fields like cognitive psychology. The major theme is not Artificial Intelligence applications, although these are discussed throughout in sketch fonn. Rather, the book places a heavy emphasis on the fonnal development of default logic, results and problems. Default logic provides a fonnalism for an important part of human reasoning. Default logic is specifically concerned with common sense reasoning, which has recently been recognized in the Artificial Intelligence literature to be of fundamental importance for knowledge representation. Previously, fonnalized reasoning systems failed in real world environments, though succeeding with an acceptable ratio in well-defined environments. This situation enabled empirical explorations and the design of systems without theoretical justification. In particular, they could not be compared since there was no basis to judge their respective merits. Default logic turned out to be very fruitful by proving the correctness of some of them. We hope that this book will initiate other successful developments in default logic.Table of Contents1. Default Reasoning.- 2. Formal Logic as a Knowledge Representation Scheme.- 3. First Order Logic.- 4. Nonmonotonic Extensions for First Order Logic.- 5. Presentation of Default Logic.- 6. Formal Development of Default Logic.- 7. Normal Defaults.- 8. Further Topics in Default Logic.- 9. Fragments of Default Logic.- 10. Problems with Default Logic.- 11. Default Logic Revisited.- 12. Circumscription.- 13. Other Logic Formalizations of Nonmonotonic Reasoning.- Appendix: Origin of the Theorems.- References.- Table of Symbols.

Read more less