Zobrazeno 1 - 10
of 191
pro vyhledávání: '"Löding, Christof"'
Autor:
Filiot, Emmanuel, Jecker, Ismaël, Puppis, Gabriele, Löding, Christof, Muscholl, Anca, Winter, Sarah
A transducer is finite-valued if for some bound k, it maps any given input to at most k outputs. For classical, one-way transducers, it is known since the 80s that finite valuedness entails decidability of the equivalence problem. This decidability r
Externí odkaz:
http://arxiv.org/abs/2405.08171
Autor:
Löding, Christof, Thomas, Wolfgang
The class of Boolean combinations of tree languages recognized by deterministic top-down tree automata (also known as deterministic root-to-frontier automata) is studied. The problem of determining for a given regular tree language whether it belongs
Externí odkaz:
http://arxiv.org/abs/2401.06596
Autor:
Bohn, León, Löding, Christof
Publikováno v:
TheoretiCS, Volume 3 (July 30, 2024) theoretics:11491
We present a polynomial time algorithm that constructs a deterministic parity automaton (DPA) from a given set of positive and negative ultimately periodic example words. We show that this algorithm is complete for the class of $\omega$-regular langu
Externí odkaz:
http://arxiv.org/abs/2302.11043
Autor:
Löding, Christof, Stachon, Max Philip
Publikováno v:
Fundamenta Informaticae, Volume 189, Issue 1 (July 1, 2023) fi:10322
We study minimization problems for deterministic $\omega$-automata in the presence of don't care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don't care words. W
Externí odkaz:
http://arxiv.org/abs/2211.08787
The notion of delay between finite transducers is a core element of numerous fundamental results of transducer theory. The goal of this work is to provide a similar notion for more complex abstract machines: we introduce a new notion of delay tailore
Externí odkaz:
http://arxiv.org/abs/2205.04287
Autor:
Bohn, León, Löding, Christof
The RPNI algorithm (Oncina, Garcia 1992) constructs deterministic finite automata from finite sets of negative and positive example words. We propose and analyze an extension of this algorithm to deterministic $\omega$-automata with different types o
Externí odkaz:
http://arxiv.org/abs/2108.03735
Autor:
Löding, Christof, Winter, Sarah
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:2, Automata, Logic and Semantics (September 6, 2023) dmtcs:7460
Regular synchronization languages can be used to define rational relations of finite words, and to characterize subclasses of rational relations, like automatic or recognizable relations. We provide a systematic study of the decidability of uniformiz
Externí odkaz:
http://arxiv.org/abs/2104.12508
In this paper, we investigate the synthesis problem of terminating reactive systems from quantitative specifications. Such systems are modeled as finite transducers whose executions are represented as finite words in $(I\times O)^*$, where $I,O$ are
Externí odkaz:
http://arxiv.org/abs/2103.05550
Recursively defined linked data structures embedded in a pointer-based heap and their properties are naturally expressed in pure first-order logic with least fixpoint definitions (FO+lfp) with background theories. Such logics, unlike pure first-order
Externí odkaz:
http://arxiv.org/abs/2009.10207
Autor:
Löding, Christof, Pirogov, Anton
Probabilistic B\"uchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that go
Externí odkaz:
http://arxiv.org/abs/2004.13692