Zobrazeno 1 - 10
of 80
pro vyhledávání: '"Howard Straubing"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 16, Issue 3 (2020)
We study two extensions of FO2[
Externí odkaz:
https://doaj.org/article/72ce23cd8d964592a9fddf6c83e43836
Publikováno v:
Logical Methods in Computer Science, Vol Volume 8, Issue 3 (2012)
We use the recently developed theory of forest algebras to find algebraic characterizations of the languages of unranked trees and forests definable in various logics. These include the temporal logics CTL and EF, and first-order logic over the ances
Externí odkaz:
https://doaj.org/article/5cdbbadc51304f259610407358ec04a3
Publikováno v:
Logical Methods in Computer Science, Vol Volume 8, Issue 3 (2012)
This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combina
Externí odkaz:
https://doaj.org/article/ae4895d2a3dc472ab3b07208f4d002a9
Autor:
Howard Straubing
Publikováno v:
ACM SIGLOG News. 5:4-20
A fundamental result about formal languages states: Theorem 1 A regular language is first-order definable if and only if its syntactic monoid contains no nontrivial groups. Rest assured, we will explain in the next section exactly what the various te
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e2943ad46578e4ae71e035821b74ec35
https://doi.org/10.1145/3242953.3242956
https://doi.org/10.1145/3242953.3242956
It is an open problem whether definability in Propositional Dynamic Logic (PDL) on forests is decidable. Based on an algebraic characterization by Boja\'nczyk, et. al.,(2012) in terms of forest algebras, Straubing (2013) described an approach to PDL
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9c54158e41dd514097cb3338e92fc373
Publikováno v:
Topology and its Applications
Topology and its Applications, Elsevier, 2019
Topology and its Applications, Elsevier, 2019
The notion of a difference hierarchy, first introduced by Hausdorff, plays an important role in many areas of mathematics, logic and theoretical computer science such as descriptive set theory, complexity theory, and the theory of regular languages a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::09fcf212370a054b8776da7c8a2b01bd
https://hal.science/hal-02413264
https://hal.science/hal-02413264
Autor:
Howard Straubing
Publikováno v:
International Journal of Algebra and Computation. 25:293-300
We give a simple proof of a wreath product decomposition for locally ℛ-trivial finite categories. As immediate consequences we obtain two classic results of Stiffler on the decomposition of ℛ-trivial monoids and locally ℛ-trivial semigroups. A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6cebe145d10ba5774d972896ec4eac5b
https://doi.org/10.1142/s0218196715400111
https://doi.org/10.1142/s0218196715400111
Autor:
Howard Straubing
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 47:261-291
We give several new applications of the wreath product of forest algebras to the study of logics on trees. These include new simplified proofs of necessary conditions for definability in CTL and first-order logic with the ancestor relation; a sequenc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1f2620dfb5a324573c2370cb888368c9
https://doi.org/10.1051/ita/2013039
https://doi.org/10.1051/ita/2013039
Publikováno v:
LICS
We study an extension of FO2[
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f9c35de4756ad2711f12e8d461e6d1ba
https://doi.org/10.1145/2933575.2935308
https://doi.org/10.1145/2933575.2935308