Institut für Informatik und Computational Science
Refine
Has Fulltext
- yes (65) (remove)
Year of publication
Document Type
- Doctoral Thesis (65) (remove)
Language
- English (65) (remove)
Keywords
- Maschinelles Lernen (7)
- Antwortmengenprogrammierung (5)
- Machine Learning (5)
- answer set programming (3)
- machine learning (3)
- Algorithmen (2)
- Algorithms (2)
- Answer Set Programming (2)
- Computersicherheit (2)
- Coq (2)
- EEG (2)
- HCI (2)
- ICA (2)
- Knowledge Representation and Reasoning (2)
- Künstliche Intelligenz (2)
- Middleware (2)
- Modell (2)
- Ontologie (2)
- Semantic Web (2)
- Synthese (2)
- Vorhersage (2)
- maschinelles Lernen (2)
- model (2)
- non-photorealistic rendering (2)
- systems biology (2)
- 'Peer To Peer' (1)
- 3D Computer Grafik (1)
- 3D Computer Graphics (1)
- 3D Drucken (1)
- 3D Semiotik (1)
- 3D Visualisierung (1)
- 3D printing (1)
- 3D semiotics (1)
- 3D visualization (1)
- 3D-Stadtmodelle (1)
- 3d city models (1)
- 6LoWPAN (1)
- ASIC (1)
- ASIC (Applikationsspezifische Integrierte Schaltkreise) (1)
- ASP (Answer Set Programming) (1)
- Abbrecherquote (1)
- Abstraktion (1)
- Ackerschmalwand (1)
- Active Evaluation (1)
- Adversarial Learning (1)
- Aktive Evaluierung (1)
- Algorithmenablaufplanung (1)
- Algorithmenkonfiguration (1)
- Algorithmenselektion (1)
- Angewandte Spieltheorie (1)
- Anisotroper Kuwahara Filter (1)
- Anleitung (1)
- Antwortmengen Programmierung (1)
- Applied Game Theory (1)
- Argumentation (1)
- Artificial Intelligence (1)
- Aspect-Oriented Programming (1)
- Aspektorientierte Programmierung (1)
- Asynchrone Schaltung (1)
- Augenbewegungen (1)
- Ausreissererkennung (1)
- BCI (1)
- BSS (1)
- Bachelorstudierende der Informatik (1)
- Baumweite (1)
- Behavior (1)
- Berührungseingaben (1)
- Beweis (1)
- Beweisassistent (1)
- Beweistheorie (1)
- Beweisumgebung (1)
- Bilddatenanalyse (1)
- Bildverarbeitung (1)
- Binäres Entscheidungsdiagramm (1)
- Bioelektrisches Signal (1)
- Bioinformatik (1)
- Boolean constraint solver (1)
- Boosting (1)
- Brain Computer Interface (1)
- Business Process Models (1)
- CASP (Constraint Answer Set Programming) (1)
- CSC (1)
- Cactus (1)
- CertiCoq (1)
- Choreographien (1)
- Classification (1)
- Cloud Computing (1)
- Cloud computing (1)
- Clusteranalyse (1)
- Common Spatial Pattern (1)
- Compliance (1)
- Composition (1)
- Computational Complexity (1)
- Computer Science (1)
- Computergrafik (1)
- Covariate Shift (1)
- Curry (1)
- DDoS (1)
- DPLL (1)
- Data Privacy (1)
- Datenschutz (1)
- Deep Learning (1)
- Dempster-Shafer-Theorie (1)
- Dempster–Shafer theory (1)
- Description Logics (1)
- Deskriptive Logik (1)
- Diagonalisierung (1)
- Didaktik der Informatik (1)
- Dienstkomposition (1)
- Dienstplattform (1)
- Differenz von Gauss Filtern (1)
- Digital Design (1)
- Distributed Computing (1)
- Dynamic Programming (1)
- Dynamische Programmierung (1)
- Dynamische Rekonfiguration (1)
- E-Learning (1)
- Eingabegenauigkeit (1)
- Elektroencephalographie (1)
- Emotionen (1)
- Emotionsforschung (1)
- Entscheidungsbäume (1)
- Entwurfsmuster für SOA-Sicherheit (1)
- Entwurfsprinzipien (1)
- Erfüllbarkeit einer Formel der Aussagenlogik (1)
- Erfüllbarkeitsproblem (1)
- Error Estimation (1)
- Evidenztheorie (1)
- Exploration (1)
- Exponential Time Hypothesis (1)
- Exponentialzeit Hypothese (1)
- FMC-QE (1)
- Feature Combination (1)
- Feedback (1)
- Fehlende Daten (1)
- Fehlerschätzung (1)
- Flussgesteuerter Bilateraler Filter (1)
- Focus+Context Visualization (1)
- Fokus-&-Kontext Visualisierung (1)
- Formalismus (1)
- Formalitätsgrad (1)
- Formeln der quantifizierten Aussagenlogik (1)
- GIS-Dienstkomposition (1)
- GPU (1)
- Gebäudemodelle (1)
- Gehirn-Computer-Schnittstelle (1)
- Geländemodelle (1)
- Generalisierung (1)
- Geodaten (1)
- Geometrieerzeugung (1)
- Geovisualisierung (1)
- Geräte-Treiber (1)
- Geschäftsprozessmodelle (1)
- Gesichtsausdruck (1)
- Globus (1)
- Grid (1)
- Grid Computing (1)
- Hardware Design (1)
- Hauptkomponentenanalyse (1)
- High-Level Synthesis (1)
- Hochschulsystem (1)
- I/O-effiziente Algorithmen (1)
- IP core (1)
- IT security (1)
- IT-Security (1)
- IT-Sicherheit (1)
- Informatik (1)
- Informatik-Studiengänge (1)
- Informatikvoraussetzungen (1)
- Information Transfer Rate (1)
- Inkonsistenz (1)
- Interactive Rendering (1)
- Interaktionsmodel (1)
- Interaktionsmodellierung (1)
- Interaktives Rendering (1)
- Internet Security (1)
- Internet applications (1)
- Internet of Things (1)
- Internet-Sicherheit (1)
- Internetanwendungen (1)
- Interoperability (1)
- Interoperabilität (1)
- IoT (1)
- Java Security Framework (1)
- Kartografisches Design (1)
- Kern-PCA (1)
- Kernmethoden (1)
- Klassifikation (1)
- Klassifikation mit großem Margin (1)
- Klassifikator-Kalibrierung (1)
- Klimafolgenanalyse (1)
- Klimawandel (1)
- Kommunikation (1)
- Kompilation (1)
- Komplexität (1)
- Komplexitätsbewältigung (1)
- Komplexitätstheorie (1)
- Komposition (1)
- Kybernetik (1)
- Landmarken (1)
- Large Margin Classification (1)
- Laser Cutten (1)
- Lehrer (1)
- Leistungsfähigkeit (1)
- Leistungsvorhersage (1)
- Linux (1)
- Linux device drivers (1)
- Logik (1)
- Logiksynthese (1)
- Lower Bounds (1)
- MEG (1)
- MQTT (1)
- Magnetoencephalographie (1)
- Malware (1)
- Mathematical Optimization (1)
- Mathematikdidaktik (1)
- Mathematikphilosophie (1)
- Mathematische Optimierung (1)
- Matrizen-Eigenwertaufgabe (1)
- Megamodel (1)
- Megamodell (1)
- Mehrklassen-Klassifikation (1)
- Mensch-Computer-Interaktion (1)
- Message Passing Interface (1)
- Migration (1)
- Mischmodelle (1)
- Mischung <Signalverarbeitung> (1)
- Mobilgeräte (1)
- Model Management (1)
- Model-Driven Engineering (1)
- Modeling (1)
- Modell Management (1)
- Modell-driven Security (1)
- Modell-getriebene Sicherheit (1)
- Modellgetriebene Entwicklung (1)
- Modellierung (1)
- Molekulare Bioinformatik (1)
- Multi Task Learning (1)
- Multi-Class (1)
- Multi-Task-Lernen (1)
- Multiprocessor (1)
- Multiprozessor (1)
- NETCONF (1)
- Network Management (1)
- Netzwerk Management (1)
- Netzwerke (1)
- Neuronales Netz (1)
- Next Generation Network (1)
- Nicht-photorealistisches Rendering (1)
- Nichtfotorealistische Bildsynthese (1)
- Nutzungsinteresse (1)
- Objektive Schwierigkeit (1)
- Ontologien (1)
- Ontologies (1)
- Ontology (1)
- Optimierungsproblem (1)
- Owner-Retained Access Control (ORAC) (1)
- Parallel Programming (1)
- Paralleles Rechnen (1)
- Parallelrechner (1)
- Parameterized Complexity (1)
- Parametrisierte Komplexität (1)
- Peer-to-Peer-Netz ; GRID computing ; Zuverlässigkeit ; Web Services ; Betriebsmittelverwaltung ; Migration (1)
- Performance (1)
- Performance Prediction (1)
- Platzierung (1)
- Policy Enforcement (1)
- Policy Languages (1)
- Policy Sprachen (1)
- Power Monitoring (1)
- Prediction Game (1)
- Predictive Models (1)
- Probleme in der Studie (1)
- Process (1)
- Process modeling (1)
- Professoren (1)
- Programmierung (1)
- Proof Theory (1)
- Prozess (1)
- Prozesse (1)
- Prozessmodellierung (1)
- Prozesssynchronisierung (1)
- Prädiktionsspiel (1)
- Präferenzen (1)
- Quantified Boolean Formula (QBF) (1)
- Quantitative Modeling (1)
- Quantitative Modellierung (1)
- Queuing Theory (1)
- Reconfigurable (1)
- Regression (1)
- Regularisierung (1)
- Regularization (1)
- Rekonfiguration (1)
- Reparatur (1)
- SMT (SAT Modulo Theories) (1)
- SOA Security Pattern (1)
- STG decomposition (1)
- STG-Dekomposition (1)
- Sample Selection Bias (1)
- Satisfiability (1)
- Scalability (1)
- Schulmaterial (1)
- Security Modelling (1)
- Segmentierung (1)
- Selektionsbias (1)
- Semantic Search (1)
- Semantik Web (1)
- Semantische Suche (1)
- Sensornetzwerke (1)
- Service Creation (1)
- Service Delivery Platform (1)
- Service convergence (1)
- Service-Orientierte Architekturen (1)
- Service-oriented Architectures (1)
- Sicherheitsmodellierung (1)
- Signal Processing (1)
- Signalquellentrennung (1)
- Signaltrennung (1)
- Simultane Diagonalisierung (1)
- Single Event Transient (1)
- Single Trial Analysis (1)
- Skalierbarkeit (1)
- Skelettberechnung (1)
- Software-basierte Cache-Kohärenz (1)
- Sonnenteilchen-Ereignis (1)
- Spam (1)
- Spam Filtering (1)
- Spam-Erkennung (1)
- Spam-Filter (1)
- Spam-Filtering (1)
- Spatio-Spectral Filter (1)
- Spawning (1)
- Sprachdesign (1)
- Statistical Tests (1)
- Statistische Tests (1)
- Stilisierung (1)
- Strahlungshartes Design (1)
- Strahlungshärte Entwurf (1)
- Stromverbrauchüberwachung (1)
- Structuring (1)
- Strukturierung (1)
- Studentenerwartungen (1)
- Studentenhaltungen (1)
- Support Vectors (1)
- Support-Vector Lernen (1)
- System Biologie (1)
- Systembiologie (1)
- Taktik (1)
- Telekommunikation (1)
- Temporal Logic (1)
- Temporallogik (1)
- Temporäre Anbindung (1)
- Terminologische Logik (1)
- Texturen (1)
- Theoretischen Vorlesungen (1)
- Time Augmented Petri Nets (1)
- Time Series Analysis (1)
- Traceability (1)
- Tracking (1)
- Transformation (1)
- Treewidth (1)
- Unabhängige Komponentenanalyse (1)
- Universität Bagdad (1)
- Universität Potsdam (1)
- Universitätseinstellungen (1)
- Untere Schranken (1)
- Unterrichtswerkzeuge (1)
- Unvollständigkeit (1)
- Usage Interest (1)
- VM (1)
- Verhalten (1)
- Verifikation (1)
- Verletzung Auflösung (1)
- Verletzung Erklärung (1)
- Verteiltes Rechnen (1)
- Verteilungsunterschied (1)
- Violation Explanation (1)
- Violation Resolution (1)
- Visualisierung (1)
- Vorhersagemodelle (1)
- Wahrnehmung (1)
- Wahrnehmung von Arousal (1)
- Wahrnehmungsunterschiede (1)
- Warteschlangentheorie (1)
- Web Services (1)
- Web Sites (1)
- Web of Data (1)
- Webseite (1)
- Well-structuredness (1)
- Wetterextreme (1)
- Wirtschaftsinformatik (1)
- Wissenschaftlichesworkflows (1)
- Wissensrepräsentation und -verarbeitung (1)
- Wissensrepräsentation und Schlussfolgerung (1)
- Wohlstrukturiertheit (1)
- ZQSA (1)
- ZQSAT (1)
- Zeitbehaftete Petri Netze (1)
- Zero-Suppressed Binary Decision Diagram (ZDD) (1)
- Zuverlässigkeitsanalyse (1)
- abstraction (1)
- adaptiv (1)
- adaptive (1)
- algorithm configuration (1)
- algorithm scheduling (1)
- algorithm selection (1)
- anisotropic Kuwahara filter (1)
- approximate joint diagonalization (1)
- argumentation (1)
- arousal perception (1)
- artificial intelligence (1)
- assistive Technologien (1)
- assistive technologies (1)
- asynchronous circuit (1)
- bild (1)
- biometrics (1)
- biometrische Identifikation (1)
- blind source separation (1)
- building models (1)
- business informatics (1)
- cartographic design (1)
- changing the study field (1)
- changing the university (1)
- choreographies (1)
- classifier calibration (1)
- classroom material (1)
- climate change (1)
- climate impact analysis (1)
- clustering (1)
- coherence-enhancing filtering (1)
- communication (1)
- compilation (1)
- complexity (1)
- computational biology (1)
- computational methods (1)
- computer graphics (1)
- computer science education (1)
- computer security (1)
- computergestützte Methoden (1)
- concurrent checking (1)
- constraints (1)
- decision trees (1)
- degree of formality (1)
- design principles (1)
- didaktische Rekonstruktion (1)
- difference of Gaussians (1)
- digital circuit (1)
- digital design (1)
- dropout (1)
- dynamic (1)
- dynamic classification (1)
- dynamic reconfiguration (1)
- dynamisch (1)
- dynamische Klassifikation (1)
- e-Learning (1)
- educational reconstruction (1)
- eingebettete Systeme (1)
- einseitige Kommunikation (1)
- email spam detection (1)
- embedded systems (1)
- emotion (1)
- emotion representation (1)
- emotion research (1)
- entity alignment (1)
- evidence theory (1)
- external memory algorithms (1)
- eye movements (1)
- face tracking (1)
- facial expression (1)
- flow-based bilateral filter (1)
- formalism (1)
- generalization (1)
- geometry generation (1)
- geospatial data (1)
- geospatial services (1)
- geovisualization (1)
- graph clustering (1)
- hardware design (1)
- higher education (1)
- human computer interaction (1)
- hybrid (1)
- hybrides Problemlösen (1)
- image (1)
- image data analysis (1)
- image processing (1)
- incompleteness (1)
- inconsistency (1)
- independent component analysis (1)
- indirect economic impacts (1)
- indirekte ökonomische Effekte (1)
- informatische Bildung im Sekundarbereich (1)
- input accuracy (1)
- interaction modeling (1)
- kernel PCA (1)
- kernel methods (1)
- konvergente Dienste (1)
- landmarks (1)
- language design (1)
- logic (1)
- logic programming (1)
- logic synthesis (1)
- logical signaling networks (1)
- logische Programmierung (1)
- logische Signalnetzwerke (1)
- macro-economic modelling (1)
- makroökonomische Modellierung (1)
- malware detection (1)
- map/reduce (1)
- maschninelles Lernen (1)
- mathematics education (1)
- medical (1)
- medizinisch (1)
- middleware (1)
- mixture models (1)
- mobile devices (1)
- molecular networks (1)
- molekulare Netzwerke (1)
- multi-class classification (1)
- networks-on-chip (1)
- nichtlineare ICA (1)
- nichtlineare PCA (NLPCA) (1)
- nonlinear ICA (1)
- nonlinear PCA (NLPCA) (1)
- objective difficulty (1)
- one-sided communication (1)
- oneM2M (1)
- online assistance (1)
- ontologies (1)
- outlier detection (1)
- output space compaction (1)
- overcomplete ICA (1)
- parallel programming (1)
- parallel solving (1)
- parallele Programmierung (1)
- paralleles Lösen (1)
- pattern recognition (1)
- perception (1)
- perception differences (1)
- philosophy of mathematics (1)
- physical Computing (1)
- physical computing (1)
- placement (1)
- prediction (1)
- preferences (1)
- priorities (1)
- probabilistic deep learning (1)
- probabilistic deep metric learning (1)
- probabilistische tiefe neuronale Netze (1)
- probabilistisches tiefes metrisches Lernen (1)
- process (1)
- process synchronization (1)
- professors (1)
- proof (1)
- proof assistant (1)
- proof environment (1)
- propagation probability (1)
- radiation hardness (1)
- radiation hardness design (1)
- reconfiguration (1)
- rekonfigurierbar (1)
- reliability assessment (1)
- repair (1)
- robust ICA (1)
- robuste ICA (1)
- scheduling (1)
- scientific workflows (1)
- secondary computer science education (1)
- segmentation (1)
- selbstanpassendes Multiprozessorsystem (1)
- self-adaptive multiprocessing system (1)
- semantic domain modeling (1)
- semantische Domänenmodellierung (1)
- service composition (1)
- sign language (1)
- single event upset (1)
- skeletonization (1)
- software-based cache coherence (1)
- solar particle event (1)
- speed independence (1)
- strahleninduzierte Einzelereignis-Effekte (1)
- structured output prediction (1)
- strukturierte Vorhersage (1)
- study problems (1)
- stylization (1)
- synthesis (1)
- tactic (1)
- teachers (1)
- temporary binding (1)
- terrain models (1)
- test (1)
- textures (1)
- tools for teaching (1)
- topics (1)
- touch input (1)
- transformation (1)
- tutorial section (1)
- user interfaces (1)
- verification (1)
- virtual 3D city models (1)
- virtual machine (1)
- virtuelle 3D-Stadtmodelle (1)
- visualization (1)
- weather extremes (1)
- zero-aliasing (1)
- überbestimmte ICA (1)
Independent component analysis (ICA) is a tool for statistical data analysis and signal processing that is able to decompose multivariate signals into their underlying source components. Although the classical ICA model is highly useful, there are many real-world applications that require powerful extensions of ICA. This thesis presents new methods that extend the functionality of ICA: (1) reliability and grouping of independent components with noise injection, (2) robust and overcomplete ICA with inlier detection, and (3) nonlinear ICA with kernel methods.
In recent years, there has been a dramatic increase in available compute capacities. However, these “Grid resources” are rarely accessible in a continuous stream, but rather appear scattered across various machine types, platforms and operating systems, which are coupled by networks of fluctuating bandwidth. It becomes increasingly difficult for scientists to exploit available resources for their applications. We believe that intelligent, self-governing applications should be able to select resources in a dynamic and heterogeneous environment: Migrating applications determine a resource when old capacities are used up. Spawning simulations launch algorithms on external machines to speed up the main execution. Applications are restarted as soon as a failure is detected. All these actions can be taken without human interaction. A distributed compute environment possesses an intrinsic unreliability. Any application that interacts with such an environment must be able to cope with its failing components: deteriorating networks, crashing machines, failing software. We construct a reliable service infrastructure by endowing a service environment with a peer-to-peer topology. This “Grid Peer Services” infrastructure accommodates high-level services like migration and spawning, as well as fundamental services for application launching, file transfer and resource selection. It utilizes existing Grid technology wherever possible to accomplish its tasks. An Application Information Server acts as a generic information registry to all participants in a service environment. The service environment that we developed, allows applications e.g. to send a relocation requests to a migration server. The server selects a new computer based on the transmitted resource requirements. It transfers the application's checkpoint and binary to the new host and resumes the simulation. Although the Grid's underlying resource substrate is not continuous, we achieve persistent computations on Grids by relocating the application. We show with our real-world examples that a traditional genome analysis program can be easily modified to perform self-determined migrations in this service environment.
In order to face the rapidly increasing need for computational resources of various scientific and engineering applications one has to think of new ways to make more efficient use of the worlds current computational resources. In this respect, the growing speed of wide area networks made a new kind of distributed computing possible: Metacomputing or (distributed) Grid computing. This is a rather new and uncharted field in computational science. The rapidly increasing speed of networks even outperforms the average increase of processor speed: Processor speeds double on average each 18 month whereas network bandwidths double every 9 months. Due to this development of local and wide area networks Grid computing will certainly play a key role in the future of parallel computing. This type of distributed computing, however, distinguishes from the traditional parallel computing in many ways since it has to deal with many problems not occurring in classical parallel computing. Those problems are for example heterogeneity, authentication and slow networks to mention only a few. Some of those problems, e.g. the allocation of distributed resources along with the providing of information about these resources to the application have been already attacked by the Globus software. Unfortunately, as far as we know, hardly any application or middle-ware software takes advantage of this information, since most parallelizing algorithms for finite differencing codes are implicitly designed for single supercomputer or cluster execution. We show that although it is possible to apply classical parallelizing algorithms in a Grid environment, in most cases the observed efficiency of the executed code is very poor. In this work we are closing this gap. In our thesis, we will - show that an execution of classical parallel codes in Grid environments is possible but very slow - analyze this situation of bad performance, nail down bottlenecks in communication, remove unnecessary overhead and other reasons for low performance - develop new and advanced algorithms for parallelisation that are aware of a Grid environment in order to generelize the traditional parallelization schemes - implement and test these new methods, replace and compare with the classical ones - introduce dynamic strategies that automatically adapt the running code to the nature of the underlying Grid environment. The higher the performance one can achieve for a single application by manual tuning for a Grid environment, the lower the chance that those changes are widely applicable to other programs. In our analysis as well as in our implementation we tried to keep the balance between high performance and generality. None of our changes directly affect code on the application level which makes our algorithms applicable to a whole class of real world applications. The implementation of our work is done within the Cactus framework using the Globus toolkit, since we think that these are the most reliable and advanced programming frameworks for supporting computations in Grid environments. On the other hand, however, we tried to be as general as possible, i.e. all methods and algorithms discussed in this thesis are independent of Cactus or Globus.
In this work we consider statistical learning problems. A learning machine aims to extract information from a set of training examples such that it is able to predict the associated label on unseen examples. We consider the case where the resulting classification or regression rule is a combination of simple rules - also called base hypotheses. The so-called boosting algorithms iteratively find a weighted linear combination of base hypotheses that predict well on unseen data. We address the following issues: o The statistical learning theory framework for analyzing boosting methods. We study learning theoretic guarantees on the prediction performance on unseen examples. Recently, large margin classification techniques emerged as a practical result of the theory of generalization, in particular Boosting and Support Vector Machines. A large margin implies a good generalization performance. Hence, we analyze how large the margins in boosting are and find an improved algorithm that is able to generate the maximum margin solution. o How can boosting methods be related to mathematical optimization techniques? To analyze the properties of the resulting classification or regression rule, it is of high importance to understand whether and under which conditions boosting converges. We show that boosting can be used to solve large scale constrained optimization problems, whose solutions are well characterizable. To show this, we relate boosting methods to methods known from mathematical optimization, and derive convergence guarantees for a quite general family of boosting algorithms. o How to make Boosting noise robust? One of the problems of current boosting techniques is that they are sensitive to noise in the training sample. In order to make boosting robust, we transfer the soft margin idea from support vector learning to boosting. We develop theoretically motivated regularized algorithms that exhibit a high noise robustness. o How to adapt boosting to regression problems? Boosting methods are originally designed for classification problems. To extend the boosting idea to regression problems, we use the previous convergence results and relations to semi-infinite programming to design boosting-like algorithms for regression problems. We show that these leveraging algorithms have desirable theoretical and practical properties. o Can boosting techniques be useful in practice? The presented theoretical results are guided by simulation results either to illustrate properties of the proposed algorithms or to show that they work well in practice. We report on successful applications in a non-intrusive power monitoring system, chaotic time series analysis and a drug discovery process. --- Anmerkung: Der Autor ist Träger des von der Mathematisch-Naturwissenschaftlichen Fakultät der Universität Potsdam vergebenen Michelson-Preises für die beste Promotion des Jahres 2001/2002.
The objective of this thesis is to provide new space compaction techniques for testing or concurrent checking of digital circuits. In particular, the work focuses on the design of space compactors that achieve high compaction ratio and minimal loss of testability of the circuits. In the first part, the compactors are designed for combinational circuits based on the knowledge of the circuit structure. Several algorithms for analyzing circuit structures are introduced and discussed for the first time. The complexity of each design procedure is linear with respect to the number of gates of the circuit. Thus, the procedures are applicable to large circuits. In the second part, the first structural approach for output compaction for sequential circuits is introduced. Essentially, it enhances the first part. For the approach introduced in the third part it is assumed that the structure of the circuit and the underlying fault model are unknown. The space compaction approach requires only the knowledge of the fault-free test responses for a precomputed test set. The proposed compactor design guarantees zero-aliasing with respect to the precomputed test set.