Results 11 to 20 of about 1,772,421 (241)
Theoretical Computer Science, 1988 AbstractThis paper is a continuation of [3]. It gives some further properties of limited regular languages and partial solutions to two of S. Eilenberg's open problems [2, p. 158].
Yi-li Zhang, Changjie Tang
openaire +2 more sources
, 2022 We introduce regular languages of morphisms in free monoidal categories, with their associated grammars and automata. These subsume the classical theory of regular languages of words and trees, but also open up a much wider class of languages over string diagrams.
Earnshaw, Matthew, Sobociński, Paweł
openaire +4 more sources
A Trichotomy for Regular Simple Path Queries on Graphs [PDF]
, 2012 Regular path queries (RPQs) select nodes connected by some path in a graph. The edge labels of such a path have to form a word that matches a given regular expression.
Bagan, Guillaume +2 more
core +2 more sources
Regular Languages of Thin Trees [PDF]
Theory of Computing Systems, 2015 An infinite tree is called thin if it contains only countably many infinite branches. Thin trees can be seen as intermediate structures between infinite words and infinite trees. In this work we investigate properties of regular languages of thin trees. Our main tool is an algebra suitable for thin trees. Using this framework we characterize various
Bojanczyk, Mikolaj +2 more
openaire +5 more sources
Separation Property for wB- and wS-regular Languages [PDF]
, 2014 In this paper we show that {\omega}B- and {\omega}S-regular languages satisfy the following separation-type theorem If L1,L2 are disjoint languages of {\omega}-words both recognised by {\omega}B- (resp.
Skrzypczak, Michał
core +1 more source
Extensions of ω-Regular Languages [PDF]
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020 We consider extensions of monadic second-order logic over ω-words, which are obtained by adding one language that is not ω-regular. We show that if the added language L has a neutral letter, then the resulting logic is necessarily undecidable. A corollary is that the ω-regular languages are the only decidable Boolean-closed full trio over ω-words.
Bojańczyk, Mikołaj +3 more
openaire +3 more sources
The rationality of Sol manifolds [PDF]
, 2005 Let $\Gamma$ be the fundamental group of a manifold modeled on three dimensional Sol geometry. We prove that $\Gamma$ has a finite index subgroup $G$ which has a rational growth series with respect to a natural generating set.
Andrew Putman +17 more
core +6 more sources
On the Boundary of Regular Languages
Theoretical Computer Science, 2013 We prove that the tight bound on the state complexity of the boundary of regular languages, defined as bd ( L ) = L * ? ( L ? ) * , is 3 / 8 ? 4 n + 2 n - 2 - 2 ? 3 n - 2 - n + 2 . Our witness languages are described over a five-letter alphabet. Next, we show that this bound cannot be met by any quaternary language if n ? 5 .
Galina Jirásková, Jozef Jirásek
openaire +3 more sources
On Notions of Regularity for Data Languages [PDF]
Theoretical Computer Science, 2007 AbstractWith motivation from considerations in XML database theory and model checking, data strings have been introduced as an extension of finite alphabet strings which carry, at each position, a symbol and a data value from an infinite domain. Previous work has shown that it is difficult to come up with an expressive yet decidable automaton model for
Thomas Schwentick, Henrik Björklund
openaire +2 more sources
Journal of Computer and System Sciences, 1992 AbstractWe give several characterizations, in terms of formal logic, semigroup theory, and operations on languages, of the regular languages in the circuit complexity class AC0, thus answering a question of Chandra, Fortune, and Lipton. As a by-product, we are able to determine effectively whether a given regular language is in AC0 and to solve in part
Mix Barrington, David A. +3 more
openaire +3 more sources