23 citations · 51 across the 17 of their papers we have counts for
18 papers · 1 filter
Operational State Complexity of Block Languages
Guilherme Duarte, Nelma Moreira, Luca Prigioniero +1
In this paper we consider block languages, namely sets of words having the same length, and study the deterministic and nondeterministic state complexity of several operations on t…
On the Representation and State Complexity of Block Languages
Guilherme Duarte, Nelma Moreira, Luca Prigioniero +1
In this paper, we consider block languages, namely sets of words having the same length, and we propose a new representation for these languages. In particular, given an alphabet o…
On the Uniform Distribution of Regular Expressions
Sabine Broda, António Machiavelo, Nelma Moreira +1
Although regular expressions do not correspond univocally to regular languages, it is still worthwhile to study their properties and algorithms. For the average case analysis one o…
The computational power of parsing expression grammars
Bruno Loff, Nelma Moreira, Rogério Reis
We study the computational power of parsing expression grammars (PEGs). We begin by constructing PEGs with unexpected behaviour, and surprising new examples of languages with PEGs,…
Regular Expressions and Transducers over Alphabet-invariant and User-defined Labels
Stavros Konstantinidis, Nelma Moreira, Rogerio Reis +1
We are interested in regular expressions and transducers that represent word relations in an alphabet-invariant way---for example, the set of all word pairs u,v where v is a prefix…
A Survey on Operational State Complexity
Yuan Gao, Nelma Moreira, Rogério Reis +1
Descriptional complexity is the study of the conciseness of the various models representing formal languages. The state complexity of a regular language is the size, measured by th…
Symbolic Manipulation of Code Properties
Stavros Konstantinidis, Casey Meijer, Nelma Moreira +1
The FAdo system is a symbolic manipulator of formal languages objects, implemented in Python. In this work, we extend its capabilities by implementing methods to manipulate transdu…
Partial Derivative Automaton for Regular Expressions with Shuffle
Sabine Broda, António Machiavelo, Nelma Moreira +1
We generalize the partial derivative automaton to regular expressions with shuffle and study its size in the worst and in the average case. The number of states of the partial deri…
Statistical Study On The Number Of Injective Linear Finite Transducers
Ivone Amorim, António Machiavelo, Rogério Reis
The notion of linear finite transducer (LFT) plays a crucial role in some cryptographic systems. In this paper we present a way to get an approximate value, by random sampling, for…
Distinguishability Operations and Closures on Regular Languages
Cezar Câmpeanu, Nelma Moreira, Rogério Reis
Given a regular language , we study the language of words , that distinguish between pairs of different left-quotients of . We characterize this distinguishabi…
Symmetric Groups and Quotient Complexity of Boolean Operations
Jason Bell, Janusz Brzozowski, Nelma Moreira +1
The quotient complexity of a regular language L is the number of left quotients of L, which is the same as the state complexity of L. Suppose that L and L' are binary regular langu…
Incomplete Transition Complexity of Basic Operations on Finite Languages
Eva Maia, Nelma Moreira, Rogério Reis
The state complexity of basic operations on finite languages (considering complete DFAs) has been in studied the literature. In this paper we study the incomplete (deterministic) s…
Small NFAs from Regular Expressions: Some Experimental Results
Hugo Gouveia, Nelma Moreira, Rogério Reis
Regular expressions (res), because of their succinctness and clear syntax, are the common choice to represent regular languages. However, efficient pattern matching or word recogni…
State Elimination Ordering Strategies: Some Experimental Results
Nelma Moreira, Davide Nabais, Rogério Reis
Recently, the problem of obtaining a short regular expression equivalent to a given finite automaton has been intensively investigated. Algorithms for converting finite automata to…
Exact generation of acyclic deterministic finite automata
Marco Almeida, Nelma Moreira, Rogério Reis
We give a canonical representation for trim acyclic deterministic finite automata (Adfa) with n states over an alphabet of k symbols. Using this normal form, we present a backtrack…
Testing the Equivalence of Regular Languages
Marco Almeida, Nelma Moreira, Rogério Reis
The minimal deterministic finite automaton is generally used to determine regular languages equality. Antimirov and Mosses proposed a rewrite system for deciding regular expression…
Aspects of enumeration and generation with a string automata representation
Marco Almeida, Nelma Moreira, Rogério Reis
In general, the representation of combinatorial objects is decisive for the feasibility of several enumerative tasks. In this work, we show how a (unique) string representation for…
On the Representation of Finite Automata
Rogério Reis, Nelma Moreira, Marco Almeida
We give an unique string representation, up to isomorphism, for initially connected deterministic finite automata (ICDFAs) with n states over an alphabet of k symbols. We show how…