Zobrazeno 1 - 10
of 19 283
pro vyhledávání: '"Computer Science::Formal Languages and Automata Theory"'
Autor:
James D. Mitchell, Maria Tsalakou
Publikováno v:
Journal of Algebra. 630:394-433
We describe a practical algorithm for computing normal forms for semigroups and monoids with finite presentations satisfying so-called small overlap conditions. Small overlap conditions are natural conditions on the relations in a presentation, which
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7a29b6477ff831abc6ad7b27334a5bc3
https://doi.org/10.1016/j.jalgebra.2023.04.019
https://doi.org/10.1016/j.jalgebra.2023.04.019
Publikováno v:
ACM Transactions on Computational Logic. 24:1-32
In this article, we introduce and investigate an extension of Halpern and Shoham’s interval temporal logic HS for the specification and verification of branching-time context-free requirements of pushdown systems under a state-based semantics over
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::27e90ae665ddc9547bb10b1c9b4739b3
https://doi.org/10.1145/3583756
https://doi.org/10.1145/3583756
Autor:
Nguyen, Linh Anh
Publikováno v:
International Journal of Approximate Reasoning. 155:113-131
Simulations and bisimulations between two fuzzy automata over a complete residuated lattice were defined by \'Ciri\'c et al. (2012) as fuzzy relations between the sets of states of the automata. However, they act as a crisp relationship between the a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0b44b490f28d72e88bbdbb9df2f7ecf8
https://doi.org/10.1016/j.ijar.2023.02.002
https://doi.org/10.1016/j.ijar.2023.02.002
Autor:
Eberbach, Eugene
Publikováno v:
Fundamenta Informaticae. 188:63-90
In the paper we define three new complexity classes for Turing Machine undecidable problems inspired by the famous Cook/Levin’s NP-complete complexity class for intractable problems. These are U-complete (Universal complete), D-complete (Diagonaliz
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1e8e3ec8b1f1909cd3e40e8e35bef0ab
https://doi.org/10.3233/fi-222142
https://doi.org/10.3233/fi-222142
Publikováno v:
LICS
ACM transactions on computational logic
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 29 June-2 July 2021, Rome, Italy
ACM transactions on computational logic
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 29 June-2 July 2021, Rome, Italy
We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper- and lower-bound tests against the counter value. Additionally, the counter updates associated with taking trans
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fd4cfce9df3bbb799429ef6b089fe087
https://doi.org/10.1145/3558549
https://doi.org/10.1145/3558549
Publikováno v:
Theoretical Computer Science. 942:180-199
The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the LCPs for lexicographically adjacent suffixes of a string. Together
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5c50058727f2829de2e2a84a43cc0e45
https://doi.org/10.1016/j.tcs.2022.11.032
https://doi.org/10.1016/j.tcs.2022.11.032
Autor:
Golov, A., Terwijn, Sebastiaan A.
Publikováno v:
Notre Dame Journal of Formal Logic, 64, 1, pp. 129-158
Notre Dame Journal of Formal Logic, 64, 129-158
Notre Dame Journal of Formal Logic, 64, 129-158
Partial combinatory algebras are algebraic structures that serve as generalized models of computation. In this paper, we study embeddings of pcas. In particular, we systematize the embeddings between relativizations of Kleene's models, of van Oosten'
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3acd2edfc8f9aebe7adc41b04d403b95
https://hdl.handle.net/2066/292547
https://hdl.handle.net/2066/292547
Autor:
Gessel, Ira M.
Publikováno v:
Algebraic Combinatorics. 5:1279-1286
Let A be an alphabet and let F be a set of words with letters in A. We show that the sum of all words with letters in A with no consecutive subwords in F, as a formal power series in noncommuting variables, is the reciprocal of a series with all coef
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dddfe10aa77d77b464c6688f2cc6e250
https://doi.org/10.5802/alco.210
https://doi.org/10.5802/alco.210
Autor:
Bowen, Lewis, Burton, Peter
Publikováno v:
Israel Journal of Mathematics. 251:239-270
We introduce the notion of soficity for locally compact groups and list a number of open problems.
Comment: Comments welcome! The new version corrects a few minor errors
Comment: Comments welcome! The new version corrects a few minor errors
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0c1a223a42d407aab83350be6d7bde2c
https://doi.org/10.1007/s11856-022-2431-2
https://doi.org/10.1007/s11856-022-2431-2
Autor:
Cheuk Ting Li
Publikováno v:
ITW
We establish the undecidability of conditional affine information inequalities, the undecidability of the conditional independence implication problem with a constraint that one random variable is binary, and the undecidability of the problem of deci
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7bbfd4c961dcce2391d90ad55934ed7f
https://doi.org/10.1109/tit.2022.3190800
https://doi.org/10.1109/tit.2022.3190800