Zobrazeno 1 - 10
of 633
pro vyhledávání: '"A. Siebertz"'
Autor:
Grobler, Mario, Siebertz, Sebastian
Various variants of Parikh automata on infinite words have recently been introduced in the literature. However, with some exceptions only their non-deterministic versions have been considered. In this paper we study the deterministic versions of all
Externí odkaz:
http://arxiv.org/abs/2401.14737
Autor:
Grobler, Mario, Maaz, Stephanie, Megow, Nicole, Mouawad, Amer E., Ramamoorthi, Vijayaragunathan, Schmand, Daniel, Siebertz, Sebastian
In the recently introduced framework of solution discovery via reconfiguration [Fellows et al., ECAI 2023], we are given an initial configuration of $k$ tokens on a graph and the question is whether we can transform this configuration into a feasible
Externí odkaz:
http://arxiv.org/abs/2311.13478
We study reduction rules for Directed Feedback Vertex Set (DFVS) on instances without long cycles. A DFVS instance without cycles longer than $d$ naturally corresponds to an instance of $d$-Hitting Set, however, enumerating all cycles in an $n$-verte
Externí odkaz:
http://arxiv.org/abs/2308.15900
Several variants of Parikh automata on infinite words were recently introduced by Guha et al. [FSTTCS, 2022]. We show that one of these variants coincides with blind counter machine as introduced by Fernau and Stiebe [Fundamenta Informaticae, 2008].
Externí odkaz:
http://arxiv.org/abs/2307.07238
Autor:
Fellows, Michael R., Grobler, Mario, Megow, Nicole, Mouawad, Amer E., Ramamoorthi, Vijayaragunathan, Rosamond, Frances A., Schmand, Daniel, Siebertz, Sebastian
The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current state of a system in a restricted way. We propose a new framework of s
Externí odkaz:
http://arxiv.org/abs/2304.14295
Autor:
Schirrmacher, Nicole, Siebertz, Sebastian, Stamoulis, Giannos, Thilikos, Dimitrios M., Vigny, Alexandre
Disjoint-paths logic, denoted $\mathsf{FO}$+$\mathsf{DP}$, extends first-order logic ($\mathsf{FO}$) with atomic predicates $\mathsf{dp}_k[(x_1,y_1),\ldots,(x_k,y_k)]$, expressing the existence of internally vertex-disjoint paths between $x_i$ and $y
Externí odkaz:
http://arxiv.org/abs/2302.07033
Autor:
Grobler, Mario, Siebertz, Sebastian
B\"uchi's theorem states that $\omega$-regular languages are characterized as languages of the form $\bigcup_i U_i V_i^\omega$, where $U_i$ and $V_i$ are regular languages. Parikh automata are automata on finite words whose transitions are equipped w
Externí odkaz:
http://arxiv.org/abs/2302.04087
A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly generalize nowhere dense classes and constitute important examples of monadic
Externí odkaz:
http://arxiv.org/abs/2302.03527
Autor:
Gajarský, Jakub, Mählmann, Nikolas, McCarty, Rose, Ohlmann, Pierre, Pilipczuk, Michał, Przybyszewski, Wojciech, Siebertz, Sebastian, Sokołowski, Marek, Toruńczyk, Szymon
A class of graphs $\mathscr{C}$ is monadically stable if for any unary expansion $\widehat{\mathscr{C}}$ of $\mathscr{C}$, one cannot interpret, in first-order logic, arbitrarily long linear orders in graphs from $\widehat{\mathscr{C}}$. It is known
Externí odkaz:
http://arxiv.org/abs/2301.13735
Parikh automata on finite words were first introduced by Klaedtke and Rue{\ss} [Automata, Languages and Programming, 2003]. In this paper, we introduce several variants of Parikh automata on infinite words and study their expressiveness. We show that
Externí odkaz:
http://arxiv.org/abs/2301.08969