Zobrazeno 1 - 10
of 1 558
pro vyhledávání: '"Nested word"'
Regular nested word languages (a.k.a. visibly pushdown languages) strictly extend regular word languages, while preserving their main closure and decidability properties. Previous works have shown that considering languages of 2-nested words, i.e. wo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9c38c60bb00b195bfc821c59714e5920
http://arxiv.org/abs/2208.10347
http://arxiv.org/abs/2208.10347
Publikováno v:
Theoretical Computer Science. 774:82-94
In this paper, we study the model checking problem of pushdown systems for projection temporal logic (PTL), an interval-based temporal logic that is as expressive as the full regular languages. For this, we provide an algorithm to decide whether a pu
Autor:
Jean-Marc Talbot, Emmanuel Filiot, Frédéric Servais, Pierre-Alain Reynier, Jean-François Raskin
Publikováno v:
Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2018, 97, pp.147-181. ⟨10.1016/j.jcss.2018.05.002⟩
Journal of Computer and System Sciences, 2018, 97, pp.147-181. ⟨10.1016/j.jcss.2018.05.002⟩
Journal of Computer and System Sciences, Elsevier, 2018, 97, pp.147-181. ⟨10.1016/j.jcss.2018.05.002⟩
Journal of Computer and System Sciences, 2018, 97, pp.147-181. ⟨10.1016/j.jcss.2018.05.002⟩
Visibly pushdown transducers ( VPT ) extend visibly pushdown automata (VPA) with outputs. They read nested words, i.e. finite words on a structured alphabet partitioned into call, return and internal symbols, and produce output words, which are not n
Autor:
Joachim Niehren, Momar Sakho
Publikováno v:
Algorithms
Algorithms, 2021, ⟨10.3390/a14030068⟩
Algorithms, MDPI, 2021, ⟨10.3390/a14030068⟩
Volume 14
Issue 3
Algorithms, Vol 14, Iss 68, p 68 (2021)
Algorithms, 2021, ⟨10.3390/a14030068⟩
Algorithms, MDPI, 2021, ⟨10.3390/a14030068⟩
Volume 14
Issue 3
Algorithms, Vol 14, Iss 68, p 68 (2021)
International audience; We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions (NREs) from the usual XPath benchmark to nested word automata (NWAs). The determ
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::100b8c172d18de85afda9db560bbf1f2
https://inria.hal.science/hal-03134596/document
https://inria.hal.science/hal-03134596/document
Publikováno v:
Computer Aided Verification ISBN: 9783030816872
CAV (2)
CAV (2)
The problem of model checking procedural programs has fostered much research towards the definition of temporal logics for reasoning on context-free structures. The most notable of such results are temporal logics on Nested Words, such as CaRet and N
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::251694277db76ddab23ec176cc9a6e77
http://hdl.handle.net/11311/1183241
http://hdl.handle.net/11311/1183241
Publikováno v:
CSR 2020-15th International Computer Science Symposium in Russia
CSR 2020-15th International Computer Science Symposium in Russia, Jun 2020, Ekaterinburg, Russia
Computer Science – Theory and Applications ISBN: 9783030500252
CSR
15th International Computer Science Symposium in Russia
15th International Computer Science Symposium in Russia, Jul 2020, Ekaterinburg, Russia
CSR 2020-15th International Computer Science Symposium in Russia, Jun 2020, Ekaterinburg, Russia
Computer Science – Theory and Applications ISBN: 9783030500252
CSR
15th International Computer Science Symposium in Russia
15th International Computer Science Symposium in Russia, Jul 2020, Ekaterinburg, Russia
International audience; We study the problem of whether regular expressions for nested words can be compiled to small deterministic nested word au-tomata (NWAs). In theory, we obtain a positive answer for small deter-ministic regular expressions for
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::666863aed71b61694903be57ad7ee7a1
https://hal.inria.fr/hal-02532706
https://hal.inria.fr/hal-02532706
Publikováno v:
Combinatorial Optimization and Applications ISBN: 9783030648428
COCOA
COCOA
Multi-matching nested relation consists of a sequence of linearly ordered positions, call, internal, and return, augmented with one-to-one, one-to-n or n-to-one matching nested edges from call to return. After word encoding by introducing tagged lett
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::29ec25f4e35ae1b8b639f65b6f2d841b
https://doi.org/10.1007/978-3-030-64843-5_22
https://doi.org/10.1007/978-3-030-64843-5_22
Autor:
Friedrich Otto, Kent Kwee
Publikováno v:
Information and Computation. 259:277-302
Stateless deterministic ordered restarting automata accept exactly the regular languages. Here we study the descriptional complexity of these automata, taking the size of the tape alphabet as the complexity measure. We present a construction that tur
Publikováno v:
Journal of Computer and System Sciences. 90:99-114
We study the size-cost of Boolean operations on constant height nondeterministic pushdown automata, i.e. on pushdown automata with a constant limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the ex
Autor:
Namit Chaturvedi, Marcus Gelderie
Publikováno v:
Information and Computation. 256:23-34
We address the problem of providing a Borel-like classification of languages of infinite Mazurkiewicz traces, and provide a solution in the framework of ω -automata over infinite words – which is invoked via the sets of linearizations of infinitar