TY - JOUR A1 - Abdelwahab, Ahmed A1 - Landwehr, Niels T1 - Deep Distributional Sequence Embeddings Based on a Wasserstein Loss JF - Neural processing letters N2 - Deep metric learning employs deep neural networks to embed instances into a metric space such that distances between instances of the same class are small and distances between instances from different classes are large. In most existing deep metric learning techniques, the embedding of an instance is given by a feature vector produced by a deep neural network and Euclidean distance or cosine similarity defines distances between these vectors. This paper studies deep distributional embeddings of sequences, where the embedding of a sequence is given by the distribution of learned deep features across the sequence. The motivation for this is to better capture statistical information about the distribution of patterns within the sequence in the embedding. When embeddings are distributions rather than vectors, measuring distances between embeddings involves comparing their respective distributions. The paper therefore proposes a distance metric based on Wasserstein distances between the distributions and a corresponding loss function for metric learning, which leads to a novel end-to-end trainable embedding model. We empirically observe that distributional embeddings outperform standard vector embeddings and that training with the proposed Wasserstein metric outperforms training with other distance functions. KW - Metric learning KW - Sequence embeddings KW - Deep learning Y1 - 2022 U6 - https://doi.org/10.1007/s11063-022-10784-y SN - 1370-4621 SN - 1573-773X PB - Springer CY - Dordrecht ER - TY - JOUR A1 - Abke, Jörg A1 - Schwirtlich, Vincent A1 - Sedelmaier, Yvonne T1 - Kompetenzförderung im Software Engineering durch ein mehrstufiges Lehrkonzept im Studiengang Mechatronik JF - Commentarii informaticae didacticae : (CID) N2 - Dieser Beitrag stellt das Lehr-Lern-Konzept zur Kompetenzförderung im Software Engineering im Studiengang Mechatronik der Hochschule Aschaffenburg dar. Dieses Konzept ist mehrstufig mit Vorlesungs-, Seminar- und Projektsequenzen. Dabei werden Herausforderungen und Verbesserungspotentiale identifiziert und dargestellt. Abschließend wird ein Überblick gegeben, wie im Rahmen eines gerade gestarteten Forschungsprojektes Lehr-Lernkonzepte weiterentwickelt werden können. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64899 SN - 1868-0844 SN - 2191-1940 IS - 5 SP - 79 EP - 84 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - AbuJarour, Mohammed T1 - Information integration in services computing Y1 - 2010 SN - 978-3-86956-036-6 ER - TY - JOUR A1 - Afantenos, Stergos A1 - Peldszus, Andreas A1 - Stede, Manfred T1 - Comparing decoding mechanisms for parsing argumentative structures JF - Argument & Computation N2 - Parsing of argumentative structures has become a very active line of research in recent years. Like discourse parsing or any other natural language task that requires prediction of linguistic structures, most approaches choose to learn a local model and then perform global decoding over the local probability distributions, often imposing constraints that are specific to the task at hand. Specifically for argumentation parsing, two decoding approaches have been recently proposed: Minimum Spanning Trees (MST) and Integer Linear Programming (ILP), following similar trends in discourse parsing. In contrast to discourse parsing though, where trees are not always used as underlying annotation schemes, argumentation structures so far have always been represented with trees. Using the ‘argumentative microtext corpus’ [in: Argumentation and Reasoned Action: Proceedings of the 1st European Conference on Argumentation, Lisbon 2015 / Vol. 2, College Publications, London, 2016, pp. 801–815] as underlying data and replicating three different decoding mechanisms, in this paper we propose a novel ILP decoder and an extension to our earlier MST work, and then thoroughly compare the approaches. The result is that our new decoder outperforms related work in important respects, and that in general, ILP and MST yield very similar performance. KW - Argumentation structure KW - argument mining KW - parsing Y1 - 2018 U6 - https://doi.org/10.3233/AAC-180033 SN - 1946-2166 SN - 1946-2174 VL - 9 IS - 3 SP - 177 EP - 192 PB - IOS Press CY - Amsterdam ER - TY - JOUR A1 - Aguado, Felicidad A1 - Cabalar, Pedro A1 - Fandinno, Jorge A1 - Pearce, David A1 - Perez, Gilberto A1 - Vidal, Concepcion T1 - Forgetting auxiliary atoms in forks JF - Artificial intelligence N2 - In this work we tackle the problem of checking strong equivalence of logic programs that may contain local auxiliary atoms, to be removed from their stable models and to be forbidden in any external context. We call this property projective strong equivalence (PSE). It has been recently proved that not any logic program containing auxiliary atoms can be reformulated, under PSE, as another logic program or formula without them – this is known as strongly persistent forgetting. In this paper, we introduce a conservative extension of Equilibrium Logic and its monotonic basis, the logic of Here-and-There, in which we deal with a new connective ‘|’ we call fork. We provide a semantic characterisation of PSE for forks and use it to show that, in this extension, it is always possible to forget auxiliary atoms under strong persistence. We further define when the obtained fork is representable as a regular formula. KW - Answer set programming KW - Non-monotonic reasoning KW - Equilibrium logic KW - Denotational semantics KW - Forgetting KW - Strong equivalence Y1 - 2019 U6 - https://doi.org/10.1016/j.artint.2019.07.005 SN - 0004-3702 SN - 1872-7921 VL - 275 SP - 575 EP - 601 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Aguado, Felicidad A1 - Cabalar, Pedro A1 - Fandiño, Jorge A1 - Pearce, David A1 - Perez, Gilberto A1 - Vidal-Peracho, Concepcion T1 - Revisiting Explicit Negation in Answer Set Programming JF - Theory and practice of logic programming KW - Answer set programming KW - Non-monotonic reasoning KW - Equilibrium logic KW - Explicit negation Y1 - 2019 U6 - https://doi.org/10.1017/S1471068419000267 SN - 1471-0684 SN - 1475-3081 VL - 19 IS - 5-6 SP - 908 EP - 924 PB - Cambridge Univ. Press CY - New York ER - TY - JOUR A1 - Ahmad, Nadeem A1 - Shoaib, Umar A1 - Prinetto, Paolo T1 - Usability of Online Assistance From Semiliterate Users' Perspective JF - International journal of human computer interaction Y1 - 2015 U6 - https://doi.org/10.1080/10447318.2014.925772 SN - 1044-7318 SN - 1532-7590 VL - 31 IS - 1 SP - 55 EP - 64 PB - Taylor & Francis Group CY - Philadelphia ER - TY - JOUR A1 - Al Laban, Firas A1 - Reger, Martin A1 - Lucke, Ulrike T1 - Closing the Policy Gap in the Academic Bridge JF - Education sciences N2 - The highly structured nature of the educational sector demands effective policy mechanisms close to the needs of the field. That is why evidence-based policy making, endorsed by the European Commission under Erasmus+ Key Action 3, aims to make an alignment between the domains of policy and practice. Against this background, this article addresses two issues: First, that there is a vertical gap in the translation of higher-level policies to local strategies and regulations. Second, that there is a horizontal gap between educational domains regarding the policy awareness of individual players. This was analyzed in quantitative and qualitative studies with domain experts from the fields of virtual mobility and teacher training. From our findings, we argue that the combination of both gaps puts the academic bridge from secondary to tertiary education at risk, including the associated knowledge proficiency levels. We discuss the role of digitalization in the academic bridge by asking the question: which value does the involved stakeholders expect from educational policies? As a theoretical basis, we rely on the model of value co-creation for and by stakeholders. We describe the used instruments along with the obtained results and proposed benefits. Moreover, we reflect on the methodology applied, and we finally derive recommendations for future academic bridge policies. KW - policy evaluation KW - higher education KW - virtual mobility KW - teacher training Y1 - 2022 U6 - https://doi.org/10.3390/educsci12120930 SN - 2227-7102 VL - 12 IS - 12 PB - MDPI CY - Basel ER - TY - JOUR A1 - Al-Saffar, Loay Talib Ahmed T1 - Where girls take the role of boys in CS BT - attitudes of CS students in a female-dominated environment JF - Commentarii informaticae didacticae : (CID) N2 - A survey has been carried out in the Computer Science (CS) department at the University of Baghdad to investigate the attitudes of CS students in a female dominant environment, showing the differences between male and female students in different academic years. We also compare the attitudes of the freshman students of two different cultures (University of Baghdad, Iraq, and the University of Potsdam). Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-65034 SN - 1868-0844 SN - 2191-1940 IS - 5 SP - 149 EP - 154 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Alnemr, Rehab T1 - Context-aware Reputation in SOA and future internet Y1 - 2010 SN - 978-3-86956-036-6 ER - TY - JOUR A1 - Andjelković, Marko A1 - Chen, Junchao A1 - Simevski, Aleksandar A1 - Schrape, Oliver A1 - Krstić, Miloš A1 - Kraemer, Rolf T1 - Monitoring of particle count rate and LET variations with pulse stretching inverters JF - IEEE transactions on nuclear science : a publication of the IEEE Nuclear and Plasma Sciences Society N2 - This study investigates the use of pulse stretching (skew-sized) inverters for monitoring the variation of count rate and linear energy transfer (LET) of energetic particles. The basic particle detector is a cascade of two pulse stretching inverters, and the required sensing area is obtained by connecting up to 12 two-inverter cells in parallel and employing the required number of parallel arrays. The incident particles are detected as single-event transients (SETs), whereby the SET count rate denotes the particle count rate, while the SET pulsewidth distribution depicts the LET variations. The advantage of the proposed solution is the possibility to sense the LET variations using fully digital processing logic. SPICE simulations conducted on IHP's 130-nm CMOS technology have shown that the SET pulsewidth varies by approximately 550 ps over the LET range from 1 to 100 MeV center dot cm(2) center dot mg(-1). The proposed detector is intended for triggering the fault-tolerant mechanisms within a self-adaptive multiprocessing system employed in space. It can be implemented as a standalone detector or integrated in the same chip with the target system. KW - Particle detector KW - pulse stretching inverters KW - single-event transient KW - (SET) count rate KW - SET pulsewidth distribution Y1 - 2021 U6 - https://doi.org/10.1109/TNS.2021.3076400 SN - 0018-9499 SN - 1558-1578 VL - 68 IS - 8 SP - 1772 EP - 1781 PB - Institute of Electrical and Electronics Engineers CY - New York, NY ER - TY - JOUR A1 - Anger, Christian A1 - Gebser, Martin A1 - Janhunen, Tomi A1 - Schaub, Torsten H. T1 - What's a head without a body? Y1 - 2006 ER - TY - JOUR A1 - Anger, Christian A1 - Gebser, Martin A1 - Linke, Thomas A1 - Neumann, Andre A1 - Schaub, Torsten H. T1 - The nomore++ approach to answer set solving Y1 - 2005 UR - http://www.cs.uni-potsdam.de/wv/pdfformat/angelinesc05c.pdf ER - TY - JOUR A1 - Anger, Christian A1 - Gebser, Martin A1 - Linke, Thomas A1 - Neumann, Andre A1 - Schaub, Torsten H. T1 - The nomore++ approach to answer set solving Y1 - 2005 UR - http://www.cs.uni-potsdam.de/wv/pdfformat/angelinesc05c.pdf ER - TY - JOUR A1 - Anger, Christian A1 - Gebser, Martin A1 - Schaub, Torsten H. T1 - Approaching the core of unfounded sets Y1 - 2006 UR - http://www.cs.uni-potsdam.de/wv/pdfformat/angesc06a.pdf ER - TY - JOUR A1 - Anger, Christian A1 - Konczak, Kathrin A1 - Linke, Thomas T1 - NoMoRe: A system for non-monotonic reasoning with logic programs under answer set semantics Y1 - 2002 SN - 3-540-42254-4 ER - TY - JOUR A1 - Anger, Christian A1 - Konczak, Kathrin A1 - Linke, Thomas T1 - NoMoRe: Non-monotonic reasoning with logic programs Y1 - 2002 SN - 3-540-44190-5 ER - TY - JOUR A1 - Anger, Christian A1 - Konczak, Kathrin A1 - Linke, Thomas T1 - A system for non-monotonic reasoning under answer set semantics Y1 - 2001 SN - 3-540-42593-4 ER - TY - JOUR A1 - Anger, Christian A1 - Konczak, Kathrin A1 - Linke, Thomas A1 - Schaub, Torsten H. T1 - A Glimpse of Answer Set Programming Y1 - 2005 UR - http://www.cs.uni-potsdam.de/~konczak/Papers/ankolisc05.pdf SN - 0170-4516 ER - TY - JOUR A1 - Apel, Rebecca A1 - Berg, Tobias A1 - Bergner, Nadine A1 - Chatti, Mhamed Amine A1 - Holz, Jan A1 - Leicht-Scholten, Carmen A1 - Schroeder, Ulrike T1 - Ein vierstufiges Förderkonzept für die Studieneingangsphase in der Informatik JF - Commentarii informaticae didacticae : (CID) N2 - Es wird ein vierstufiges Förderkonzept für die Studieneingangsphase im Fach Informatik beschrieben, das derzeit im Rahmen des Projekts IGaDtools4MINT an der RWTH Aachen auf der Basis einer Literaturanalyse und eines daraus abgeleiteten Indikatorenkatalogs entwickelt wird. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-65025 SN - 1868-0844 SN - 2191-1940 IS - 5 SP - 143 EP - 148 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Appeltauer, Malte T1 - declarative and event-based context-oriented programming Y1 - 2010 SN - 978-3-86956-036-6 ER - TY - JOUR A1 - Arnold, Holger T1 - A linearized DPLL calculus with learning N2 - This paper describes the proof calculus LD for clausal propositional logic, which is a linearized form of the well-known DPLL calculus extended by clause learning. It is motivated by the demand to model how current SAT solvers built on clause learning are working, while abstracting from decision heuristics and implementation details. The calculus is proved sound and terminating. Further, it is shown that both the original DPLL calculus and the conflict-directed backtracking calculus with clause learning, as it is implemented in many current SAT solvers, are complete and proof-confluent instances of the LD calculus. N2 - Dieser Artikel beschreibt den Beweiskalkül LD für aussagenlogische Formeln in Klauselform. Dieser Kalkül ist eine um Klausellernen erweiterte linearisierte Variante des bekannten DPLL-Kalküls. Er soll dazu dienen, das Verhalten von auf Klausellernen basierenden SAT-Beweisern zu modellieren, wobei von Entscheidungsheuristiken und Implementierungsdetails abstrahiert werden soll. Es werden Korrektheit und Terminierung des Kalküls bewiesen. Weiterhin wird gezeigt, dass sowohl der ursprüngliche DPLL-Kalkül als auch der konfliktgesteuerte Rücksetzalgorithmus mit Klausellernen, wie er in vielen aktuellen SAT-Beweisern implementiert ist, vollständige und beweiskonfluente Spezialisierungen des LD-Kalküls sind. KW - SAT KW - DPLL KW - Klausellernen KW - Automatisches Beweisen KW - SAT KW - DPLL KW - Clause Learning KW - Automated Theorem Proving Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-15421 ER - TY - JOUR A1 - Arrighi, Pablo A1 - Nesme, Vincent A1 - Werner, Reinhard F. T1 - One-Dimensional quantum cellular automata JF - International journal of unconventional computing : non-classical computation and cellular automata N2 - We define and study quantum cellular automata (QCA). We show that they are reversible and that the neighborhood of the inverse is the opposite of the neighborhood. We also show that QCA always admit, modulo shifts, a two-layered block representation. Note that the same two-layered block representation result applies also over infinite configurations, as was previously shown for one-dimensional systems in the more elaborate formalism of operators algebras [18]. Here the proof is simpler and self-contained, moreover we discuss a counterexample QCA in higher dimensions. KW - cellular automata KW - quantum KW - neighborhood KW - block representation Y1 - 2011 SN - 1548-7199 VL - 7 IS - 4 SP - 223 EP - 244 PB - Old City Publishing Science CY - Philadelphia ER - TY - JOUR A1 - Baedke, Jan A1 - Schöttler, Tobias T1 - Visual Metaphors in the Sciences BT - the Case of Epigenetic Landscape Images JF - Journal for General Philosophy of Science N2 - Recent philosophical analyses of the epistemic dimension of images in the sciences show a certain trend in acknowledging potential roles of these images beyond their merely decorative or pedagogical functions. We argue, however, that this new debate has yet paid little attention to a special type of pictures, we call ‘visual metaphor’, and its versatile heuristic potential in organizing data, supporting communication, and guiding research, modeling, and theory formation. Based on a case study of Conrad Hal Waddington’s epigenetic landscape images in biology, we develop a descriptive framework applicable to heuristic roles of various visual metaphors in the sciences. KW - Conrad Hal Waddington KW - Epigenetic landscape KW - Modelling KW - Scientific images KW - Theory formation KW - Visual metaphor Y1 - 2017 U6 - https://doi.org/10.1007/s10838-016-9353-9 SN - 0925-4560 SN - 1572-8587 VL - 48 SP - 173 EP - 194 PB - Springer CY - Dordrecht ER - TY - JOUR A1 - Baier, Thomas A1 - Di Ciccio, Claudio A1 - Mendling, Jan A1 - Weske, Mathias T1 - Matching events and activities by integrating behavioral aspects and label analysis JF - Software and systems modeling N2 - Nowadays, business processes are increasingly supported by IT services that produce massive amounts of event data during the execution of a process. These event data can be used to analyze the process using process mining techniques to discover the real process, measure conformance to a given process model, or to enhance existing models with performance information. Mapping the produced events to activities of a given process model is essential for conformance checking, annotation and understanding of process mining results. In order to accomplish this mapping with low manual effort, we developed a semi-automatic approach that maps events to activities using insights from behavioral analysis and label analysis. The approach extracts Declare constraints from both the log and the model to build matching constraints to efficiently reduce the number of possible mappings. These mappings are further reduced using techniques from natural language processing, which allow for a matching based on labels and external knowledge sources. The evaluation with synthetic and real-life data demonstrates the effectiveness of the approach and its robustness toward non-conforming execution logs. KW - Process mining KW - Event mapping KW - Business process intelligence KW - Constraint satisfaction KW - Declare KW - Natural language processing Y1 - 2018 U6 - https://doi.org/10.1007/s10270-017-0603-z SN - 1619-1366 SN - 1619-1374 VL - 17 IS - 2 SP - 573 EP - 598 PB - Springer CY - Heidelberg ER - TY - JOUR A1 - Baier, Thomas A1 - Mendling, Jan A1 - Weske, Mathias T1 - Bridging abstraction layers in process mining JF - Information systems N2 - While the maturity of process mining algorithms increases and more process mining tools enter the market, process mining projects still face the problem of different levels of abstraction when comparing events with modeled business activities. Current approaches for event log abstraction try to abstract from the events in an automated way that does not capture the required domain knowledge to fit business activities. This can lead to misinterpretation of discovered process models. We developed an approach that aims to abstract an event log to the same abstraction level that is needed by the business. We use domain knowledge extracted from existing process documentation to semi-automatically match events and activities. Our abstraction approach is able to deal with n:m relations between events and activities and also supports concurrency. We evaluated our approach in two case studies with a German IT outsourcing company. (C) 2014 Elsevier Ltd. All rights reserved. KW - Process mining KW - Abstraction KW - Event mapping Y1 - 2014 U6 - https://doi.org/10.1016/j.is.2014.04.004 SN - 0306-4379 SN - 1873-6076 VL - 46 SP - 123 EP - 139 PB - Elsevier CY - Oxford ER - TY - JOUR A1 - Bailis, Peter A1 - Dillahunt, Tawanna A1 - Müller, Stefanie A1 - Baudisch, Patrick T1 - Research for Practice: Technology for Underserved Communities; Personal Fabrication JF - Communications of the ACM / Association for Computing Machinery N2 - THIS INSTALLMENT OF Research for Practice provides curated reading guides to technology for underserved communities and to new developments in personal fabrication. First, Tawanna Dillahunt describes design considerations and technology for underserved and impoverished communities. Designing for the more than 1.6 billion impoverished individuals worldwide requires special consideration of community needs, constraints, and context. Her selections span protocols for poor-quality communication networks, community-driven content generation, and resource and public service discovery. Second, Stefanie Mueller and Patrick Baudisch provide an overview of recent advances in personal fabrication (for example, 3D printers). Y1 - 2017 U6 - https://doi.org/10.1145/3080188 SN - 0001-0782 SN - 1557-7317 VL - 60 SP - 46 EP - 49 PB - Association for Computing Machinery CY - New York ER - TY - JOUR A1 - Bakera, Marco A1 - Margaria, Tiziana A1 - Renner, Clemens D. A1 - Steffen, Bernhard T1 - Game-Based model checking for reliable autonomy in space JF - Journal of aerospace computing, information, and communication N2 - Autonomy is an emerging paradigm for the design and implementation of managed services and systems. Self-managed aspects frequently concern the communication of systems with their environment. Self-management subsystems are critical, they should thus be designed and implemented as high-assurance components. Here, we propose to use GEAR, a game-based model checker for the full modal mu-calculus, and derived, more user-oriented logics, as a user friendly tool that can offer automatic proofs of critical properties of such systems. Designers and engineers can interactively investigate automatically generated winning strategies resulting from the games, this way exploring the connection between the property, the system, and the proof. The benefits of the approach are illustrated on a case study that concerns the ExoMars Rover. Y1 - 2011 U6 - https://doi.org/10.2514/1.32013 SN - 1940-3151 VL - 8 IS - 4 SP - 100 EP - 114 PB - American Institute of Aeronautics and Astronautics CY - Reston ER - TY - JOUR A1 - Banbara, Mutsunori A1 - Inoue, Katsumi A1 - Kaufmann, Benjamin A1 - Okimoto, Tenda A1 - Schaub, Torsten H. A1 - Soh, Takehide A1 - Tamura, Naoyuki A1 - Wanko, Philipp T1 - teaspoon BT - solving the curriculum-based course timetabling problems with answer set programming JF - Annals of operation research N2 - Answer Set Programming (ASP) is an approach to declarative problem solving, combining a rich yet simple modeling language with high performance solving capacities. We here develop an ASP-based approach to curriculum-based course timetabling (CB-CTT), one of the most widely studied course timetabling problems. The resulting teaspoon system reads a CB-CTT instance of a standard input format and converts it into a set of ASP facts. In turn, these facts are combined with a first-order encoding for CB-CTT solving, which can subsequently be solved by any off-the-shelf ASP systems. We establish the competitiveness of our approach by empirically contrasting it to the best known bounds obtained so far via dedicated implementations. Furthermore, we extend the teaspoon system to multi-objective course timetabling and consider minimal perturbation problems. KW - Educational timetabling KW - Course timetabling KW - Answer set programming KW - Multi-objective optimization KW - Minimal perturbation problems Y1 - 2018 U6 - https://doi.org/10.1007/s10479-018-2757-7 SN - 0254-5330 SN - 1572-9338 VL - 275 IS - 1 SP - 3 EP - 37 PB - Springer CY - Dordrecht ER - TY - JOUR A1 - Banbara, Mutsunori A1 - Soh, Takehide A1 - Tamura, Naoyuki A1 - Inoue, Katsumi A1 - Schaub, Torsten H. T1 - Answer set programming as a modeling language for course timetabling JF - Theory and practice of logic programming N2 - The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds. KW - answer set programming KW - educational timetabling KW - course timetabling Y1 - 2013 U6 - https://doi.org/10.1017/S1471068413000495 SN - 1471-0684 VL - 13 IS - 2 SP - 783 EP - 798 PB - Cambridge Univ. Press CY - New York ER - TY - JOUR A1 - Barnes, Jan A1 - Kennewell, Steve T1 - Teacher Perceptions of Key Competencies in ICT JF - KEYCIT 2014 - Key Competencies in Informatics and ICT N2 - Regardless of what is intended by government curriculum specifications and advised by educational experts, the competencies taught and learned in and out of classrooms can vary considerably. In this paper, we discuss in particular how we can investigate the perceptions that individual teachers have of competencies in ICT, and how these and other factors may influence students’ learning. We report case study research which identifies contradictions within the teaching of ICT competencies as an activity system, highlighting issues concerning the object of the curriculum, the roles of the participants and the school cultures. In a particular case, contradictions in the learning objectives between higher order skills and the use of application tools have been resolved by a change in the teacher’s perceptions which have not led to changes in other aspects of the activity system. We look forward to further investigation of the effects of these contradictions in other case studies and on forthcoming curriculum change. KW - ICT competencies KW - Teacher perceptions KW - Activity Theory KW - Contradictions Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-82604 SN - 1868-0844 SN - 2191-1940 IS - 7 SP - 61 EP - 75 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Bauer, Chris A1 - Herwig, Ralf A1 - Lienhard, Matthias A1 - Prasse, Paul A1 - Scheffer, Tobias A1 - Schuchhardt, Johannes T1 - Large-scale literature mining to assess the relation between anti-cancer drugs and cancer types JF - Journal of translational medicine N2 - Background: There is a huge body of scientific literature describing the relation between tumor types and anti-cancer drugs. The vast amount of scientific literature makes it impossible for researchers and physicians to extract all relevant information manually. Methods: In order to cope with the large amount of literature we applied an automated text mining approach to assess the relations between 30 most frequent cancer types and 270 anti-cancer drugs. We applied two different approaches, a classical text mining based on named entity recognition and an AI-based approach employing word embeddings. The consistency of literature mining results was validated with 3 independent methods: first, using data from FDA approvals, second, using experimentally measured IC-50 cell line data and third, using clinical patient survival data. Results: We demonstrated that the automated text mining was able to successfully assess the relation between cancer types and anti-cancer drugs. All validation methods showed a good correspondence between the results from literature mining and independent confirmatory approaches. The relation between most frequent cancer types and drugs employed for their treatment were visualized in a large heatmap. All results are accessible in an interactive web-based knowledge base using the following link: . Conclusions: Our approach is able to assess the relations between compounds and cancer types in an automated manner. Both, cancer types and compounds could be grouped into different clusters. Researchers can use the interactive knowledge base to inspect the presented results and follow their own research questions, for example the identification of novel indication areas for known drugs. KW - Literature mining KW - Anti-cancer drugs KW - Tumor types KW - Word embeddings KW - Database Y1 - 2021 U6 - https://doi.org/10.1186/s12967-021-02941-z SN - 1479-5876 VL - 19 IS - 1 PB - BioMed Central CY - London ER - TY - JOUR A1 - Beerenwinkel, Niko A1 - Sing, Tobias A1 - Lengauer, Thomas A1 - Rahnenfuhrer, Joerg A1 - Roomp, Kirsten A1 - Savenkov, Igor A1 - Fischer, Roman A1 - Hoffmann, Daniel A1 - Selbig, Joachim A1 - Korn, Klaus A1 - Walter, Hauke A1 - Berg, Thomas A1 - Braun, Patrick A1 - Faetkenheuer, Gerd A1 - Oette, Mark A1 - Rockstroh, Juergen A1 - Kupfer, Bernd A1 - Kaiser, Rolf A1 - Daeumer, Martin T1 - Computational methods for the design of effective therapies against drug resistant HIV strains N2 - The development of drug resistance is a major obstacle to successful treatment of HIV infection. The extraordinary replication dynamics of HIV facilitates its escape from selective pressure exerted by the human immune system and by combination drug therapy. We have developed several computational methods whose combined use can support the design of optimal antiretroviral therapies based on viral genomic data Y1 - 2005 ER - TY - JOUR A1 - Bender, Katrin A1 - Steinert, Markus T1 - Ein handlungsorientiertes, didaktisches Training für Tutoren im Bachelorstudium der Informatik JF - Commentarii informaticae didacticae : (CID) N2 - Die didaktisch-pädagogische Ausbildung studentischer Tutoren für den Einsatz im Bachelorstudium der Informatik ist Gegenstand dieser Arbeit. Um die theoretischen Inhalte aus Sozial- und Lernpsychologie handlungsorientiert und effizient zu vermitteln, wird das Training als Lehrform gewählt. Die in einer Tutorübung zentrale Methode der Gruppenarbeit wird dabei explizit und implizit vermittelt. Erste praktische Erfahrungen mit ihrer zukünftigen Rolle gewinnen die Tutoren in Rollenspielen, wobei sowohl Standardsituationen als auch fachspezifisch und pädagogisch problematische Situationen simuliert werden. Während die Vermittlung der genannten Inhalte und die Rollenspiele im Rahmen einer Blockveranstaltung vor Beginn des Semesters durchgeführt werden, finden während des Semesters Hospitationen statt, in der die Fähigkeiten der Tutoren anhand eines standardisierten Bewertungsbogens beurteilt werden. KW - Informatik KW - Ausbildung KW - Didaktik KW - Hochschuldidaktik Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-29690 SN - 1868-0844 SN - 2191-1940 IS - 1 SP - 119 EP - 130 ER - TY - JOUR A1 - Benhammadi, Farid A1 - Nicolas, Pascal A1 - Schaub, Torsten H. T1 - Extension calculus and query answering in prioritized default logic Y1 - 1998 SN - 3-540-64993-X ER - TY - JOUR A1 - Benhammadi, Farid A1 - Nicolas, Pascal A1 - Schaub, Torsten H. T1 - Extension calculus and query answering in prioritized default logic Y1 - 1998 SN - 3-540- 64993-X ER - TY - JOUR A1 - Benhammadi, Farid A1 - Nicolas, Pascal A1 - Schaub, Torsten H. T1 - Query-answering in prioritized default logic Y1 - 1999 SN - 3-540-66131-X ER - TY - JOUR A1 - Benhammadi, Farid A1 - Nicolas, Pascal A1 - Schaub, Torsten H. T1 - Query-answering in prioritized default logic Y1 - 1999 SN - 3-540-66131-X ER - TY - JOUR A1 - Bensch, Suna A1 - Bordihn, Henning A1 - Holzer, Markus A1 - Kutrib, Martin T1 - On input-revolving deterministic and nondeterministic finite automata N2 - We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular-interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any deterministic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection. Y1 - 2009 UR - http://www.sciencedirect.com/science/journal/08905401 U6 - https://doi.org/10.1016/J.Ic.2009.03.002 SN - 0890-5401 ER - TY - JOUR A1 - Berges, Marc A1 - Hubwieser, Peter T1 - Vorkurse in objektorientierter Programmierung JF - Commentarii informaticae didacticae : (CID) N2 - Die Studienanfänger der Informatik haben in Deutschland sehr unterschiedliche Grundkenntnisse in der Programmierung. Dies führt immer wieder zu Schwierigkeiten in der Ausrichtung der Einführungsveranstaltungen. An der TU München wird seit dem Wintersemester 2008/2009 nun eine neue Art von Vorkursen angeboten. In nur 2,5 Tagen erstellen die Teilnehmer ein kleines objektorientiertes Programm. Dabei arbeiten sie weitestgehend alleine, unterstützt von einem studentischen Tutor. In dieser Arbeit sollen nun das Konzept der sogenannten „Vorprojekte“ sowie erste Forschungsansätze vorgestellt werden Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64299 SN - 1868-0844 SN - 2191-1940 IS - 4 SP - 13 EP - 22 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Berges, Marc A1 - Mühling, Andreas A1 - Hubwieser, Peter A1 - Steuer, Horst T1 - Informatik für Nichtinformatiker BT - ein kontext- und praxisorientiertes Konzept JF - Commentarii informaticae didacticae : (CID) N2 - Wir stellen die Konzeption und erste Ergebnisse einer neuartigen Informatik- Lehrveranstaltung für Studierende der Geodäsie vor. Das Konzept verbindet drei didaktische Ideen: Kontextorientierung, Peer-Tutoring und Praxisbezug (Course). Die Studierenden sollen dabei in zwei Semestern wichtige Grundlagen der Informatik verstehen und anzuwenden lernen. Durch enge Verzahnung der Aufgaben mit einem für Nichtinformatiker relevanten Kontext, sowie einem sehr hohen Anteil von Selbsttätigkeit der Studierenden soll die Motivation für fachfremde Themen gesteigert werden. Die Ergebnisse zeigen, dass die Veranstaltung sehr erfolgreich war. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64962 SN - 1868-0844 SN - 2191-1940 IS - 5 SP - 105 EP - 110 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Bergner, Nadine A1 - Taraschewski, Christian A1 - Schroeder, Ulrik ED - Schubert, Sigrid ED - Schwill, Andreas T1 - Beispiel eines Schülerwettbewerbs zum Thema Projektmanagement und App-Programmierung JF - HDI 2014 : Gestalten von Übergängen N2 - Es wird ein Informatik-Wettbewerb für Schülerinnen und Schüler der Sekundarstufe II beschrieben, der über mehrere Wochen möglichst realitätsnah die Arbeitswelt eines Informatikers vorstellt. Im Wettbewerb erarbeiten die Schülerteams eine Android-App und organisieren ihre Entwicklung durch Projektmanagementmethoden, die sich an professionellen, agilen Prozessen orientieren. Im Beitrag werden der theoretische Hintergrund zu Wettbewerben, die organisatorischen und didaktischen Entscheidung, eine erste Evaluation sowie Reflexion und Ausblick dargestellt. Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-84726 VL - 2015 IS - 9 SP - 161 EP - 168 ER - TY - JOUR A1 - Besnard, Philippe A1 - Fanselow, Gisbert A1 - Schaub, Torsten H. T1 - Optimality theory as a family of cumulative logics Y1 - 2002 ER - TY - JOUR A1 - Besnard, Philippe A1 - Hunter, Anthony T1 - A logic-based theory of deductive arguments Y1 - 2001 SN - 0004-3702 ER - TY - JOUR A1 - Besnard, Philippe A1 - Hunter, Anthony T1 - Towards a logic-based theory of argumentation Y1 - 2000 SN - 0-262-51112-6 ER - TY - JOUR A1 - Besnard, Philippe A1 - Lang, Jerome T1 - Graded paraconsistency Y1 - 2000 SN - 0-86380-253-2 ER - TY - JOUR A1 - Besnard, Philippe A1 - Mercer, Robert E. A1 - Schaub, Torsten H. T1 - Optimality theory throught default logic Y1 - 2003 SN - 3-540-20059-2 ER - TY - JOUR A1 - Besnard, Philippe A1 - Mercer, Robert E. A1 - Schaub, Torsten H. T1 - Optimality Theory via Default Logic Y1 - 2002 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - A simple signed system for paraconsistent reasoning Y1 - 1996 SN - 3-540-61630-6 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - A context-based framework for default logics Y1 - 1993 SN - 0-262-51071-5 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - Signed systems for paraconsistent reasoning Y1 - 1998 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - Characterization of non-monotone non-constructive systems Y1 - 1998 SN - 1012-2443 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - Signed systems for paraconsistent reasoning Y1 - 1998 SN - 0168-7433 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - An approach to context-based default reasoning Y1 - 1995 SN - 0169-2968 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - Circumscribing inconsistency Y1 - 1997 SN - 1-558-60480-4 SN - 1045-0823 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - Significant inferences Y1 - 2000 SN - 1-55860-690-4 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. T1 - What is a (non-constructive) non-monotone logical system? Y1 - 2000 SN - 0304-3975 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. A1 - Tompits, Hans A1 - Woltran, Stefan T1 - Paraconsistent reasoning via quantified boolean formulas Y1 - 2002 SN - 3-540-44190-5 ER - TY - JOUR A1 - Besnard, Philippe A1 - Schaub, Torsten H. A1 - Tompits, Hans A1 - Woltran, Stefan T1 - Paraconsistent reasoning via quantified boolean formulas : Part II: Circumscribing inconsistent theories Y1 - 2003 SN - 3-540- 409494-5 ER - TY - JOUR A1 - Bhattacharya, M. K. A1 - Dimitriev, Alexej A1 - Gössel, Michael T1 - Zero-aliasing space compresion using a single periodic output and its application to testing of embedded Y1 - 2000 ER - TY - JOUR A1 - Bibel, Wolfgang A1 - Brüning, Stefan A1 - Otten, Jens A1 - Rath, Thomas A1 - Schaub, Torsten H. T1 - Compressions and extensions Y1 - 1998 ER - TY - JOUR A1 - Bickel, Steffen A1 - Brueckner, Michael A1 - Scheffer, Tobias T1 - Discriminative learning under covariate shift N2 - We address classification problems for which the training instances are governed by an input distribution that is allowed to differ arbitrarily from the test distribution-problems also referred to as classification under covariate shift. We derive a solution that is purely discriminative: neither training nor test distribution are modeled explicitly. The problem of learning under covariate shift can be written as an integrated optimization problem. Instantiating the general optimization problem leads to a kernel logistic regression and an exponential model classifier for covariate shift. The optimization problem is convex under certain conditions; our findings also clarify the relationship to the known kernel mean matching procedure. We report on experiments on problems of spam filtering, text classification, and landmine detection. Y1 - 2009 UR - http://jmlr.csail.mit.edu/ SN - 1532-4435 ER - TY - JOUR A1 - Bickel, Steffen A1 - Brückner, Michael A1 - Scheffer, Tobias T1 - Discriminative learning under covariate shift N2 - We address classification problems for which the training instances are governed by an input distribution that is allowed to differ arbitrarily from the test distribution-problems also referred to as classification under covariate shift. We derive a solution that is purely discriminative: neither training nor test distribution are modeled explicitly. The problem of learning under covariate shift can be written as an integrated optimization problem. Instantiating the general optimization problem leads to a kernel logistic regression and an exponential model classifier for covariate shift. The optimization problem is convex under certain conditions; our findings also clarify the relationship to the known kernel mean matching procedure. We report on experiments on problems of spam filtering, text classification, and landmine detection. Y1 - 2009 UR - http://jmlr.csail.mit.edu/ SN - 1532-4435 ER - TY - JOUR A1 - Bieniusa, Annette A1 - Degen, Markus A1 - Heidegger, Phillip A1 - Thiemann, Peter A1 - Wehr, Stefan A1 - Gasbichler, Martin A1 - Crestani, Marcus A1 - Klaeren, Herbert A1 - Knauel, Eric A1 - Sperber, Michael T1 - Auf dem Weg zu einer robusten Programmierausbildung JF - Commentarii informaticae didacticae : (CID) N2 - Die gelungene Durchführung einer Vorlesung „Informatik I – Einführung in die Programmierung“ ist schwierig, trotz einer Vielfalt existierender Materialien und erprobter didaktischer Methoden. Gerade aufgrund dieser vielfältigen Auswahl hat sich bisher noch kein robustes Konzept durchgesetzt, das unabhängig von den Durchführenden eine hohe Erfolgsquote garantiert. An den Universitäten Tübingen und Freiburg wurde die Informatik I aus den gleichen Lehrmaterialien und unter ähnlichen Bedingungen durchgeführt, um das verwendete Konzept auf Robustheit zu überprüfen. Die Grundlage der Vorlesung bildet ein systematischer Ansatz zum Erlernen des Programmierens, der von der PLTGruppe in USA entwickelt worden ist. Hinzu kommen neue Ansätze zur Betreuung, insbesondere das Betreute Programmieren, bei dem die Studierenden eine solide Basis für ihre Programmierfähigkeiten entwickeln. Der vorliegende Bericht beschreibt hierbei gesammelte Erfahrungen, erläutert die Entwicklung der Unterrichtsmethodik und der Inhaltsauswahl im Vergleich zu vorangegangenen Vorlesungen und präsentiert Daten zum Erfolg der Vorlesung. KW - Informatik KW - Ausbildung KW - Didaktik KW - Hochschuldidaktik Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-29655 SN - 1868-0844 SN - 2191-1940 IS - 1 SP - 67 EP - 79 ER - TY - JOUR A1 - Blaese, Leif T1 - Data mining for unidentified protein squences JF - Process design for natural scientists: an agile model-driven approach N2 - Through the use of next generation sequencing (NGS) technology, a lot of newly sequenced organisms are now available. Annotating those genes is one of the most challenging tasks in sequence biology. Here, we present an automated workflow to find homologue proteins, annotate sequences according to function and create a three-dimensional model. Y1 - 2014 SN - 978-3-662-45005-5 SN - 1865-0929 IS - 500 SP - 73 EP - 87 PB - Springer CY - Berlin ER - TY - JOUR A1 - Blankertz, Benjamin A1 - Dornhege, Guido A1 - Krauledat, Matthias A1 - Müller, Klaus-Robert A1 - Kunzmann, Volker A1 - Losch, Florian A1 - Curio, Gabriel T1 - The Berlin brain-computer interface : EEG-based communication without subject training N2 - The Berlin Brain-Computer Interface (BBCI) project develops a noninvasive BCI system whose key features are 1) the use of well-established motor competences as control paradigms, 2) high-dimensional features from 128-channel electroencephalogram (EEG), and 3) advanced machine learning techniques. As reported earlier, our experiments demonstrate that very high information transfer rates can be achieved using the readiness potential (RP) when predicting the laterality of upcoming left-versus right-hand movements in healthy subjects. A more recent study showed that the RP similarily accompanies phantom movements in arm amputees, but the signal strength decreases with longer loss of the limb. In a complementary approach, oscillatory features are used to discriminate imagined movements (left hand versus right hand versus foot). In a recent feedback study with six healthy subjects with no or very little experience with BCI control, three subjects achieved an information transfer rate above 35 bits per minute (bpm), and further two subjects above 24 and 15 bpm, while one subject could not achieve any BCI control. These results are encouraging for an EEG-based BCI system in untrained subjects that is independent of peripheral nervous system activity and does not rely on evoked potentials even when compared to results with very well-trained subjects operating other BCI systems Y1 - 2006 UR - http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=7333 U6 - https://doi.org/10.1109/Tnsre.2006.875557 SN - 1534-4320 ER - TY - JOUR A1 - Blankertz, Benjamin A1 - Müller, Klaus-Robert A1 - Curio, Gabriel A1 - Vaughan, Theresa M. A1 - Schalk, Gerwin A1 - Wolpaw, Jonathan R. A1 - Schlogl, Alois A1 - Neuper, Christa A1 - Pfurtscheller, Gert A1 - Hinterberger, Thilo A1 - Schroder, Michael A1 - Birbaumer, Niels T1 - The BCI competition 2003 : Progress and perspectives in detection and discrimination of EEG single trials N2 - Interest in developing a new method of man-to-machine communication-a brain-computer interface (BCI)-has grown steadily over the past few decades. BCIs create a new communication channel between the brain and an output device by bypassing conventional motor output pathways of nerves and muscles. These systems use signals recorded from the scalp, the surface of the cortex, or from inside the brain to enable users to control a variety of applications including simple word-processing software and orthotics. BCI technology could therefore provide a new communication and control option for individuals who cannot otherwise express their wishes to the outside world. Signal processing and classification methods are essential tools in the development of improved BCI technology. We organized the BCI Competition 2003 to evaluate the current state of the art of these tools. Four laboratories well versed in EEG-based BCI research provided six data sets in a documented format. We made these data sets (i.e., labeled training sets and unlabeled test sets) and their descriptions available on the Internet. The goal in the competition was to maximize the performance measure for the test labels. Researchers worldwide tested their algorithms and competed for the best classification results. This paper describes the six data sets and the results and function of the most successful algorithms Y1 - 2004 SN - 0018-9294 ER - TY - JOUR A1 - Blankertz, Benjamin A1 - Müller, Klaus-Robert A1 - Krusienski, Dean A1 - Schalk, Gerwin A1 - Wolpaw, Jonathan R. A1 - Schlögl, Alois A1 - Pfurtscheller, Gert A1 - Millan, José del R. A1 - Schröder, Michael A1 - Birbaumer, Niels T1 - The BCI competition III : validating alternative approaches to actual BCI problems N2 - A brain-computer interface (BCI) is a system that allows its users to control external devices with brain activity. Although the proof-of-concept was given decades ago, the reliable translation of user intent into device control commands is still a major challenge. Success requires the effective interaction of two adaptive controllers: the user's brain, which produces brain activity that encodes intent, and the BCI system, which translates that activity into device control commands. In order to facilitate this interaction, many laboratories are exploring a variety of signal analysis techniques to improve the adaptation of the BCI system to the user. In the literature, many machine learning and pattern classification algorithms have been reported to give impressive results when applied to BCI data in offline analyses. However, it is more difficult to evaluate their relative value for actual online use. BCI data competitions have been organized to provide objective formal evaluations of alternative methods. Prompted by the great interest in the first two BCI Competitions, we organized the third BCI Competition to address several of the most difficult and important analysis problems in BCI research. The paper describes the data sets that were provided to the competitors and gives an overview of the results. Y1 - 2006 UR - http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=7333 U6 - https://doi.org/10.1109/Tnsre.2006.875642 SN - 1534-4320 ER - TY - JOUR A1 - Blum, Niklas A1 - Boldea, Irina A1 - Magedanz, Thomas A1 - Margaria, Tiziana T1 - Service-oriented access to next generation networks : from service creation to execution N2 - Existing telecommunication networks and classical roles of operators are subject to fundamental change. Many network operators are currently seeking for new sources to generate revenue by exposing network capabilities to 3rd party service providers. At the same time we can observe that services on the World Wide Web (WWW) are becoming mature in terms of the definition of APIs that are offered towards other services. The combinations of those services are commonly referred to as Web 2.0 mash-ups. Rapid service design and creation becomes therefore important to meet the requirements in a changing technology and competitive market environment. This report describes our approach to include Next Generation Networks (NGN)-based telecommunications application enabler into complex services by defining a service broker that mediates between 3rd party applications and NGN service enablers. It provides policy-driven orchestration mechanisms for service enablers, a service authorization functionality, and a service discovery interface for Service Creation Environments. The work has been implemented as part of the Open SOA Telco Playground testbed at Fraunhofer FOKUS. Y1 - 2010 UR - http://www.springerlink.com/content/101750 U6 - https://doi.org/10.1007/s11036-010-0222-1 SN - 1383-469X ER - TY - JOUR A1 - Bobda, Christophe T1 - Special issue on ReCoSoC 2007 : editorial Y1 - 2009 UR - http://www.sciencedirect.com/science/journal/01419331 U6 - https://doi.org/10.1016/j.micpro.2009.01.001 SN - 0141-9331 ER - TY - JOUR A1 - Boerner, Ferdinand A1 - Bulatov, Andrei A1 - Chen, Hubie A1 - Jeavons, Peter A1 - Krokhin, Andrei T1 - The complexity of constraint satisfaction games and QCSP N2 - We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint: the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true. While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate. one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games. Y1 - 2009 UR - http://www.sciencedirect.com/science/journal/08905401 U6 - https://doi.org/10.1016/J.Ic.2009.05.003 SN - 0890-5401 ER - TY - JOUR A1 - Boesel, Andreas A1 - Linke, Thomas A1 - Schaub, Torsten H. T1 - Profiling answer set programming : the visualization component of the noMoRe System Y1 - 2004 SN - 3-540-23242-7 ER - TY - JOUR A1 - Bogue, Ted A1 - Gössel, Michael A1 - Jürgensen, Helmut A1 - Zorian, Yervant T1 - Built-in self-Test with an alternating output Y1 - 1998 SN - 0-8186-8359-7 ER - TY - JOUR A1 - Bogue, Ted A1 - Jürgensen, Helmut A1 - Gössel, Michael T1 - BIST with negligible aliasing through random cover circuits Y1 - 1995 ER - TY - JOUR A1 - Bogue, Ted A1 - Jürgensen, Helmut A1 - Gössel, Michael T1 - Design of cover circuits for monitoring the output of a MISR Y1 - 1994 SN - 0-8186-6307-3 , 0-8186-6306-5 ER - TY - JOUR A1 - Boll, Susanne A1 - Meinhardt, Rolf A1 - Gronewold, Sabine A1 - Krekeler, Larissa T1 - Informatik für Migratinnen und Migranten Einführung eines neuen Studienprogramms an der Universität Oldenburg JF - Commentarii informaticae didacticae : (CID) N2 - Für die Integration und den Bedarf der hochqualifizierten Migranten auf dem Arbeitsmarkt in Deutschland gibt es viele Überlegungen, aber noch keine ausreichenden Lösungen. Dieser Artikel beschreibt eine praktische Lösung über die Umsetzung des Konzepts für die Qualifizierung der akademischen Migranten am Beispiel eines Studienprogramms in Informatik an der Universität Oldenburg. Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64370 SN - 1868-0844 SN - 2191-1940 IS - 4 SP - 79 EP - 86 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Borchert, P. A1 - Anger, Christian A1 - Schaub, Torsten H. A1 - Truszczynski, M. T1 - Towards systematic benchmarking in answer set programming : the dagstuhl initiative Y1 - 2004 SN - 3-540- 20721-x ER - TY - JOUR A1 - Bordihn, Henning T1 - On the number of components in cooperating distributed grammar systems N2 - It is proved that the number of components in context-free cooperating distributed (CD) grammar systems can be reduced to 3 when they are working in the so-called sf-mode of derivation, which is the cooperation protocol which has been considered first for CD grammar systems. In this derivation mode, a component continues the derivation until and unless there is a nonterminal in the sentential form which cannot be rewritten according to that component. Moreover, it is shown that CD grammar systems in sf-mode with only one component can generate only the context-free languages but they can generate non-context-free languages if two components are used. The sf-mode of derivation is compared with other well-known cooperation protocols with respect to the hierarchies induced by the number of components. (C) 2004 Elsevier B.V. All rights reserved Y1 - 2005 SN - 0304-3975 ER - TY - JOUR A1 - Bordihn, Henning T1 - Context-freeness of the power of context-free languages is undecidable N2 - The power of a language L is the set of all powers of the words in L. In this paper, the following decision problem is investigated. Given a context-free language L, is the power of L context-free? We show that this problem is decidable for languages over unary alphabets, but it is undecidable whenever languages over alphabets with at least two letters are considered. (C) 2003 Elsevier B.V. All rights reserved Y1 - 2004 SN - 0304-3975 ER - TY - JOUR A1 - Bordihn, Henning A1 - Dassow, Juergen A1 - Holzer, Markus T1 - Extending regular expressions with homomorphic replacement N2 - We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns, pattern expressions, H-systems and uniform substitutions are also investigated. Furthermore, we present their closure properties with respect to TRIO operations and discuss the decidability status and complexity of fixed and general membership, emptiness, and the equivalence problem. Y1 - 2010 UR - http://www.rairo-ita.org/ U6 - https://doi.org/10.1051/Ita/2010013 SN - 0988-3754 ER - TY - JOUR A1 - Bordihn, Henning A1 - Fernau, Henning A1 - Holzer, Markus A1 - Manca, Vincenzo A1 - Martin-Vide, Carlos T1 - Iterated sequential transducers as language generating devices JF - Theoretical computer science N2 - Iterated finite state sequential transducers are considered as language generating devices. The hierarchy induced by the size of the state alphabet is proved to collapse to the fourth level. The corresponding language families are related to the families of languages generated by Lindenmayer systems and Chomsky grammars. Finally, some results on deterministic and extended iterated finite state transducers are established. KW - finite state sequential transducers KW - state complexity KW - Lindenmayer systems Y1 - 2006 U6 - https://doi.org/10.1016/j.tcs.2006.07.059 SN - 0304-3975 VL - 369 IS - 1 SP - 67 EP - 81 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Bordihn, Henning A1 - Holzer, Markus T1 - Programmed grammars and their relation to the LBA problem JF - Acta informatica N2 - We consider generating and accepting programmed grammars with bounded degree of non-regulation, that is, the maximum number of elements in success or in failure fields of the underlying grammar. In particular, it is shown that this measure can be restricted to two without loss of descriptional capacity, regardless of whether arbitrary derivations or left-most derivations are considered. Moreover, in some cases, precise characterizations of the linear bounded automaton problem in terms of programmed grammars are obtained. Thus, the results presented in this paper shed new light on some longstanding open problem in the theory of computational complexity. KW - programmed grammars KW - accepting grammars KW - LBA problem KW - degree of non-regulation KW - leftmost derivations Y1 - 2006 U6 - https://doi.org/10.1007/s00236-006-0017-9 SN - 0001-5903 VL - 43 SP - 223 EP - 242 PB - Elsevier CY - New York ER - TY - JOUR A1 - Bordihn, Henning A1 - Holzer, Markus T1 - On the number of active states in finite automata JF - Acta informatica N2 - We introduce a new measure of descriptional complexity on finite automata, called the number of active states. Roughly speaking, the number of active states of an automaton A on input w counts the number of different states visited during the most economic computation of the automaton A for the word w. This concept generalizes to finite automata and regular languages in a straightforward way. We show that the number of active states of both finite automata and regular languages is computable, even with respect to nondeterministic finite automata. We further compare the number of active states to related measures for regular languages. In particular, we show incomparability to the radius of regular languages and that the difference between the number of active states and the total number of states needed in finite automata for a regular language can be of exponential order. Y1 - 2021 U6 - https://doi.org/10.1007/s00236-021-00397-8 SN - 0001-5903 SN - 1432-0525 VL - 58 IS - 4 SP - 301 EP - 318 PB - Springer CY - Berlin ; Heidelberg [u.a.] ER - TY - JOUR A1 - Bordihn, Henning A1 - Holzer, Markus A1 - Kutrib, Martin T1 - Unsolvability levels of operation problems for subclasses of context-free languages N2 - We investigate the operation problem for linear and deterministic context-free languages: Fix an operation on formal languages. Given linear (deterministic, respectively) context-free languages, is the application of this operation to the given languages still a linear (deterministic, respectively) context-free language? Besides the classical operations, for which the linear and deterministic context-free languages are not closed, we also consider the recently introduced root and power operation. We show non-semidecidability, to be more precise, we show completeness for the second level of the arithmetic hierarchy for all of the aforementioned operations, except for the power operation, if the underlying alphabet contains at least two letters. The result for the power opera, tion solves an open problem stated in Theoret. Comput. Sci. 314 (2004) 445-449 Y1 - 2005 SN - 0129-0541 ER - TY - JOUR A1 - Bordihn, Henning A1 - Holzer, Markus A1 - Kutrib, Martin T1 - Determination of finite automata accepting subregular languages N2 - We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, Suffix-, and infix-free languages. Most of the bounds for the conversion problem are shown to be tight ill the exact number of states, that is, the number is sufficient and necessary in the worst case. Otherwise tight bounds in order of magnitude are shown. Y1 - 2009 UR - http://www.sciencedirect.com/science/journal/03043975 U6 - https://doi.org/10.1016/j.tcs.2009.05.019 SN - 0304-3975 ER - TY - JOUR A1 - Bordihn, Henning A1 - Holzer, Markus A1 - Kutrib, Martin T1 - Decidability of operation problems for TOL languages and subclasses JF - Information and computation N2 - We investigate the decidability of the operation problem for TOL languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (OL languages, TOL languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of OL and TOL languages and their propagating variants are not even semidecidable. The situation changes for unary OL languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable. KW - L systems KW - Operation problem KW - Decidability KW - Unary languages Y1 - 2011 U6 - https://doi.org/10.1016/j.ic.2010.11.008 SN - 0890-5401 VL - 209 IS - 3 SP - 344 EP - 352 PB - Elsevier CY - San Diego ER - TY - JOUR A1 - Bordihn, Henning A1 - Kutrib, Martin A1 - Malcher, Andreas T1 - On the computational capacity of parallel communicating finite automata JF - International journal of foundations of computer science N2 - Systems of parallel finite automata communicating by states are investigated. We consider deterministic and nondeterministic devices and distinguish four working modes. It is known that systems in the most general mode are as powerful as one-way multi-head finite automata. Here we solve some open problems on the computational capacity of systems working in the remaining modes. In particular, it is shown that deterministic returning and non-returning devices are equivalent, and that there are languages which are accepted by deterministic returning and centralized systems but cannot be accepted by deterministic non-returning centralized systems. Furthermore, we show that nondeterministic systems are strictly more powerful than their deterministic variants in all the four working modes. Finally, incomparability with the classes of (deterministic) (linear) context-free languages as well as the Church-Rosser languages is derived. KW - Automata systems KW - cooperating systems KW - formal languages KW - theory of computation Y1 - 2012 U6 - https://doi.org/10.1142/S0129054112500062 SN - 0129-0541 VL - 23 IS - 3 SP - 713 EP - 732 PB - World Scientific CY - Singapore ER - TY - JOUR A1 - Bordihn, Henning A1 - Kutrib, Martin A1 - Malcher, Andreas T1 - Undecidability and hierarchy results for parallel communicating finite automata JF - International journal of foundations of computer science N2 - Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes. KW - Automata systems KW - cooperating systems KW - formal languages KW - decidability questions Y1 - 2011 U6 - https://doi.org/10.1142/S0129054111008891 SN - 0129-0541 VL - 22 IS - 7 SP - 1577 EP - 1592 PB - World Scientific CY - Singapore ER - TY - JOUR A1 - Bordihn, Henning A1 - Mitrana, Victor T1 - On the degrees of non-regularity and non-context-freeness JF - Journal of computer and system sciences N2 - We study the derivational complexity of context-free and context-sensitive grammars by counting the maximal number of non-regular and non-context-free rules used in a derivation, respectively. The degree of non-regularity/non-context-freeness of a language is the minimum degree of non-regularity/non-context-freeness of context-free/context-sensitive grammars generating it. A language has finite degree of non-regularity iff it is regular. We give a condition for deciding whether the degree of non-regularity of a given unambiguous context-free grammar is finite. The problem becomes undecidable for arbitrary linear context-free grammars. The degree of non-regularity of unambiguous context-free grammars generating non-regular languages as well as that of grammars generating deterministic context-free languages that are not regular is of order Omega(n). Context-free non-regular languages of sublinear degree of non-regularity are presented. A language has finite degree of non-context-freeness if it is context-free. Context-sensitive grammars with a quadratic degree of non-context-freeness are more powerful than those of a linear degree. KW - context-free grammar KW - degree of non-regularity KW - context-sensitive KW - grammar KW - degree of non-context-freeness Y1 - 2020 U6 - https://doi.org/10.1016/j.jcss.2019.09.003 SN - 0022-0000 SN - 1090-2724 VL - 108 SP - 104 EP - 117 PB - Elsevier CY - San Diego, Calif. [u.a.] ER - TY - JOUR A1 - Bordihn, Henning A1 - Mitrana, Victor A1 - Negru, Maria C. A1 - Paun, Andrei A1 - Paun, Mihaela T1 - Small networks of polarized splicing processors are universal JF - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal N2 - In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. All these results can be obtained with NPSPs with valuations in the set as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of this simulation. KW - Computing with DNA KW - Splicing KW - Splicing processor KW - Polarization KW - 2-tag system KW - Turing machine Y1 - 2018 U6 - https://doi.org/10.1007/s11047-018-9691-0 SN - 1567-7818 SN - 1572-9796 VL - 17 IS - 4 SP - 799 EP - 809 PB - Springer CY - Dordrecht ER - TY - JOUR A1 - Bordihn, Henning A1 - Mitrana, Victor A1 - Paun, Andrei A1 - Paun, Mihaela T1 - Hairpin completions and reductions BT - semilinearity properties JF - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal N2 - This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin completions or reductions of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying the non-iterated hairpin completion or hairpin reduction. A similar approach is then applied to the iterated variants of these operations. Along these lines, we define the hairpin reduction root of a language and show that the hairpin reduction root of a semilinear language is not necessarily semilinear except the universal language. A few open problems are finally discussed. KW - DNA hairpin formation KW - Hairpin completions KW - Hairpin reductions KW - Semilinearity property Y1 - 2020 U6 - https://doi.org/10.1007/s11047-020-09797-0 SN - 1572-9796 VL - 20 IS - 2 SP - 193 EP - 203 PB - Springer Science + Business Media B.V. CY - Dordrecht ER - TY - JOUR A1 - Bordihn, Henning A1 - Vaszil, György T1 - Deterministic Lindenmayer systems with dynamic control of parallelism JF - International journal of foundations of computer science N2 - M-rate 0L systems are interactionless Lindenmayer systems together with a function assigning to every string a set of multisets of productions that may be applied simultaneously to the string. Some questions that have been left open in the forerunner papers are examined, and the computational power of deterministic M-rate 0L systems is investigated, where also tabled and extended variants are taken into consideration. KW - parallel rewriting KW - Lindenmayer systems KW - restricted parallelism KW - determinism KW - developmental systems KW - formal languages Y1 - 2019 U6 - https://doi.org/10.1142/S0129054120400031 SN - 0129-0541 SN - 1793-6373 VL - 31 IS - 1 SP - 37 EP - 51 PB - World Scientific CY - Singapore ER - TY - JOUR A1 - Bordihn, Henning A1 - Vaszil, György T1 - Reversible parallel communicating finite automata systems JF - Acta informatica N2 - We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type. KW - Finite automata KW - Reversibility KW - Systems of parallel communicating KW - automata Y1 - 2021 U6 - https://doi.org/10.1007/s00236-021-00396-9 SN - 0001-5903 SN - 1432-0525 VL - 58 IS - 4 SP - 263 EP - 279 PB - Springer CY - Berlin ; Heidelberg ; New York, NY ER - TY - JOUR A1 - Bottino, Rosa A1 - Chioccariello, Augusto T1 - Computational Thinking BT - Videogames, Educational Robotics, and other Powerful Ideas to Think with JF - KEYCIT 2014 - Key Competencies in Informatics and ICT N2 - Digital technology has radically changed the way people work in industry, finance, services, media and commerce. Informatics has contributed to the scientific and technological development of our society in general and to the digital revolution in particular. Computational thinking is the term indicating the key ideas of this discipline that might be included in the key competencies underlying the curriculum of compulsory education. The educational potential of informatics has a history dating back to the sixties. In this article, we briefly revisit this history looking for lessons learned. In particular, we focus on experiences of teaching and learning programming. However, computational thinking is more than coding. It is a way of thinking and practicing interactive dynamic modeling with computers. We advocate that learners can practice computational thinking in playful contexts where they can develop personal projects, for example building videogames and/or robots, share and discuss their construction with others. In our view, this approach allows an integration of computational thinking in the K-12 curriculum across disciplines. KW - Computational thinking KW - programming in context KW - informatics education Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-82820 SN - 1868-0844 SN - 2191-1940 IS - 7 SP - 301 EP - 309 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Brain, Martin A1 - Faber, Wolfgang A1 - Maratea, Marco A1 - Polleres, Axel A1 - Schaub, Torsten H. A1 - Schindlauer, Roman T1 - What should an ASP solver output? : a multiple position paper Y1 - 2007 ER - TY - JOUR A1 - Brain, Martin A1 - Gebser, Martin A1 - Pührer, Jörg A1 - Schaub, Torsten H. A1 - Tompits, Hans A1 - Woltran, Stefan T1 - "That is illogical, Captain!" : the debugging support tool spock for answer-set programs ; system description Y1 - 2007 ER - TY - JOUR A1 - Brain, Martin A1 - Gebser, Martin A1 - Pührer, Jörg A1 - Schaub, Torsten H. A1 - Tompits, Hans A1 - Woltran, Stefan T1 - Debugging ASP programs by means of ASP Y1 - 2007 SN - 978-3-540- 72199-4 ER - TY - JOUR A1 - Braun, Iris A1 - Kapp, Felix A1 - Hara, Tenshi A1 - Kubica, Tommy T1 - Erfolgsfaktoren beim Einsatz von Audience Response Systemen in der universitären Lehre BT - Erfahrungen aus dem ARS-Projekt "Auditorium Mobile Classroom Service" JF - E-Learning Symposium 2018 N2 - Der vorliegende Beitrag berichtet auf der Grundlage von Erfahrungen mit dem Audience Response System (ARS) „Auditorium Mobile Classroom Service“ von Erfolgsfaktoren für den Einsatz in der universitären Lehre. Dabei werden sowohl die technischen Rahmenbedingungen und Herausforderungen der Anwendungen berücksichtigt, als auch die unterschiedlichen didaktischen Konzepte und Ziele der beteiligten Akteure (Studierende, Lehrende und Institution). Ziel ist es, Einflussfaktoren für den erfolgreichen Einsatz sowohl für die Praxis als auch die wissenschaftliche Untersuchung und Weiterentwicklung der Systeme zu benennen und ein heuristisches Framework für Chancen und Herausforderungen beim Einsatz von ARS anzubieten. KW - Audience Response Systeme KW - technische Rahmenbedingungen KW - didaktisches Konzept Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-421959 SP - 65 EP - 67 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Brede, Nuria A1 - Botta, Nicola T1 - On the correctness of monadic backward induction JF - Journal of functional programming N2 - In control theory, to solve a finite-horizon sequential decision problem (SDP) commonly means to find a list of decision rules that result in an optimal expected total reward (or cost) when taking a given number of decision steps. SDPs are routinely solved using Bellman's backward induction. Textbook authors (e.g. Bertsekas or Puterman) typically give more or less formal proofs to show that the backward induction algorithm is correct as solution method for deterministic and stochastic SDPs. Botta, Jansson and Ionescu propose a generic framework for finite horizon, monadic SDPs together with a monadic version of backward induction for solving such SDPs. In monadic SDPs, the monad captures a generic notion of uncertainty, while a generic measure function aggregates rewards. In the present paper, we define a notion of correctness for monadic SDPs and identify three conditions that allow us to prove a correctness result for monadic backward induction that is comparable to textbook correctness proofs for ordinary backward induction. The conditions that we impose are fairly general and can be cast in category-theoretical terms using the notion of Eilenberg-Moore algebra. They hold in familiar settings like those of deterministic or stochastic SDPs, but we also give examples in which they fail. Our results show that backward induction can safely be employed for a broader class of SDPs than usually treated in textbooks. However, they also rule out certain instances that were considered admissible in the context of Botta et al. 's generic framework. Our development is formalised in Idris as an extension of the Botta et al. framework and the sources are available as supplementary material. Y1 - 2021 U6 - https://doi.org/10.1017/S0956796821000228 SN - 1469-7653 VL - 31 PB - Cambridge University Press CY - Cambridge ER - TY - JOUR A1 - Breitenreiter, Anselm A1 - Andjelković, Marko A1 - Schrape, Oliver A1 - Krstić, Miloš T1 - Fast error propagation probability estimates by answer set programming and approximate model counting JF - IEEE Access N2 - We present a method employing Answer Set Programming in combination with Approximate Model Counting for fast and accurate calculation of error propagation probabilities in digital circuits. By an efficient problem encoding, we achieve an input data format similar to a Verilog netlist so that extensive preprocessing is avoided. By a tight interconnection of our application with the underlying solver, we avoid iterating over fault sites and reduce calls to the solver. Several circuits were analyzed with varying numbers of considered cycles and different degrees of approximation. Our experiments show, that the runtime can be reduced by approximation by a factor of 91, whereas the error compared to the exact result is below 1%. KW - Circuit faults KW - Integrated circuit modeling KW - Programming KW - Analytical models KW - Search problems KW - Flip-flops KW - Encoding KW - Answer set programming KW - approximate model counting KW - error propagation KW - radhard design KW - reliability analysis KW - selective fault tolerance KW - single event upsets Y1 - 2022 U6 - https://doi.org/10.1109/ACCESS.2022.3174564 SN - 2169-3536 VL - 10 SP - 51814 EP - 51825 PB - Inst. of Electr. and Electronics Engineers CY - Piscataway ER -