Zobrazeno 1 - 10
of 113
pro vyhledávání: '"Klin, Bartek"'
Autor:
Bojańczyk, Mikołaj, Klin, Bartek
We consider injective first-order interpretations that input and output trees of bounded height. The corresponding functions have polynomial output size, since a first-order interpretation can use a k-tuple of input nodes to represent a single output
Externí odkaz:
http://arxiv.org/abs/2311.04180
Autor:
Kołodziejski, Jędrzej, Klin, Bartek
We introduce the countdown $\mu$-calculus, an extension of the modal $\mu$-calculus with ordinal approximations of fixpoint operators. In addition to properties definable in the classical calculus, it can express (un)boundedness properties such as th
Externí odkaz:
http://arxiv.org/abs/2208.00536
One of the main reasons for the correspondence of regular languages and monadic second-order logic is that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for structures
Externí odkaz:
http://arxiv.org/abs/2201.09969
Publikováno v:
TheoretiCS, Volume 3 (May 6, 2024) theoretics:11208
We develop a theory of vector spaces spanned by orbit-finite sets. Using this theory, we give a decision procedure for equivalence of weighted register automata, which are the common generalization of weighted automata and register automata for infin
Externí odkaz:
http://arxiv.org/abs/2104.02438
Bisimilarity as an equivalence notion of systems has been central to process theory. Due to the recent rise of interest in quantitative systems (probabilistic, weighted, hybrid, etc.), bisimilarity has been extended in various ways: notably, bisimula
Externí odkaz:
http://arxiv.org/abs/1907.09634
Autor:
Bojańczyk, Mikołaj, Klin, Bartek
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 4 (November 29, 2019) lmcs:4447
$\omega$-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as $\omega$-semigroups are convenient algebras for infinite words. In the algebraic theory of languages, one hopes that a language is regular if an
Externí odkaz:
http://arxiv.org/abs/1804.06667
Autor:
Klin, Bartek, Łełyk, Mateusz
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 4 (October 29, 2019) lmcs:4389
We study an extension of modal $\mu$-calculus to sets with atoms and we study its basic properties. Model checking is decidable on orbit-finite structures, and a correspondence to parity games holds. On the other hand, satisfiability becomes undecida
Externí odkaz:
http://arxiv.org/abs/1803.06752
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 4 (December 11, 2019) lmcs:4321
We investigate the isomorphism problem in the setting of definable sets (equivalent to sets with atoms): given two definable relational structures, are they related by a definable isomorphism? Under mild assumptions on the underlying structure of ato
Externí odkaz:
http://arxiv.org/abs/1802.08500
Autor:
Klin, Bartek, Rot, Jurriaan
Publikováno v:
Logical Methods in Computer Science, Volume 12, Issue 4 (April 27, 2017) lmcs:2622
We use modal logic as a framework for coalgebraic trace semantics, and show the flexibility of the approach with concrete examples such as the language semantics of weighted, alternating and tree automata, and the trace semantics of generative probab
Externí odkaz:
http://arxiv.org/abs/1611.05183
We present an Angluin-style algorithm to learn nominal automata, which are acceptors of languages over infinite (structured) alphabets. The abstract approach we take allows us to seamlessly extend known variations of the algorithm to this new setting
Externí odkaz:
http://arxiv.org/abs/1607.06268