23 citations · 60 across the 17 of their papers we have counts for
19 papers
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…
Channels with Synchronization/Substitution Errors and Computation of Error Control Codes
Stavros Konstantinidis, Nelma Moreira, Rogerio Reis
We introduce the concept of an \ff-maximal error-detecting block code, for some parameter \ff{} between 0 and 1, in order to formalize the situation where a block code is close to…
Formalization of the pumping lemma for context-free languages
Marcus V. M. Ramos, Ruy J. G. B. de Queiroz, Nelma Moreira +1
Context-free languages (CFLs) are highly important in computer language processing technology as well as in formal language theory. The Pumping Lemma is a property that is valid fo…
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…