Zobrazeno 1 - 10
of 28
pro vyhledávání: '"Theory of computation → Regular languages"'
Publikováno v:
Logical Methods in Computer Science. 19
We study the learnability of symbolic finite state automata (SFA), a model shown useful in many applications in software verification. The state-of-the-art literature on this topic follows the query learning paradigm, and so far all obtained results
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b68fbc239ed4dcdecb2c7e7939f179f
https://doi.org/10.46298/lmcs-19(2:5)2023
https://doi.org/10.46298/lmcs-19(2:5)2023
Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n states to 2ⁿ states. In this articl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4fa11efd8cda0aadc031bacda61f8403
A generic polynomial time approach to separation by first-order logic without quantifier alternation
Autor:
Place, Thomas, Zeitoun, Marc
We look at classes of languages associated to fragments of first-order logic BΣ₁, in which quantifier alternations are disallowed. Each such fragment is fully determined by choosing the set of predicates on positions that may be used. Equipping fi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::52a81c62006477965d22d77334c36abc
http://arxiv.org/abs/2210.00946
http://arxiv.org/abs/2210.00946
Autor:
Roussanaly, Victor, Falcone, Yliès
Publikováno v:
TIME 2022-29th International Symposium on Temporal Representation and Reasoning
TIME 2022-29th International Symposium on Temporal Representation and Reasoning, Nov 2022, Online, France. pp.1-18, ⟨10.4230/LIPIcs..12⟩
TIME 2022-29th International Symposium on Temporal Representation and Reasoning, Nov 2022, Online, France. pp.1-18, ⟨10.4230/LIPIcs..12⟩
Ensuring the correctness of distributed cyber-physical systems can be done at runtime by monitoring properties over their behaviour. In a decentralised setting, such behaviour consists of multiple local traces, each offering an incomplete view of the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fe56c6df002833568cc5e13ba9ebc953
Generalizing the notion of the boundary sequence introduced by Chen and Wen, the $n$th term of the $\ell$-boundary sequence of an infinite word is the finite set of pairs $(u,v)$ of prefixes and suffixes of length $\ell$ appearing in factors $uyv$ of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::01156528a7f57244a646bb236e9bd4be
http://arxiv.org/abs/2206.15319
http://arxiv.org/abs/2206.15319
Autor:
Colcombet, Thomas, Jaquard, Arthur
Publikováno v:
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Jul 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.127⟩
Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
International Colloquium on Automata, Languages, and Programming, ICALP
International Colloquium on Automata, Languages, and Programming, ICALP, 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.127⟩
International Colloquium on Automata, Languages, and Programming, ICALP, 2021, Glasgow, United Kingdom. pp.123:1-123:14, ⟨10.4230/LIPIcs.ICALP.2021.127⟩
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Jul 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.127⟩
Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
International Colloquium on Automata, Languages, and Programming, ICALP
International Colloquium on Automata, Languages, and Programming, ICALP, 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.127⟩
International Colloquium on Automata, Languages, and Programming, ICALP, 2021, Glasgow, United Kingdom. pp.123:1-123:14, ⟨10.4230/LIPIcs.ICALP.2021.127⟩
In this paper, we initiate a study of the expressive power of tree algebras, and more generally infinitely sorted algebras, based on their asymptotic complexity. We provide a characterization of the expressiveness of tree algebras of bounded complexi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::73ef028cc856e8bb3f88d5502b43afd5
https://hal.archives-ouvertes.fr/hal-03468263/document
https://hal.archives-ouvertes.fr/hal-03468263/document
Autor:
Pous, Damien, Wagemaker, Jana
Publikováno v:
CONCUR
CONCUR, Sep 2022, Varsovie, Poland. ⟨10.4230/LIPIcs.CONCUR.2022.26⟩
CONCUR, Sep 2022, Varsovie, Poland. ⟨10.4230/LIPIcs.CONCUR.2022.26⟩
We prove two completeness results for Kleene algebra with a top element, with respect to languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra, this is no longer the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::04631926ed9d6abb7765e6cd9fb936c5
https://hal.archives-ouvertes.fr/hal-03644317/document
https://hal.archives-ouvertes.fr/hal-03644317/document
The notion of synchronization of finite automata is connected to one of the long-standing open problems in combinatorial automata theory, which is Černý’s Conjecture. In this paper, we focus on so-called synchronization games. We will discuss how
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ab11e528312c6ad9c2df946111263e70
Autor:
Colcombet, Thomas, Jaquard, Arthur
Publikováno v:
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Aug 2022, Vienna, Austria. pp.1868-8969, ⟨10.4230/LIPIcs.MFCS.2022.37⟩
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Aug 2022, Vienna, Austria. pp.1868-8969, ⟨10.4230/LIPIcs.MFCS.2022.37⟩
In this paper, we consider infinitely sorted tree algebras recognising regular language of finite trees. We pursue their analysis under the angle of their asymptotic complexity, i.e. the asymptotic size of the sorts as a function of the number of var
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d54cdec7fbb609a85a0854b85bb0be6f
Autor:
Shallit, Jeffrey
The first-order theory of automatic sequences with addition is decidable, and this means that one can often prove combinatorial properties of these sequences "automatically", using the free software Walnut written by Hamoon Mousavi. In this talk I wi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::465f96c951a2287543f313994c7ce2af