Zobrazeno 1 - 10
of 71
pro vyhledávání: '"Philippe Schnoebelen"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 15, Issue 2 (2019)
The height of a piecewise-testable language $L$ is the maximum length of the words needed to define $L$ by excluding and requiring given subwords. The height of $L$ is an important descriptive complexity measure that has not yet been investigated in
Externí odkaz:
https://doaj.org/article/05d2befdd8b44bbc866eba7b90fa6325
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 117, Iss Proc. QAPL 2013, Pp 116-131 (2013)
We consider games played on an infinite probabilistic arena where the first player aims at satisfying generalized Büchi objectives almost surely, i.e., with probability one. We provide a fixpoint characterization of the winning sets and associated w
Externí odkaz:
https://doaj.org/article/12dabe74fbc94875b27fc25457b273d5
Publikováno v:
Logical Methods in Computer Science, Vol Volume 11, Issue 2 (2015)
"Unidirectional channel systems" (Chambart & Schnoebelen, CONCUR 2008) are finite-state systems where one-way communication from a Sender to a Receiver goes via one reliable and one unreliable unbounded fifo channel. While reachability is decidable f
Externí odkaz:
https://doaj.org/article/4cc3d5c1c7a24d52b5885d1d570e9e07
Publikováno v:
Logical Methods in Computer Science, Vol Volume 10, Issue 4 (2014)
We introduce Priority Channel Systems, a new class of channel systems where messages carry a numeric priority and where higher-priority messages can supersede lower-priority messages preceding them in the fifo communication buffers. The decidability
Externí odkaz:
https://doaj.org/article/da04677659a544c7b310233e732e89a9
Autor:
Philippe Schnoebelen, K. Narayan Kumar, Simon Halfon, Prateek Karandikar, Jean Goubault-Larrecq
Publikováno v:
Well Quasi-Orders in Computation, Logic, Language and Reasoning
Well Quasi-Orders in Computation, Logic, Language and Reasoning, 53, Springer, pp.55-105, 2020, Trends in Logic, 978-3-030-30228-3. ⟨10.1007/978-3-030-30229-0_3⟩
Trends in Logic ISBN: 9783030302283
Well Quasi-Orders in Computation, Logic, Language and Reasoning, 53, Springer, pp.55-105, 2020, Trends in Logic, 978-3-030-30228-3. ⟨10.1007/978-3-030-30229-0_3⟩
Trends in Logic ISBN: 9783030302283
International audience; Elegant and general algorithms for handling upwards-closed and downwards-closed subsets of WQOs can be developed using the filter-based and ideal-based representation for these sets. These algorithms can be built in a generic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f3179025119cf969bf1651af4a97c7c
https://hal.archives-ouvertes.fr/hal-03083290
https://hal.archives-ouvertes.fr/hal-03083290
Publikováno v:
Well-Quasi Orders in Computation, Logic, Language and Reasoning
Peter M. Schuster; Monika Seisenberger; Andreas Weiermann. Well-Quasi Orders in Computation, Logic, Language and Reasoning, 53, Springer, 2020, Trends in Logic, ⟨10.1007/978-3-030-30229-0_2⟩
Trends in Logic ISBN: 9783030302283
Peter M. Schuster; Monika Seisenberger; Andreas Weiermann. Well-Quasi Orders in Computation, Logic, Language and Reasoning, 53, Springer, 2020, Trends in Logic, ⟨10.1007/978-3-030-30229-0_2⟩
Trends in Logic ISBN: 9783030302283
International audience; We investigate the ordinal invariants height, length, and width of well quasi orders (WQO), with particular emphasis on width, an invariant of interest for the larger class of orders with finite antichain condition (FAC). We s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8cd143e483c5738db24b102d2d7ba3f3
https://halshs.archives-ouvertes.fr/halshs-01625981/document
https://halshs.archives-ouvertes.fr/halshs-01625981/document
Autor:
Simon Halfon, Philippe Schnoebelen
Publikováno v:
Information Processing Letters
Information Processing Letters, Elsevier, 2019, 145, pp.68-73. ⟨10.1016/j.ipl.2019.01.012⟩
Information Processing Letters, Elsevier, 2019, 145, pp.68-73. ⟨10.1016/j.ipl.2019.01.012⟩
We show that the shuffle L ⊔ ⊔ F of a piecewise-testable language L and a finite language F is piecewise-testable. The proof relies on a classic but little-used automata-theoretic characterization of piecewise-testable languages. We also discuss
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bad53184d507d74ad57cd62acbb9f49d
https://hal.archives-ouvertes.fr/hal-02408648
https://hal.archives-ouvertes.fr/hal-02408648
We consider first-order logic over the subword ordering on finite words, where each word is available as a constant. Our first result is that the $\Sigma_1$ theory is undecidable (already over two letters). We investigate the decidability border by c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d1aad3bb73fbe779d768ac13744e762f
Autor:
Antonín Kučera, Philippe Schnoebelen
Publikováno v:
CONCUR
We introduce a generic family of behavioral relations for which the regular equivalence problem (i.e., comparing an arbitrary transition system to some finite-state specification) can be reduced to the model checking problem against simple modal form
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f06954848e80ada4f213241dfbc84ac
Publikováno v:
EXPRESS
The hierarchy of Symbolic Transition Systems, introduced by Henzinger, Majumdar and Raskin, is an elegant classification tool for some families of infinite-state operational models that support some variants of a symbolic “backward closure” verif
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::948f10f0d5d967a8e484e2c3c9946ef1