Results 1 to 10 of about 4,664,026 (360)
Separating Regular Languages with First-Order Logic [PDF]
Logical Methods in Computer Science, 2016 Given two languages, a separator is a third language that contains the first one and is disjoint from the second one. We investigate the following decision problem: given two regular input languages of finite words, decide whether there exists a first ...
Thomas Place, Marc Zeitoun
doaj +7 more sources
Learning Regular Languages over Large Ordered Alphabets [PDF]
Logical Methods in Computer Science, 2015 This work is concerned with regular languages defined over large alphabets, either infinite or just too large to be expressed enumeratively. We define a generic model where transitions are labeled by elements of a finite partition of the alphabet.
Irini-Eleftheria Mens, Oded Maler
doaj +5 more sources
Quotient Complexity of Regular Languages [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 The past research on the state complexity of operations on regular languages is examined, and a new approach based on an old method (derivatives of regular expressions) is presented.
Janusz Brzozowski
doaj +6 more sources
Regular languages and associative language descriptions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 The Associative Language Description model (ALD) is a combination of locally testable and constituent structure ideas. It is consistent with current views on brain organization and can rather conveniently describe typical technical languages such as ...
Marcella Anselmo +2 more
doaj +7 more sources
Boolean Circuit Complexity of Regular Languages [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 In this paper we define a new descriptional complexity measure for Deterministic Finite Automata, BC-complexity, as an alternative to the state complexity.
Maris Valdats
doaj +4 more sources
Testing the Equivalence of Regular Languages [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 The minimal deterministic finite automaton is generally used to determine regular languages equality. Antimirov and Mosses proposed a rewrite system for deciding regular expressions equivalence of which Almeida et al.
Marco Almeida +2 more
doaj +3 more sources
Rate of Escape of Random Walks on Regular Languages and Free Products by Amalgamation of Finite Groups [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 We consider random walks on the set of all words over a finite alphabet such that in each step only the last two letters of the current word may be modified and only one letter may be adjoined or deleted.
Lorenz A. Gilch
doaj +3 more sources
Complexity in Prefix-Free Regular Languages [PDF]
Electronic Proceedings in Theoretical Computer Science, 2010 We examine deterministic and nondeterministic state complexities of regular operations on prefix-free languages. We strengthen several results by providing witness languages over smaller alphabets, usually as small as possible.
Galina Jirásková, Monika Krausová
doaj +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 +4 more sources
Separating regular languages with two quantifier alternations [PDF]
Logical Methods in Computer Science, 2018 We investigate a famous decision problem in automata theory: separation. Given a class of language C, the separation problem for C takes as input two regular languages and asks whether there exists a third one which belongs to C, includes the first one ...
Thomas Place
doaj +3 more sources