Results 41 to 50 of about 4,664,026 (360)
A survey on difference hierarchies of regular languages [PDF]
Logical Methods in Computer Science, 2018 Difference hierarchies were originally introduced by Hausdorff and they play an important role in descriptive set theory. In this survey paper, we study difference hierarchies of regular languages.
Olivier Carton +2 more
doaj +1 more source
Odometers on Regular Languages [PDF]
Theory of Computing Systems, 2005 Odometers or "adding machines" are usually introduced in the context of positional numeration systems built on a strictly increasing sequence of integers. We generalize this notion to systems defined on an arbitrary infinite regular language. In this latter situation, if (A,
Berthé,, Rigo, Michel
openaire +2 more sources
Parallelisable Regular Languages [PDF]
IOP Conference Series: Materials Science and Engineering, 2021 Abstract In this paper, we have defined Parallelisable strings and languages in order to reduce the recognition time of strings. Parallelisable languages have been introduced and their recognition has been studied through parallelisable finite automaton.
N Mohana +2 more
openaire +1 more source
Regular Languages of Thin Trees
Theory of Computing Systems, 2016 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.
Mikolaj Bojanczyk +2 more
semanticscholar +1 more source
Efficient and Generalized Decentralized Monitoring of Regular Languages [PDF]
Formal Techniques for (Networked and) Distributed Systems, 2014 This paper proposes an efficient and generalized decentralized monitoring algorithm allowing to detect satisfaction or violation of any regular specification by local monitors alone in a system without central observation point.
Tom Cornebize, Yliès Falcone
semanticscholar +1 more source
On regular languages over power sets
Journal of Language Modelling, 2016 The power set of a finite set is used as the alphabet of a string interpreting a sentence of Monadic Second-Order Logic so that the string can be reduced (in a straightforward way) to the symbols occurring in the sentence.
Tim Fernando
doaj +1 more source
On Learning Nominal Automata with Binders [PDF]
Electronic Proceedings in Theoretical Computer Science, 2019 We investigate a learning algorithm in the context of nominal automata, an extension of classical automata to alphabets featuring names. This class of automata captures nominal regular languages; analogously to the classical language theory, nominal ...
Yi Xiao, Emilio Tuosto
doaj +1 more source
On the Problem of Computing the Probability of Regular Sets of Trees [PDF]
, 2015 We consider the problem of computing the probability of regular languages of infinite trees with respect to the natural coin-flipping measure. We propose an algorithm which computes the probability of languages recognizable by \emph{game automata}.
Michalewski, Henryk, Mio, Matteo
core +5 more sources
Power of Randomization in Automata on Infinite Strings [PDF]
Logical Methods in Computer Science, 2011 Probabilistic B\"uchi Automata (PBA) are randomized, finite state automata that process input strings of infinite length. Based on the threshold chosen for the acceptance probability, different classes of languages can be defined.
Rohit Chadha +2 more
doaj +1 more source
Query learning of derived $\omega$-tree languages in polynomial time [PDF]
Logical Methods in Computer Science, 2019 We present the first polynomial time algorithm to learn nontrivial classes of languages of infinite trees. Specifically, our algorithm uses membership and equivalence queries to learn classes of $\omega$-tree languages derived from weak regular $\omega ...
Dana Angluin +2 more
doaj +1 more source