Revising Type-2 Computation and Degrees of Discontinuity - Ziegler, Martin (Electronic Notes in Theoretical Computer Science)

Real Hypercomputation and Continuity - Ziegler, Martin (Theory of Computing Systems)

(Short) Survey of Real Hypercomputation - Ziegler, Martin (Lecture Notes in Computer Science)

Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation - Meer, Klaus; Ziegler, Martin (Mathematical Foundations of Computer Science 2007)

On Faster Integer Calculations using Non-Arithmetic Primitives - Lürwer-Brüggemeier, Katharina; Ziegler, Martin (arXiv:0709.0624)
The unit cost model is both convenient and largely realistic for describing integer decision algorithms over (+,*). Additional operations like division with remainder or bitwise conjunction, although equally supported by computing hardware, may lead to a considerable drop in complexity. We show a variety of concrete problems to benefit from such NON-arithmetic primitives by presenting and analyzing corresponding fast algorithms.

Real Computability and Hypercomputation - Ziegler, Martin

Interactive Refinement of a Material Flow Simulation Model by Comparing Multiple Simulation Runs in one 3D Environment - Fischer, Matthias; Laroque, Christoph; Huber, Daniel; Krokowski, Jens; Mueck, Bengt; Kortenjan, Michael; Aufenanger, Mark; Dangelmaier, Wilhelm (European Simulation and Modelling Conference (ESM 2007))
The validation of material flow models as well as the selection of promising strategies for the generation of a successful experiment plan is a time-consuming process. A new approach is presented, which supports the simulation expert in his working process by giving him the opportunity to modify the simulated simulation run and afterwards compare the effects of his modification with the original setting, online and in one user interface, implemented by switching the visualizations between the simulation runs or opening up to 5 parallel 3D windows. The method developed therefore clones existing simulation runs online and allows the navigation within these existing simulation runs. The method has been implemented and is validated by a test model, which describes in detail the new working process of a modeler. New research questions are derived from this work, which will define following working steps.

Ein ganzheitlicher Ansatz zur immersiven 3D-Materialflusssimulation innerhalb der Digitalen Fabrik - Dangelmaier, Wilhelm; Laroque, Christoph; Fischer, Matthias (Augmented & Virtual Reality in der Produktentstehung)

Estimating Clustering Indexes in Data Streams - Buriol, Luciana S.; Frahling, Gereon; Leonardi, Stefano; Sohler, Christian (Proceedings of the 15th European Symposium on Algorithms (ESA))
We present random sampling algorithms that with probability at least 1 − δ compute a (1 ±ε)-approximation of the clustering coefficient and of the number of bipartite clique subgraphs of a graph given as an incidence stream of edges. The space used by our algorithm to estimate the clustering coefficient is inversely related to the clustering coefficient of the network itself. The space used by our algorithm to compute the number K 3,3 of bipartite cliques is proportional to the ratio between the number of K 1,3 and K 3,3 in the graph. Since the space complexity depends only on the structure of the input graph and not on the number of nodes, our algorithms scale very well with increasing graph size. Therefore they provide a basic tool to analyze the structure of dense clusters in large graphs and have many applications in the discovery of web communities, the analysis of the structure of large social networks and the probing of frequent patterns in large graphs. We implemented both algorithms and evaluated their performance on networks from different application domains and of different size; The largest instance is a webgraph consisting of more than 135 million nodes and 1 billion edges. Both algorithms compute accurate results in reasonable time on the tested instances.

On Testable Properties in Bounded Degree Graphs - Sohler, Christian; Czumaj, Artur (Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'07))
We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. We call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is O(1/log2 n), where n is the graph size). A graph family is hereditary if it is closed under vertex removal. Similarly, a graph property is hereditary if it is closed under vertex removal. Next, we call a graph property Π to be testable for a graph family F if for every graph G ε F, in time independent of the size of G we can distinguish between the case when G satisfies property Π and when it is far from every graph satisfying property Π. In this paper we prove thatIn the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs.As an application, our result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.