Mathematical Aspects of Computer and Information Sciences

Name: Mathematical Aspects of Computer and Information Sciences | 6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers

Ilias S. Kotsireas Siegfried M. Rump Chee K. Yap(Herausgeber*in)

Springer (Verlag)

Erschienen am 16. April 2016

XXIII, 628 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-32859-1 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Abstracts of Invited Papers
Current Challenges in Developing Open Source Computer Algebra Systems
Modeling Side-Channel Leakage
Solving Structured Polynomial Systems with Gröbner Bases
Exploiting Structure in Floating-Point Arithmetic
Symbolic Geometric Reasoning with Advanced Invariant Algebras
Decidability from a Numerical Point of View
Congruence Testing of Point Sets in Three and Four Dimensions Results and Techniques
Contents
Invited Papers
Current Challenges in Developing Open Source Computer Algebra Systems
1 Introduction
2 Seven Challenges
2.1 Reconsidering the Efficiency of the Basic Algorithms
2.2 Parallelization
2.3 Make More and More of the Abstract Concepts of Algebraic Geometry Constructive
2.4 Interaction and Integration of Computer Algebra Systems and Libraries from Different Areas of Research
2.5 A Convenient Hierarchy of Languages
2.6 Create and Integrate Electronic Libraries and Databases Relevant to Research
2.7 Facilitating the Access to Computer Algebra Systems
3 A Parallel Approach to Normalization
4 Computing GIT-Fans
References
Exploiting Structure in Floating-Point Arithmetic
1 Introduction
2 Low-Level Properties
3 Revisiting Some Classical Wilkinson-Style Error Bounds
3.1 Summation
3.2 Other Examples of O(u2)-Free Error Bounds
4 Provably Accurate Numerical Kernels
4.1 Computation of ab+cd
4.2 Complex Multiplication
References
Symbolic Geometric Reasoning with Advanced Invariant Algebras
1 Algebraic Approach to Geometric Reasoning
2 Geometric Reasoning by Basic and Advanced Invariants
3 Euclidean Invariants: From Basic to Advanced Ones
4 Conclusion
References
Congruence Testing of Point Sets in Three and Four Dimensions
1 Problem Statement
2 Two Dimensions
3 Three Dimensions
4 Pruning and Condensation
5 The Three-Dimensional Point Groups
6 General Dimensions
7 Four Dimensions
7.1 Iterative Pruning and Condensation Using the Closest-Pair Graph (Algorithm C)
7.2 Generating Orbit Cycles (Algorithm O)
7.3 Marking and Condensation of Great Circles (Algorithm M)
7.4 The Mirror-Symmetric Case (Algorithm R)
7.5 2+2 Dimension Reduction
8 The Four-Dimensional Point Groups
References
Curves and Surfaces
Mesh Reduction to Exterior Surface Parts via Random Convex-Edge Affine Features
1 Motivation
2 Alignment Algorithms
3 Strategies for Estimating the Outer Dimensions of an Object
4 Random Convex-Edge Affine Feature (RanCEAF) Selection
5 Evaluation
6 Results
7 Outlook
References
Numeric and Certified Isolation of the Singularities of the Projection of a Smooth Space Curve
1 Introduction
1.1 Previous Works
1.2 Notations and Assumptions
2 Description of the Singularity Locus
3 Modeling System
3.1 Ball System
3.2 Regularity Condition
4 Experiments
4.1 Resolution Methods
4.2 Singularities Isolation: Comments on Tables1, 2 and 3
5 Conclusion
References
Linear k-Monotonicity Preserving Algorithms and Their Approximation Properties
1 Introduction
2 The Example of Preservation k-Monotonocity
3 The Main Result
4 Conclusion
References
Applied Algebraic Geometry
Workspace Multiplicity and Fault Tolerance of Cooperating Robots
1 Introduction
2 Formal Problem Statement
3 Workspace Computation
4 Homotopy Continuation
5 Two Examples
5.1 2D Case: Two Link Planar Robots
5.2 3D Case: Three Joint Manipulators
6 Conclusion
References
Numerical Local Irreducible Decomposition
1 Introduction
2 Local Witness Sets
3 Computing Numerical Local Irreducible Decompositions
4 Examples
4.1 Illustrative Example
4.2 Local Irreducibility and Real Solutions
4.3 Foldable Griffis-Duffy Platform
References
Computing the Chow Variety of Quadratic Space Curves
1 Introduction
2 Coisotropic Quadrics
3 The Chow Variety
4 Conclusion
References
Numerically Testing Generically Reduced Projective Schemes for the Arithmetic Gorenstein Property
1 Introduction
2 Background
2.1 Arithmetically Cohen-Macaulay and Arithmetically Gorenstein
2.2 Hilbert Functions
2.3 Cayley-Bacharach Property
2.4 Witness Point Sets
3 Method
3.1 Reduced Zero-Dimensional Schemes
3.2 Generically Reduced Positive-Dimensional Schemes
4 Examples
4.1 3(P1P1P1P1)
4.2 3(P1P1P1P2)
4.3 3(4(P2))
References
Some Results Concerning the Explicit Isomorphism Problem over Number Fields
1 Introduction
2 Quadratic Forms
3 Constructing Involutions
References
Cryptography
Implementing Cryptographic Pairings on Accumulator Based Smart Card Architectures
1 Introduction
2 Background
2.1 Definition of Pairings and the Embedding Degree
2.2 Motivation for the Eta Pairing
2.3 The Eta Pairing for Fields of Characteristic 2
3 The Architecture
4 Implementation on the Generic Architecture
4.1 Squaring the Miller Variable
4.2 Point Doubling and Line Functions
4.3 Sparse Multiplication with the Line Function
4.4 The Complete Miller Algorithm
4.5 The Final Exponentiation
5 Performance on Real Hardware
5.1 The SLE 78 Smart Card
5.2 Measurement Setup and Results
5.3 Limitations of Today's Cryptographic Coprocessors
6 Conclusion
References
Short Group Signatures with Distributed Traceability
1 Introduction
2 Preliminaries
3 Group Signature Schemes and Distributed Traceability
4 A Group Signature Scheme with Distributed Traceability
4.1 Construction of Our Group Signature Scheme
4.2 Proof of Anonymity
4.3 Further Properties
5 Extensions and Modifications
References
On the Optimality of Differential Fault Analyses on CLEFIA
1 Introduction
2 Background
2.1 Differential Fault Analysis
2.2 CLEFIA
2.3 Information Theory
3 Differential Fault Analyses on CLEFIA
4 Information-Theoretic Analysis of DFAs on CLEFIA
4.1 General Methodology Adapted to CLEFIA
4.2 Results of the Information-Theoretic Analysis
5 Improvement of the Non-Optimal DFAs
5.1 Improvements on CLEFIA-128
5.2 Improvements on CLEFIA-192 and CLEFIA-256
6 Conclusion
References
Verified Numerical Computation
H3 and H4 Regularities of the Poisson Equation on Polygonal Domains
1 Introduction
2 A Priori Error Estimations
3 Main Theorem
References
Explicit Error Bound for Modified Numerical Iterated Integration by Means of Sinc Methods
1 Introduction
2 Review of Muhammad--Mori's Approximation Formula
2.1 Sinc Quadrature and Sinc Indefinite Integration Combined with the DE Transformation
2.2 Muhammad--Mori's Approximation Formula
3 Main Results: Modified Approximation Formula and Its Explicit Error Bound
3.1 Modified Approximation Formula
3.2 Explicit Error Bound of the Modified Formula
4 Numerical Examples
5 Proofs
5.1 Sketch of the Proof
5.2 Bound of E1 (Error of the DE-Sinc Quadrature)
5.3 Bound of E2 (Error of the DE-Sinc Indefinite Integration)
6 Concluding Remarks
References
Verified Computations for Solutions to Semilinear Parabolic Equations Using the Evolution Operator
1 Introduction
2 Fixed-Point Formulation
3 Main Theorem
References
Verified Error Bounds for the Real Gamma Function Using Double Exponential Formula over Semi-infinite Interval
1 Introduction
2 Error Bounds of the Double Exponential Formula
2.1 Preliminary
2.2 Main Theorem
3 Numerical Result
References
Polynomial System Solving
Improving a CGS-QE Algorithm
1 Introduction
2 Preliminary
3 Computation of Signatures
4 Examples
5 Conclusion and Remarks
References
Efficient Subformula Orders for Real Quantifier Elimination of Non-prenex Formulas
1 Introduction
2 Problem
3 Methodology
3.1 Ordering Functions
3.2 Features and Labeling for Machine Learning
4 Computational Experiments
4.1 Datasets
4.2 Parameter Optimization of SVMs
4.3 An Illustrative Example
4.4 Experimental Results
5 Conclusion
References
Solving Extended Ideal Membership Problems in Rings of Convergent Power Series via Gröbner Bases
1 Introduction
2 Solving Extended Ideal Membership Problems
3 Parametric Cases
3.1 Algebraic Local Cohomology and Membership Problems
3.2 Comprehensive Gröbner Systems (CGS)
3.3 Solving Extended Ideal Membership Problems
4 Concluding Remarks
References
Advanced Algebraic Attack on Trivium
1 Introduction
1.1 Organization
1.2 Related Work
1.3 Our Contributions
2 Trivium
2.1 Definition and Direct Considerations
2.2 Similar Variables
3 Solving the System
3.1 Main Core
4 Experiments
5 Conclusions
References
Managing Massive Data
Compressing Big Data: When the Rate of Convergence to the Entropy Matters
1 Introduction
2 Preliminaries
3 Experimental Results
References
Trends in Temporal Reasoning: Constraints, Graphs and Posets
1 Introduction
2 Preliminaries and Definitions
2.1 The Constraint Satisfaction Problem
2.2 Allen's Interval Algebra
2.3 Subclasses of Allen's Interval Algebra
3 Algebraic Closure Properties of Constraints
4 Posets and the Fishburn-Shepp Inequality
5 Conclusion
References
Reconstructing a Sparse Solution from a Compressed Support Vector Machine
1 Introduction
2 Compression
3 Reconstruction
4 Feature Selection
5 Conclusions
References
Subquadratic-Time Algorithms for Abelian Stringology Problems
1 Introduction
2 Preliminaries
3 Abelian Squares
3.1 First Optimization
3.2 Second Optimization
3.3 Counting All Abelian Squares
3.4 Abelian Borders
4 Abelian Periods
4.1 Computing RP Faster
4.2 Computing GP Faster
5 Abelian Covers
5.1 Optimizing Running Time
6 The Case of a Larger Alphabet
7 Conclusions
References
Using Statistical Search to Discover Semantic Relations of Political Lexica -- Evidences from Bulgarian-Slovak EUROPARL 7 Corpus
1 Introduction
2 Bulgarian-Slovak EUROPARL 7 Corpus
3 The Sketch Engine
3.1 Parallel Corpora Processing in SE
4 Semantic Analysis
4.1 Lexical Relations
5 Conclusion
References
Computational Theory of Differential and Difference Equations
Simple Differential Field Extensions and Effective Bounds
1 Notation
2 Introduction
3 Variations of the Primitive Element Theorem for Differential Field Extensions
4 Improving the Bounds in the Differential Lüroth Theorem
4.1 The Nonconstant Case
4.2 The Constant Case
References
A New Bound for the Existence of Differential Field Extensions
1 Preliminaries
2 Results
References
Dimension Polynomials of Intermediate Fields of Inversive Difference Field Extensions
1 Introduction
2 Preliminaries
3 The Main Theorem
4 Type and Dimension of an Inversive Difference Field Extension
5 Multivariate Dimension Polynomials of Intermediate -field Extensions
References
A ``Polynomial Shifting'' Trick in Differential Algebra
References
Data and Knowledge Exploration
Searching for Geometric Theorems Using Features Retrieved from Diagrams
1 Introduction
2 OpenGeo: A Formalized Geometric Knowledge Base
2.1 Representation of Geometric Knowledge Objects in OpenGeo
2.2 OpenGeo Extension
3 Searching for Geometric Theorems in OpenGeo
3.1 Retrieving Geometric Features from Diagrams
3.2 Filtering Out Irrelevant Theorems Using Features
3.3 Matching Geometric Objects and Relations
4 Processing Results of Searching
4.1 Computing Degrees of Relevance
4.2 Ranking the Results
5 Implementation and Experimental Results
5.1 Implementation Issues
5.2 Examples and Experiments
6 Conclusion and Future Work
References
New Method for Instance Feature Selection Using Redundant Features for Biological Data
1 Introduction
2 New Method for Instance Feature Selection
2.1 Feature Ranking and Pertinence Study
2.2 Similarity Study and Instance Creation
3 Experimental Investigations
4 Conclusion
References
Faceted Search for Mathematics
1 Introduction
2 Preliminaries
3 Schematization of Formula Sets
4 Implementation
5 Finding a Cutoff Heuristic
6 Applications and Future Work
7 Conclusion
References
Evaluation of a Predictive Algorithm for Converting Linear Strings to Mathematical Formulae for an Input Method
1 Introduction
2 Predictive Conversion
2.1 Linear String Rules
2.2 Design of Intelligently Predictive Conversion
2.3 Predictive Algorithm
3 Main Algorithm
4 Conclusion and Future Work
References
Algorithm Engineering in Geometric Computing
Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
1 Introduction
2 Ordered Fields and Rational Functions
3 Parameterized Polyhedra
4 Tropical Dual Convex Hulls
5 Implementation
6 Computations
6.1 Using polymake
6.2 Linear Programs
6.3 Convex Hulls
6.4 Experimental Setup
References
Another Classroom Example of Robustness Problems in Planar Convex Hull Computation
1 Introduction
2 Short Description of Algorithm and Predicates
3 How It Fails
4 Conclusions
References
Precision-Driven Computation in the Evaluation of Expression-Dags with Common Subexpressions: Problems and Solutions
1 Introduction
2 Expression-Dag-Based Number Types
3 Precision-Driven Computation
4 Common Problems with Common Subexpressions
5 Improved Evaluation Strategies
6 Conclusions
References
Real Complexity: Theory and Practice
Rigorous Numerical Computation of Polynomial Differential Equations Over Unbounded Domains
1 Introduction
2 Solving IVPs Over Unbounded Domains
3 Contributions
4 The Numerical Method SolvePIVPEx and Sketch of the Proof of Theorem
References
Using Taylor Models in Exact Real Arithmetic
1 Introduction
2 Computability Using Wrapping Families
3 Computability Using Taylor Models
4 Arithmetic on Taylor Models in ERA
5 Taylor Models in iRRAM
6 Experimental Results
7 Conclusions and Future Work
References
On the Computational Complexity of Positive Linear Functionals on C[0
1]
1 Motivation and Introduction
1.1 Recap of Discrete, Real, and Second-Order Complexity Theory
1.2 Overview, Techniques, and Related Work
2 Smooth Cantor Integration Is at Least as Hard as Continuous Riemann Integration
3 Continuous Cantor Integration is at Most as Hard as Smooth Riemann Integration
4 Generalized Hardness and Tractability Conditions
4.1 Hardness
4.2 Tractability
4.3 Applications and Examples
5 Conclusion and Perspectives
5.1 Prototype Vs. the General Case
References
Average-Case Bit-Complexity Theory of Real Functions
1 Introduction and Motivation
1.1 Real Worst-Case and Average-Case Complexity
2 Average Versus Worst-Case Complexity
2.1 Proof of Theorem3
3 Average-Case and Randomized Expected Polynomial-Time Type-2 Computation
3.1 Probability Distributions on the Represented Space [0
1]
3.2 Local Deterministic Average Versus Randomized Expected Worst-Case
3.3 Proof of Theorem9
4 Conclusion and Perspectives
References
Certifying Trajectories of Dynamical Systems
1 Introduction
2 Fast Numerical Integration
2.1 Classical Algorithms
2.2 Parallelism
3 Global Certification
3.1 From Local to Global Certification
3.2 Certifying a Numerical Trajectory
3.3 Algorithmic Considerations and Parallelism
4 Lagrange Models
4.1 Taylor Models
4.2 Lagrange Models
4.3 Reliable Integration of Dynamical Systems
4.4 Discussion
References
Global Optimization
A New Matrix Splitting Based Relaxation for the Quadratic Assignment Problem
1 Introduction
1.1 Notation and Preliminaries
2 QAP Relaxations Based on Matrix Splitting
2.1 Non-redundant Positive Semidefinite Matrix Splitting
2.2 Interrelated Matrix Splitting
3 Additional Cuts Based on Symmetric Functions
3.1 Further Improvements
4 Numerical Results
References
Global Optimization of H Problems: Application to Robust Control Synthesis Under Structural Constraints
1 Context
2 H Control Synthesis Under Structural Constraints
3 Global Optimization of min/max Problems
4 Application
References
Global Optimization Based on Contractor Programming: An Overview of the IBEX Library
1 Kernel of IBEX
1.1 Interval Arithmetic
1.2 Affine Arithmetic
1.3 Contractor Programming
2 Lists of Contractors
3 Optimization Strategies
References
The Bernstein Branch-and-Prune Algorithm for Constrained Global Optimization of Multivariate Polynomial MINLPs
1 Introduction
2 Background
3 Consistency Techniques
3.1 Bernstein Box Consistency
3.2 Algorithm Bernstein Box Consistency for a Set of Constraints
3.3 Bernstein Hull Consistency
3.4 Algorithm Bernstein Hull Consistency for a Set of Constraints
4 Main Algorithm BBPMINLP
5 Numerical Studies
6 Conclusions
References
General Session
Maximum Likelihood Estimates for Gaussian Mixtures Are Transcendental
1 Introduction
2 Reaching Transcendence
3 Many Critical Points
4 Conclusion
References
On the Quality of Some Root-Bounds
References
Relative Hilbert-Post Completeness for Exceptions
1 Introduction
2 Relative Hilbert-Post Completeness
3 Completeness for Exceptions
4 Completeness of the Core Language for Exceptions
5 Verification of Hilbert-Post Completeness in Coq
6 Conclusion and Future Work
References
Optimal Coverage in Automotive Configuration
1 Introduction
2 Preliminaries
3 Related Work
4 Use Cases in the Context of Automotive Configuration
5 Formal Problem Descriptions
5.1 Encoding of a Variable Target Set
5.2 Encoding of a Boolean Formula Target Set
5.3 Implicit Vehicle Representation
6 Greedy Algorithms
7 Exact Algorithms
8 Experimental Evaluation
8.1 Use Case 1: Optimal Test Vehicle Coverage
8.2 Use Case 2: Optimal Verification Explanation
9 Conclusion and Future Work
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken