Publikationen an der Fakultät für Informatik und Automatisierung ab 2015

Anzahl der Treffer: 1905
Erstellt: Wed, 27 Mar 2024 23:30:23 +0100 in 0.0469 sec


Klee, Sascha; Link, Dietmar; Sinzinger, Stefan; Haueisen, Jens
Scotoma simulation in healthy subjects. - In: Optometry and vision science, ISSN 1538-9235, Bd. 95 (2018), 12, S. 1120-1128

https://doi.org/10.1097/OPX.0000000000001310
Dunke, Susanne; Boho, David; Wäldchen, Jana; Mäder, Patrick
Combining high-throughput imaging flow cytometry and deep learning for efficient species and life-cycle stage identification of phytoplankton. - In: BMC ecology, ISSN 1472-6785, Bd. 18 (2018), 51, insges. 15 S.

https://doi.org/10.1186/s12898-018-0209-5
Abu Zaid, Faried;
Uniformly automatic classes of finite structures. - In: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, (2018), Seite 10:1-10:21

We investigate the recently introduced concept of uniformly tree-automatic classes in the realm of parameterized complexity theory. Roughly speaking, a class of finite structures is uniformly tree-automatic if it can be presented by a set of finite trees and a tuple of automata. A tree t encodes a structure and an element of this structure is encoded by a labeling of t. The automata are used to present the relations of the structure. We use this formalism to obtain algorithmic meta-theorems for first-order logic and in some cases also monadic second-order logic on classes of finite Boolean algebras, finite groups, and graphs of bounded tree-depth. Our main concern is the efficiency of this approach with respect to the hidden parameter dependence (size of the formula). We develop a method to analyze the complexity of uniformly tree-automatic presentations, which allows us to give upper bounds for the runtime of the automata-based model checking algorithm on the presented class. It turns out that the parameter dependence is elementary for all the above mentioned classes. Additionally we show that one can lift the FPT results, which are obtained by our method, from a class C to the closure of C under direct products with only a singly exponential blow-up in the parameter dependence.



http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2018.10
Abu Zaid, Faried; Köcher, Chris
The Cayley-graph of the queue monoid: logic and decidability. - In: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, (2018), Seite 9:1-9:17

We investigate the decidability of logical aspects of graphs that arise as Cayley-graphs of the so-called queue monoids. These monoids model the behavior of the classical (reliable) fifo-queues. We answer a question raised by Huschenbett, Kuske, and Zetzsche and prove the decidability of the first-order theory of these graphs with the help of an - at least for the authors - new combination of the well-known method from Ferrante and Rackoff and an automata-based approach. On the other hand, we prove that the monadic second-order of the queue monoid's Cayley-graph is undecidable.



http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2018.9
Köcher, Chris;
Rational, recognizable, and aperiodic sets in the partially lossy queue monoid. - In: 35th Symposium on Theoretical Aspects of Computer Science, (2018), S. 45:1-45:14

Partially lossy queue monoids (or plq monoids) model the behavior of queues that can forget arbitrary parts of their content. While many decision problems on recognizable subsets in the plq monoid are decidable, most of them are undecidable if the sets are rational. In particular, in this monoid the classes of rational and recognizable subsets do not coincide. By restricting multiplication and iteration in the construction of rational sets and by allowing complementation we obtain precisely the class of recognizable sets. From these special rational expressions we can obtain an MSO logic describing the recognizable subsets. Moreover, we provide similar results for the class of aperiodic subsets in the plq monoid.



https://doi.org/10.4230/LIPIcs.STACS.2018.45
Abu Zaid, Faried; Kuske, Dietrich; Lindner, Peter
Climbing up the elementary complexity classes with theories of automatic structures. - In: Computer Science Logic 2018, (2018), Seite 3:1-3:16

We investigate the recently introduced concept of uniformly tree-automatic classes in the realm of parameterized complexity theory. Roughly speaking, a class of finite structures is uniformly tree-automatic if it can be presented by a set of finite trees and a tuple of automata. A tree t encodes a structure and an element of this structure is encoded by a labeling of t. The automata are used to present the relations of the structure. We use this formalism to obtain algorithmic meta-theorems for first-order logic and in some cases also monadic second-order logic on classes of finite Boolean algebras, finite groups, and graphs of bounded tree-depth. Our main concern is the efficiency of this approach with respect to the hidden parameter dependence (size of the formula). We develop a method to analyze the complexity of uniformly tree-automatic presentations, which allows us to give upper bounds for the runtime of the automata-based model checking algorithm on the presented class. It turns out that the parameter dependence is elementary for all the above mentioned classes. Additionally we show that one can lift the FPT results, which are obtained by our method, from a class C to the closure of C under direct products with only a singly exponential blow-up in the parameter dependence.



http://dx.doi.org/10.4230/LIPIcs.CSL.2018.3
Kuske, Dietrich; Schweikardt, Nicole
Gaifman normal forms for counting extensions of first-order logic. - In: 45th International Colloquium on Automata, Languages, and Programming, (2018), Seite 133:1-133:14

We consider the extension of first-order logic FO by unary counting quantifiers and generalise the notion of Gaifman normal form from FO to this setting. For formulas that use only ultimately periodic counting quantifiers, we provide an algorithm that computes equivalent formulas in Gaifman normal form. We also show that this is not possible for formulas using at least one quantifier that is not ultimately periodic. Now let d be a degree bound. We show that for any formula phi with arbitrary counting quantifiers, there is a formula gamma in Gaifman normal form that is equivalent to phi on all finite structures of degree <= d. If the quantifiers of phi are decidable (decidable in elementary time, ultimately periodic), gamma can be constructed effectively (in elementary time, in worst-case optimal 3-fold exponential time). For the setting with unrestricted degree we show that by using our Gaifman normal form for formulas with only ultimately periodic counting quantifiers, a known fixed-parameter tractability result for FO on classes of structures of bounded local tree-width can be lifted to the extension of FO with ultimately periodic counting quantifiers (a logic equally expressive as FO+MOD, i.e., first-oder logic with modulo-counting quantifiers).



http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.133
Kuske, Dietrich; Liu, Jiamou; Moskvina, Anastasia
Infinite and bi-infinite words with decidable monadic theories. - In: Logical methods in computer science, ISSN 1860-5974, Bd. 14 (2018), 3:9, S. 1-24

We study word structures of the form (D,<,P) where D is either N or Z, < is the natural linear ordering on D and P⊆D is a predicate on D. In particular we show: (a) The set of recursive ω-words with decidable monadic second order theories is Σ3-complete. (b) Known characterisations of the ω-words with decidable monadic second order theories are transfered to the corresponding question for bi-infinite words. (c) We show that such "tame" predicates P exist in every Turing degree. (d) We determine, for P⊆Z, the number of predicates Q⊆Z such that (Z,≤,P) and (Z,≤,Q) are indistinguishable. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.



https://doi.org/10.23638/LMCS-14(3:9)2018
Glotzbach, Thomas;
Navigation of autonomous marine robots - novel approaches using cooperating teams. - Ilmenau. - XXXII, 366 Seiten
Technische Universität Ilmenau, Habilitationsschrift 2018


Rojas, Jorge; Baatar, Ganzorig; Cuellar, Francisco; Eichhorn, Mike; Glotzbach, Thomas
Modelling and essential control of an oceanographic monitoring remotely operated underwater vehicle. - In: IFAC-PapersOnLine, ISSN 2405-8963, Bd. 51 (2018), 29, S. 213-219

https://doi.org/10.1016/j.ifacol.2018.09.495