Zobrazeno 1 - 10
of 48
pro vyhledávání: '"Paperman, Charles"'
The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary $\Sigma_2$ formula defines a regular language with a neutral letter, then there is an
Externí odkaz:
http://arxiv.org/abs/2203.06075
Autor:
Amarilli, Antoine, Paperman, Charles
Publikováno v:
Logical Methods in Computer Science, Volume 19, Issue 4 (October 18, 2023) lmcs:11555
We study the variety ZG of monoids where the elements that belong to a group are central, i.e., commute with all other elements. We show that ZG is local, that is, the semidirect product ZG * D of ZG by definite semigroups is equal to LZG, the variet
Externí odkaz:
http://arxiv.org/abs/2102.07724
We study the dynamic membership problem for regular languages: fix a language L, read a word w, build in time O(|w|) a data structure indicating if w is in L, and maintain this structure efficiently under letter substitutions on w. We consider this p
Externí odkaz:
http://arxiv.org/abs/2102.07728
Autor:
Cadilhac, Michaël, Mazowiecki, Filip, Paperman, Charles, Pilipczuk, Michał, Sénizergues, Géraud
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expres
Externí odkaz:
http://arxiv.org/abs/2002.08630
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 1 (February 21, 2020) lmcs:4336
A word-to-word function is continuous for a class of languages~$\mathcal{V}$ if its inverse maps $\mathcal{V}$_languages to~$\mathcal{V}$. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of
Externí odkaz:
http://arxiv.org/abs/1802.10555
Autor:
Fijalkow, Nathanaël, Paperman, Charles
Publikováno v:
ACM Transactions on Computational Logic (TOCL): Volume 18 Issue 3, August 2017
We study Monadic Second-Order Logic (MSO) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebraic, automata-theoretic and machine-independent characterizations. We c
Externí odkaz:
http://arxiv.org/abs/1709.03117
Autor:
Amarilli, Antoine, Paperman, Charles
We introduce the constrained topological sorting problem (CTS): given a regular language K and a directed acyclic graph G with labeled vertices, determine if G has a topological sort that forms a word in K. This natural problem applies to several set
Externí odkaz:
http://arxiv.org/abs/1707.04310
Autor:
Cadilhac, Michaël, Paperman, Charles
First-order logic (FO) over words is shown to be equiexpressive with FO equipped with a restricted set of numerical predicates, namely the order, a binary predicate MSB$_0$, and the finite-degree predicates: FO[Arb] = FO[<, MSB$_0$, Fin]. The Crane B
Externí odkaz:
http://arxiv.org/abs/1701.02673
Autor:
Cadilhac, Michaël, Mazowiecki, Filip, Paperman, Charles, Pilipczuk, Michał, Sénizergues, Géraud
Publikováno v:
Theory of Computing Systems; Aug2024, Vol. 68 Issue 4, p593-614, 22p
We investigate a subclass of languages recognized by vector addition systems, namely languages of nondeterministic Parikh automata. While the regularity problem (is the language of a given automaton regular?) is undecidable for this model, we show su
Externí odkaz:
http://arxiv.org/abs/1612.06233