BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nelma Moreira

Nelma Moreira appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata TheoryInformation TheoryLogic in Computer Sciencemath.IT

Catalog footprint

What is connected

14works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2022arXiv

Approximate NFA Universality and Related Problems Motivated by Information Theory

In coding and information theory, it is desirable to construct maximal codes that can be either variable length codes or error control codes of fixed length. However deciding code maximality boils down to deciding whether a given NFA is universal, and this is a hard problem (including the case of whether the NFA accepts all words of a fixed length). On the other hand, it is acceptable to know whether a code is `approximately' maximal, which then boils down to whether a given NFA is `approximately' universal. Here we introduce the notion of a $(1-ε)$-universal automaton and present polynomial randomized approximation algorithms to test NFA universality and related hard automata problems, for certain natural probability distributions on the set of words. We also conclude that the randomization aspect is necessary, as approximate universality remains hard for any fixed polynomially computable $ε$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The computational power of parsing expression grammars

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, including the language of palindromes whose length is a power of two, and a binary-counting language. We then propose a new computational model, the scaffolding automaton, and prove that it exactly characterises the computational power of parsing expression grammars (PEGs). Using this characterisation we show that: (*) PEGs have unexpected power and semantics. We present several PEGs with surprising behaviour, and languages which, unexpectedly, have PEGs, including a PEG for the language of palindromes whose length is a power of two. (*) PEGs are computationally `universal', in the following sense: take any computable function $f:\{0,1\}^\ast\to \{0,1\}^\ast$; then there exists a computable function $g: \{0,1\}^\ast \to \mathbb{N}$ such that $\{ f(x) \#^{g(x)} x \mid x \in \{0,1\}^\ast \}$ has a PEG. (*) There can be no pumping lemma for PEGs. There is no total computable function $A$ with the following property: for every well-formed PEG $G$, there exists $n_0$ such that for every string $x \in \mathcal{L}(G)$ of size $|x| \ge n_0$, the output $y = A(G, x)$ is in $\mathcal{L}(G)$ and has $|y| > |x|$. (*) PEGs are strongly non real-time for Turing machines. There exists a language with a PEG, such that neither it nor its reverse can be recognised by any multi-tape online Turing machine which is allowed to do only $o(n/\log n)$ steps after reading each input symbol.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Channels with Synchronization/Substitution Errors and Computation of Error Control Codes

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 maximal with respect to being error-detecting. Our motivation for this is that constructing a maximal error-detecting code is a computationally hard problem. We present a randomized algorithm that takes as input two positive integers $N,\ell$, a probability value \ff, and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code having up to $N$ codewords of length $\ell$. If the algorithm finds less than $N$ codewords, then those codewords constitute a code that is \ff-maximal with high probability. The error specification (also called channel) is modelled as a transducer, which allows one to model any rational combination of substitution and synchronization errors. We also present some elements of our implementation of various error-detecting properties and their associated methods. Then, we show several tests of the implemented randomized algorithm on various channels. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Symbolic Manipulation of Code Properties

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 transducers and we go one level higher than existing formal language systems and implement methods to manipulate objects representing classes of independent languages (widely known as code properties). Our methods allow users to define their own code properties and combine them between themselves or with fixed properties such as prefix codes, suffix codes, error detecting codes, etc. The satisfaction and maximality decision questions are solvable for any of the definable properties. The new online system LaSer allows to query about code properties and obtain the answer in a batch mode. Our work is founded on independence theory as well as the theory of rational relations and transducers and contributes with improveded algorithms on these objects.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Survey on Operational State Complexity

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 the number of states of the smallest, either deterministic or nondeterministic, finite automaton that recognises it. Operational state complexity is the study of the state complexity of operations over languages. In this survey, we review the state complexities of individual regularity preserving language operations on regular and some subregular languages. Then we revisit the state complexities of the combination of individual operations. We also review methods of estimation and approximation of state complexity of more complex combined operations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Formalization of context-free language theory

Context-free language theory is a subject of high importance in computer language processing technology as well as in formal language theory. This paper presents a formalization, using the Coq proof assistant, of fundamental results related to context-free grammars and languages. These include closure properties (union, concatenation and Kleene star), grammar simplification (elimination of useless symbols inaccessible symbols, empty rules and unit rules) and the existence of a Chomsky Normal Form for context-free grammars.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Formalization of the pumping lemma for context-free languages

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 for all context-free languages, and is used to show the existence of non context-free languages. This paper presents a formalization, using the Coq proof assistant, of the Pumping Lemma for context-free languages.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Distinguishability Operations and Closures on Regular Languages

Given a regular language $L$, we study the language of words $\mathsf{D}(L)$, that distinguish between pairs of different left-quotients of $L$. We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators. We give an upper bound for the state complexity of the distinguishability operation, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different left-quotients of a language $L$ has at most $n-1$ elements, where $n$ is the state complexity of $L$, and we also study the properties of its iteration. We generalize the results for the languages of words that distinguish between pairs of different right-quotients and two-sided quotients of a language $L$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Incomplete Transition Complexity of Basic Operations on Finite Languages

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) state and transition complexity on finite languages of boolean operations, concatenation, star, and reversal. For all operations we give tight upper bounds for both description measures. We correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right automaton is larger than the left one. For all binary operations the tightness is proved using family languages with a variable alphabet size. In general the operational complexities depend not only on the complexities of the operands but also on other refined measures.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Symmetric Groups and Quotient Complexity of Boolean Operations

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 languages with quotient complexities m and n, and that the transition semigroups of the minimal deterministic automata accepting L and L' are the symmetric groups S_m and S_n of degrees m and n, respectively. Denote by o any binary boolean operation that is not a constant and not a function of one argument only. For m,n >= 2 with (m,n) not in {(2,2),(3,4),(4,3),(4,4)} we prove that the quotient complexity of LoL' is mn if and only either (a) m is not equal to n or (b) m=n and the bases (ordered pairs of generators) of S_m and S_n are not conjugate. For (m,n)\in {(2,2),(3,4),(4,3),(4,4)} we give examples to show that this need not hold. In proving these results we generalize the notion of uniform minimality to direct products of automata. We also establish a non-trivial connection between complexity of boolean operations and group theory.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Deciding KAT and Hoare Logic with Derivatives

Kleene algebra with tests (KAT) is an equational system for program verification, which is the combination of Boolean algebra (BA) and Kleene algebra (KA), the algebra of regular expressions. In particular, KAT subsumes the propositional fragment of Hoare logic (PHL) which is a formal system for the specification and verification of programs, and that is currently the base of most tools for checking program correctness. Both the equational theory of KAT and the encoding of PHL in KAT are known to be decidable. In this paper we present a new decision procedure for the equivalence of two KAT expressions based on the notion of partial derivatives. We also introduce the notion of derivative modulo particular sets of equations. With this we extend the previous procedure for deciding PHL. Some experimental results are also presented.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Small NFAs from Regular Expressions: Some Experimental Results

Regular expressions (res), because of their succinctness and clear syntax, are the common choice to represent regular languages. However, efficient pattern matching or word recognition depend on the size of the equivalent nondeterministic finite automata (NFA). We present the implementation of several algorithms for constructing small epsilon-free NFAss from res within the FAdo system, and a comparison of regular expression measures and NFA sizes based on experimental results obtained from uniform random generated res. For this analysis, nonredundant res and reduced res in star normal form were considered.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

State Elimination Ordering Strategies: Some Experimental Results

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 regular expressions have an exponential blow-up in the worst-case. To overcome this, simple heuristic methods have been proposed. In this paper we analyse some of the heuristics presented in the literature and propose new ones. We also present some experimental comparative results based on uniform random generated deterministic finite automata.

0 citations0 reviewsNo code linkedOpen access