Results 41 to 50 of about 4,638,570 (374)
Sliding window property testing for regular languages [PDF]
International Symposium on Algorithms and Computation, 2019 We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window $n$ and a stream of symbols. At each time instant, we must
Moses Ganardi +3 more
semanticscholar +1 more source
Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages [PDF]
Logical Methods in Computer Science, 2023 A classic result in formal language theory is the equivalence among non-counting, or aperiodic, regular languages, and languages defined through star-free regular expressions, or first-order logic.
Dino Mandrioli +2 more
doaj +1 more source
Interval type-2 fuzzy automata and Interval type-2 fuzzy grammar [PDF]
, 2021 The purpose of the present work is to introduce and study the concept of interval type-2 (IT2) fuzzy grammar which recognizes the given IT2 fuzzy languages. The relationship between IT2 fuzzy automata and IT2 fuzzy (weak) regular grammars is discussed.
Kavikumar, Jacob +2 more
core +1 more source
Weakly and Strongly Irreversible Regular Languages [PDF]
Electronic Proceedings in Theoretical Computer Science, 2017 Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k, are considered. These devices and their accepted languages are called k-reversible automata and k-reversible languages ...
Giovanna J. Lavado +2 more
doaj +1 more source
On the State Complexity of the Shuffle of Regular Languages [PDF]
Workshop on Descriptional Complexity of Formal Systems, 2015 We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that $f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-1)$ is an upper bound on the state complexity of the shuffle of two ...
J. Brzozowski +4 more
semanticscholar +1 more source
Regular matching problems for infinite trees [PDF]
Logical Methods in Computer Science, 2022 We study the matching problem of regular tree languages, that is, "$\exists \sigma:\sigma(L)\subseteq R$?" where $L,R$ are regular tree languages over the union of finite ranked alphabets $\Sigma$ and $\mathcal{X}$ where $\mathcal{X}$ is an alphabet of ...
Carlos Camino +4 more
doaj +1 more source
Extracting Subregular constraints from Regular stringsets
Journal of Language Modelling, 2019 We introduce algorithms that, given a Finite-State Automaton (FSA), compute a minimal set of forbidden local factors that define a Strictly Local (SL) tight approximation of the stringset recognised by the FSA and the set of forbidden piecewise factors ...
James Rogers, Dakotah Lambert
doaj +1 more source
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
Kleene Algebras, Regular Languages and Substructural Logics [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We introduce the two substructural propositional logics KL, KL+ , which use disjunction, fusion and a unary, (quasi-)exponential connective. For both we prove strong completeness with respect to the interpretation in Kleene algebras and a variant thereof.
Christian Wurm
doaj +1 more source