Zobrazeno 1 - 10
of 100
pro vyhledávání: '"Straubing, Howard"'
Autor:
Krebs, Andreas, Straubing, Howard
We give a simple new proof that regular languages defined by first-order sentences with no quantifier alteration can be defined by such sentences in which only regular atomic formulas appear. Earlier proofs of this fact relied on arguments from circu
Externí odkaz:
http://arxiv.org/abs/2208.10480
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:
http://arxiv.org/abs/1911.03493
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 3 (September 8, 2020) lmcs:5206
We study two extensions of FO2[<], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. We adjoin to this language two-variable atomic formulas that say, "the letter $a$ appears between positions
Externí odkaz:
http://arxiv.org/abs/1902.05905
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:
http://arxiv.org/abs/1812.01921
Autor:
Straubing, Howard
We extend Tilson's theory of the algebra of finite categories, in particular, the Derived Category Theorem, to the setting of forest algebras. As an illustration of the usefulness of this method, we provide a new proof of a result of Place and Segouf
Externí odkaz:
http://arxiv.org/abs/1801.04337
We study an extension of FO^2[<], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. We adjoin to this language two-variable atomic formulas that say, `the letter a appears between positions x a
Externí odkaz:
http://arxiv.org/abs/1603.05625
Autor:
Straubing, Howard, Weil, Pascal
Publikováno v:
Chapter 16 in Handbook of Automata Theory (Jean-Eric Pin ed.), EMS Publishing, 2021
This text is devoted to the theory of varieties, which provides an important tool, based in universal algebra, for the classification of regular languages. In the introductory section, we present a number of examples that illustrate and motivate the
Externí odkaz:
http://arxiv.org/abs/1502.03951
Publikováno v:
In Topology and its Applications 15 March 2020 273
Autor:
Krebs, Andreas, Straubing, Howard
We examine languages of unranked forests definable using the temporal operators EF and EX. We characterize the languages definable in this logic, and various fragments thereof, using the syntactic forest algebras introduced by Bojanczyk and Walukiewi
Externí odkaz:
http://arxiv.org/abs/1408.0809
Publikováno v:
Logical Methods in Computer Science, Volume 8, Issue 3 (September 19, 2012) lmcs:1215
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:
http://arxiv.org/abs/1208.6172