Rogério Reis


Err and err and err again, but less and less and less.


Publications

[167] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Location automata for synchronized shuffle expressions. Journal of Logical and Algebraic Methods in Programming, (132):100847, 2023. [ DOI ]
Several notions of synchronisation in concurrent systems can be modelled by regular shuffle operators. In this paper we consider regular expressions extended with three operators corresponding respectively to strong, arbitrary, and weak synchronisation. For these expressions, we define a location based position automaton. Furthermore, we show that the partial derivative automaton is still a quotient of the position automaton.
[166] Stavros Konstantinidis, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average complexity of partial derivative transducers. Theoretical Computer Science, page 113830, 2023. [ DOI ]
2D regular expressions represent rational relations over two alphabets Sigma and DElta. In standard 2D expressions (S2D-RE) the basic terms are generators of Sigma*xDelta*, while in generalised 2D expressions (2D-RE) the basic terms are pairs of (ordinary) regular expressions over one alphabet (1D). In this paper we study the average state complexity of partial derivative standard transducers (TPD) for both S2D-RE and 2D-RE. For S2D-RE we obtain the same asymptotic bounds as for partial derivative automata. For 2D-RE, while in the worst case the number of states of TPD can be O(n^2), where n is the size of the expression, asymptotically and on average that value is bounded from above by O(n^(3/2)). We also show that asymptotically and on average the alphabetic size of a 2D-RE is half of its size. All results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. In particular, we generalise the methods developed in previous work to a broad class of analytic function
[165] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Average complexity of partial derivatives for synchronised shuffle expressions. In Benedek Nagy, editor, Implementation and Application of Automata - 27th International Conference, CIAA 2023, Famagusta, North Cyprus, September 19-22, 2023, Proceedings, volume 14151 of Lecture Notes in Computer Science, pages 103--115. Springer, 2023. [ DOI | http ]
Synchronised shuffle operators allow to specify symbols on which the operands must or can synchronise instead of interleave. Recently, partial derivative and position based automata for regular expressions with synchronised shuffle operators were introduced. In this paper, using the framework of analytic combinatorics, we study the asymptotic average state complexity of partial derivative automata for regular expressions with strongly and arbitrarily synchronised shuffles. The new results extend and improve the ones previously obtained for regular expressions with shuffle and intersection. For intersection, asymptotically the average state complexity of the partial derivative automaton is 3, which significantly improves the known exponential upper-bound.
[164] Nelma Moreira and Rogério Reis. Special issue: 25th international conference on developments in language theory (DLT 2021) - preface. Int. J. Found. Comput. Sci., 34(2&3):81--83, 2023. [ DOI | http ]
[163] Stavros Konstantinidis, Mitja Mastnak, Nelma Moreira, and Rogério Reis. Approximate nfa universality and related problems motivated by information theory. Theoretical Computer Science, page 114076, 2023. [ DOI ]
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-epsilon)-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 epsilon.
Keywords: NFA universality, approximation, randomized algorithm, PSPACE hard
[162] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Location based automata for expressions with shuffle and intersection. Information and Computation, 2022. [ DOI ]
We define the notion of location for regular expressions with shuffle by extending the notion of position in standard regular expressions. Locations allow for the definition of the sets Follow, First, and Last with their usual semantics. From these, we construct an automaton for regular expressions with shuffle (apos), which generalises the standard position/Glushkov automaton. The sets mentioned above are also the foundation for other constructions, such as the Follow automaton, and automata based on pointed expressions. As a consequence, all these constructions can be generalised to the shuffle operator. We show that the partial derivative automaton is a right-quotient of apos. We relate apos with another automaton construction based on positions that has been previously studied (apartialpos). The prefix automaton is extended to the shuffle operator and shown not to be a quotient of apos. Locations are also used to define a position automaton for regular expressions with the intersection.
[161] Nelma Moreira and Rogério Reis. Manipulation of regular expressions using derivatives: An overview. In Pascal Caron and Ludovic Mignot, editors, Implementation and Application of Automata - 26th International Conference, CIAA 2022, Rouen, France, June 28 - July 1, 2022, Proceedings, volume 13266 of LNCS, pages 19--33. Springer, 2022. [ DOI | .pdf ]
The notions of derivative and partial derivative of regular expressions revealed themselves to be very powerful and have been successfully extended to many other formal language classes and algebraic structures. Although the undisputed elegance of this formalism, its efficient practical use is still a challenging research topic. Here we give a brief historical overview and summarise some of these aspects.
[160] Stavros Konstantinidis, Mitja Mastnak, Nelma Moreira, and Rogério Reis. Approximate NFA universality motivated by information theory. In Yo-Sub Han and György Vaszil, editors, Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Debrecen, Hungary, August 29-31, 2022, Proceedings, volume 13439 of LNCS, pages 142--154. Springer, 2022. [ DOI ]
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-e)-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 e.
[159] Sabine Broda, Eva Maia, Nelma Moreira, and Rogério Reis. The prefix automaton. Journal of Automata, Languages and Combinatorics, 26:17--53, 2021. [ DOI ]
There are many different constructions when converting regular expressions to finite automata. In this paper we focus on the prefix automaton APRE introduced by Yamamoto in 2014. We present two different methods for the construction of APRE. First, an inductive one, based on a system of expression equations. A second one using an iterative function for computing the states and transitions. We establish relationships between APRE and other constructions, such as the position automaton, partial derivative automaton and their double reversal (dual) counterparts. We study the average size of these constructions, both experimentally and from an analytic combinatorics point of view. Finally, we extend the construction of the prefix automaton to regular expressions with intersection and show that the relationships with the other automaton constructions also hold for these expressions.
[158] Stavros Konstantinidis, Nelma Moreira, and Rogério Reis. Partial derivatives of regular expressions over alphabet-invariant and user-defined labels. Theoretical Computer Science, 31(08):983--1019, 2021. [ DOI ]
We are interested in regular expressions that represent word relations in an alphabet-invariant way---for example, the set of all word pairs (u,v) where v is a prefix of u independently of what the alphabet is. Current software systems of formal language objects do not have a mechanism to define such objects. Labelled graphs (transducers and automata) with alphabet-invariant and user-defined labels were considered in a recent paper. In this paper we study derivatives of regular expressions over labels (atomic objects) in some set B. These labels can be any strings as long as the strings represent subsets of a certain monoid. We show that the number of partial derivatives of any type B regular expression is linearly bounded, and that one can define partial derivative labelled graphs, whose transition labels can be elements of another label set X as long as X and B refer to the same monoid. We also show how to use derivatives directly to decide whether a given word is in the language of a regular expression over set specs. Set specs and pairing specs are label sets allowing one to express languages and relations over large alphabets in a natural and concise way such that many algorithms work directly on these labels without the need to expand these labels to linear or quadratic size expressions.
[157] Martin Kutrib, Nelma Moreira, Giovanni Pighizzini, and Rogério Reis. Hot current topics of descriptional complexity. In Michael Goedicke, Erich Neuhold, and Kai Rannenberg, editors, IFIP Anniversary AICTAdvancing Research in Information and Communication Technology - IFIP's Exciting First 60+ Years, Views from the Technical Committees and Working Groups, IFIP Advances in Information and Communication Technology, pages 3--28. Springer, 2021. [ DOI ]
[156] A. Machiavelo, R. Reis, and N. Tsopanidis. Report on Zhì-Wěi Sun's 1-3-5 conjecture and some of its refinements. Journal of Number Theory, 2021. [ DOI ]
We report here on the computational verification of a re-finement of Zhì-Wěi Sun's “1-3-5 conjecture” for all natural numbers upto 105 103 560 126. This, together with a result of two of the authors,completes the proof of that conjecture.
[155] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Location based automata for expressions with shuffle. In A. Leporati, C. Martín-Vide, D. Shapira, and C. Zandron, editors, LATA 2021: 15th International Conference on Language and Automata Theory and Applications, LATA 2021, Milan, Italy, March 1--5, 2021, Proceedings, volume 12638 of Lecture Notes in Computer Science, pages 43--54. Springer, 2021. [ DOI ]
We define the notion of location for regular expressions with shuffle by extending the notion of position in standard regular expressions. Locations allow for the definition of the sets Follow, First and Last with their usual semantics. From these, we construct an automaton for regular expressions with shuffle (apos), which generalises the standard position/Glushkov automaton. The sets mentioned above are also the foundation for other constructions, such as the Follow automaton, and automata based on pointed expressions. As a consequence, all these constructions can now be directly generalised to regular expressions with shuffle, as well as their known relationships. We also show that the partial derivative automaton (apd) is a (right) quotient of the new position automaton, apos. In previous work an automaton construction based on positions was studied (adpos), and here we relate apos and adpos. Finally, we extend the construction of the prefix automaton to the shuffle operator and show that it is not a quotient of apos.
[154] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the uniform distribution of regular expressions. CORR, abs/2102.07504, 2021. [ arXiv | http ]
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 often relies on the uniform random generation using a specific grammar for regular expressions, that can represent regular languages with more or less redundancy. Generators that are uniform on the set of expressions are not necessarily uniform on the set of regular languages. Nevertheless, it is not straightforward that asymptotic estimates obtained by considering the whole set of regular expressions are different from those obtained using a more refined set that avoids some large class of equivalent expressions. In this paper we study a set of expressions that avoid a given absorbing pattern. It is shown that, although this set is significantly smaller than the standard one, the asymptotic average estimates for the size of the Glushkov automaton for these expressions does not differ from the standard case.
[153] Stavros Konstantinidis, António Machiavelo, Nelma Moreira, and Rogério Reis. On the size of partial derivatives and the word membership problem. Acta Informatica, 58(4):357--375, 2021. [ DOI ]
Partial derivatives are widely used to convert regular expressions to nondeterministic automata. For the word membership problem, it is not strictly necessary to build an automaton. In this paper, we study the size of partial derivatives on the average case. For expressions in strong star normal form, we show that on average and asymptotically the largest partial derivative is at most half the size of the expression. The results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. Our average case estimates suggest that a detailed word membership algorithm based directly on partial derivatives should be analysed both theoretically and experimentally.
[152] Nelma Moreira and Rogério Reis, editors. Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings, volume 12811 of Lecture Notes in Computer Science. Springer, 2021. ISBN 978-3-030-81507-3. [ DOI ]
[151] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the uniform distribution of regular expressions. In YS. Yan and SK. Ko, editors, Proc. 23rd DCFS 2021, volume 13037 of LNCS, pages 13--25. Springer, 2021. [ DOI ]
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 often relies on the uniform random generation using a specific grammar for regular expressions, that can represent regular languages with more or less redundancy. Generators that are uniform on the set of expressions are not necessarily uniform on the set of regular languages. Nevertheless, it is not straightforward that asymptotic estimates obtained by considering the whole set of regular expressions are different from those obtained using a more refined set that avoids some large class of equivalent expressions. In this paper we study a set of expressions that avoid a given absorbing pattern. It is shown that, although this set is significantly smaller than the standard one, the asymptotic average estimates for the size of the Glushkov automaton for these expressions does not differ from the standard case.
[150] Stavros Konstantinidis, António Machiavelo, Nelma Moreira, and Rogério Reis. Partial derivative automaton by compressing regular expressions. In YS. Yan and SK. Ko, editors, Proc. 23rd DCFS 2021, volume 13037 of LNCS, pages 100--112. Springer, 2021. [ DOI ]
The partial derivative automaton (apd) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton (apos), the algorithms that build apd in quadratic worst-case time, first compute apos. Asymptotically, and on average for the uniform distribution, the size of apd is half the size of apos, being both linear on the size of the expression. We address the construction of apd efficiently, on average, avoiding the computation of apos. The expression and the set of its partial derivatives are represented by a directed acyclic graph with shared common subexpressions. We develop an algorithm for building apd's from expressions in strong star normal form of size n that runs in time O(n^3/2sqrt[4]log(n)) and space O(n^3/2/(log n)^3/4), on average. Empirical results corroborate its good practical performance.
[149] Bruno Loff, Nelma Moreira, and Rogério Reis. The computational power of parsing expression grammars. Journal of Computer and System Sciences, 111:1--21, August 2020. [ DOI | http ]
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). Several consequences will follow from this characterisation: (1) we show that PEGs are computationally “universal”, in a certain sense, which implies the existence of a PEG for a P-complete language; (2) we show that there can be no pumping lemma for PEGs; and (3) we show that PEGs are strictly more powerful than online Turing machines which do o(n/(log n)^2) steps of computation per input symbol.
[148] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Analytic combinatorics and descriptional complexity of regular languages on average. ACM SIGACT News, 51(1):38--56, March 2020. [ DOI | http ]
Average-case complexity results provide important information about computational models and methods, as worst-case scenarios usually occur for a negligible amount of cases. The frame- work of analytic combinatorics provides an elegant tool for that analysis, completely avoiding the use of statistical methods, by relating combinatorial objects to algebraic properties of complex analytic generating functions. We have previously used this framework to study the average size of different nondeterministic finite automata simulations of regular expressions. In some cases it was not feasible to obtain explicit expressions for the generating functions involved, and we had to resort to Puiseux expansions. This is particularly important when dealing with families of generating functions indexed by a parameter, e.g. the size of underlying alphabets, and when the corresponding generating functions are obtained by algebraic curves of degree higher than two. In this paper we expound our approach in a tutorial pace, providing sufficient details to make it available to the reader. Corrigendum: In formula (7) a 4 is missing in the denominator; so 4 should be removed from (8). We thank M. Wallner fo hthe correction.
[147] Stavros Konstantinidis, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average state complexity of partial derivative transducers. In Alexander Chatzigeorgiou, Riccardo Dondi, Herodotos Herodotou, Christos A. Kapoutsis, Yannis Manolopoulos, George A. Papadopoulos, and Florian Sikora, editors, SOFSEM 2020: 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20-24, 2020, Proceedings, volume 12011 of Lecture Notes in Computer Science, pages 174--186. Springer, 2020. [ DOI | http ]
2D regular expressions represent rational relations over two alphabets. In this paper we study the average state complexity of partial derivative standard transducers (tpd) that can be defined for (general) 2D expressions where basic terms are pairs of ordinary regular expressions (1D). While in the worst case the number of states of tpd can be O(n^2), where n is the size of the expression, asymptotically and on average that value is bounded from above by O(n^3/2). Moreover, asymptotically and on average the alphabetic size of a 2D expression is half of the size of that expression. All results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. In particular, we generalise the methods developed in previous work to a broad class of analytic functions.
[146] Stavros Konstantinidis, Nelma Moreira, Rogério Reis, and Joshua Young. Regular expressions and transducers over alphabet-invariant and user-defined labels. International Journal of Foundations of Computer Science, 31(8):983--1019, 2020. [ DOI | http ]
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 of u independently of what the alphabet is. Current software systems of formal language objects do not have a mechanism to define such objects. We define transducers in which transition labels involve what we call set specifications, some of which are alphabet invariant. In fact, we give a more broad definition of automata-type objects, called labelled graphs, where each transition label can be any string, as long as that string represents a subset of a certain monoid. Then, the behaviour of the labelled graph is a subset of that monoid. We do the same for regular expressions. We obtain extensions of a few classic algorithmic constructions on ordinary regular expressions and transducers at the broad level of labelled graphs and in such a way that the computational efficiency of the extended constructions is not sacrificed. For transducers with set specs we obtain further algorithms that can be applied to questions about independent regular languages, as well as a decision question about synchronous transducers.
[145] Sabine Broda, Markus Holzer, Eva Maia, Nelma Moreira, and Rogério Reis. Mesh of automata. Information and Computation, 265:94--111, 2019. [ DOI | .pdf ]
We contribute new relations to the taxonomy of different conversions from regular expressions to equivalent finite automata. In particular, we are interested in transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton (Apos), and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version Aposr of the position automaton which plays a similar role as Apos but now for the reverse expression. Moreover, it turns out that the prefix automaton Apre is central to reverse expressions, because the determinisation of the double reversal of Apre (first reverse the expression, construct the automaton Apre, and then reverse the automaton) can be represented as a quotient of any of the considered deterministic automata that we consider in this investigation. This shows that although the conversion of regular expressions and reversal of regular expressions to finite automata seems quite similar, there are significant differences.
[144] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On average behaviour of regular expressions in strong star normal form. International Journal of Foundations of Computer Science, 30(6--7):899--920, 2019. [ DOI | .pdf ]
For regular expressions in (strong) star normal form a large set of efficient algorithms is known, from conversions into finite automata to characterisations of unambiguity. In this paper we study the average complexity of this class of expressions using analytic combinatorics. As it is not always feasible to obtain explicit expressions for the generating functions involved, here we show how to get the required information for the asymptotic estimates with an indirect use of the existence of Puiseux expansions at singularities. We study, asymptotically and on average, the alphabetic size, the size of the epsilon-follow automaton and of the position automaton, as well as the ratio and the size of these expressions to standard regular expressions.
[143] Stavros Konstantinidis, Nelma Moreira, and Rogério Reis. Randomized generation of error control codes with automata and transducers. RAIRO - Theoretical Informatics and Applications, 2019. [ DOI | .pdf ]
We introduce the concept of an f-maximal error-detecting block code, for some parameter f in (0,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 it is computationally hard to decide whether an error-detecting block code is maximal. We present an output-polynomial time randomized algorithm that takes as input two positive integers N,l and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code of length l that is fp-maximal, or contains N words with a high likelihood. We model error specifications as (nondeterministic) transducers, which allow one to represent 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 error specifications. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.
[142] Stavros Konstantinidis, Nelma Moreira, João Pires, and Rogério Reis. Partial derivatives of regular expressions over alphabet-invariant and user-defined labels. In Michal Hospodár and Galina Jirásková, editors, Implementation and Application of Automata - 24th International Conference, CIAA 2019, Košice, Slovakia, July 22-25, 2019, Proceedings, volume 11601 of Lecture Notes in Computer Science, pages 184--196. Springer, 2019. [ DOI | http ]
We are interested in regular expressions that represent word relations in an alphabet-invariant way—for example, the set of all word pairs u, v where v is a prefix of u independently of what the alphabet is. This is the second part of a recent paper on this topic which focused on labelled graphs (transducers and automata) with alphabet-invariant and user-defined labels. In this paper we study derivatives of regular expressions over labels (atomic objects) in some set B. These labels can be any strings as long as the strings represent subsets of a certain monoid. We show that one can define partial derivative labelled graphs of type B expressions, whose transition labels can be elements of another label set X as long as X and B refer to the same monoid. We also show how to use derivatives directly to decide whether a given word pair is in the relation of a regular expression over pairing specs. Set specs and pairing specs are useful label sets allowing one to express languages and relations over large alphabets in a natural and compact way.
[141] António Machiavelo and Rogério Reis. Criptografia e criptoanágeneralise. Revista de Ciência Elementar, 7(4), 2019. [ DOI ]
[140] Sabine Broda, António Machiavelo Nelma Moreira, and Rogério Reis. Automata for regular expressions with shuffle. Information and Computation, 259:162--173, 2018. [ DOI | .pdf ]
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
[139] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Position automata for semi-extended expressions. Journal of Automata, Languages and Combinatorics, 23(1--3):39--65, 2018. [ DOI | .pdf ]
Positions and derivatives are two essential notions in the conversion methods from regular expressions to equivalent finite automata. Partial derivative based methods have recently been extended to regular expressions with intersection (semi-extended). In this paper, we present a position automaton construction for those expressions. This construction generalizes the notion of position, making it compatible with intersection. The resulting automaton is homogeneous and has the partial derivative automaton as a quotient.
[138] Stavros Konstantinidis, Casey Meijer, Nelma Moreira, and Rogério Reis. Symbolic manipulation of code properties. Journal of Automata, Languages and Combinatorics, 23(1--3):243--269, 2018. [ DOI | .pdf ]
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 improved algorithms on these objects.
[137] Miguel Ferreira, Nelma Moreira, and Rogério Reis. Forward injective finite automata: Exact and random generation of nonisomorphic nfas. In Stavros Konstantinidis and Giovanni Pighizzini, editors, Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Halifax, NS, Canada, July 25-27, 2018, Proceedings, volume 10952 of Lecture Notes in Computer Science, pages 88--100. Springer, 2018. [ DOI | .pdf ]
We define the class of forward injective finite automata (FIFA) and study some of their properties. Each FIFA has a unique canonical representation up to isomorphism. Using this representation an enumeration is given and an efficient uniform random generator is presented. We provide a conversion algorithm from a nondeterministic finite automaton or regular expression into an equivalent FIFA. Finally, we present some experimental results comparing the size of FIFA with other automata.
[136] Bruno Loff, Nelma Moreira, and Rogério Reis. The computational power of parsing expression grammars. In Mizuho Hoshi and Shinnosuke Seki, editors, Developements in Language Theory , 22nd International Conference, DLT 2018, number 491--502 in LNCS. Springer, 2018.
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). Several consequences will follow from this characterisation: (1) we show that PEGs are computationally “universal”, in a certain sense, which implies the existence of a PEG for a P-complete language; (2) we show that there can be no pumping lemma for PEGs; and (3) we show that PEGs are strictly more powerful than online Turing machines which do o(n/(log n)^2) steps of computation per input symbol.
[135] Stavros Konstantinidis, Nelma Moreira, Rogério Reis, and Joshua Young. Regular expressions and transducers over alphabet-invariant and user-defined labels. In Cezar Câmpeanu, editor, Implementation and Application of Automata - 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 - August 2, 2018, Proceedings, volume 10977 of Lecture Notes in Computer Science, pages 4--27. Springer, 2018. [ DOI | http ]
[134] Nelma Moreira, Giovanni Pighizzini, and Rogério Reis. Optimal state reductions of automata with partially specified behaviors. Theoretical Computer Science, 658:235--245, January 2017. [ DOI | .pdf ]
Nondeterministic finite automata with don't care states, namely states which neither accept nor reject, are considered. A characterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. It is proved that the problem of minimizing deterministic don't care automata is NP-complete and PSPACE-hard in the nondeterministic case. The restriction to the unary case is also considered.
Keywords: Finite automata; Nondeterminism; Don't care automata; Descriptional complexity
[133] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average complexity of strong star normal form. In Cezar Câmpeanu and Giovanni Pighizzini, editors, Description Complexity of Formal Systems (DCFS 2017), volume 10316 of LNCS, pages 77--88. Springer, 2017. [ DOI | .pdf ]
For regular expressions in (strong) star normal form a large set of efficient algorithms is known, from conversions into finite automata to characterisations of unambiguity. In this paper we study the average complexity of this class of expressions using analytic combinatorics. As it is not always feasible to obtain explicit expressions for the generating functions involved, here we show how to get the required information for the asymptotic estimates with an indirect use of the existence of Puiseux expansions at singularities. We study, asymptotically and on average, the alphabetic size, the size of the varepsilon-follow automaton and the ratio of these expressions to standard regular expressions.
[132] Yuan Gao, Nelma Moreira, Rogério Reis, and Sheng Yu. A survey on operational state complexity. Journal of Automata, Languages and Combinatorics, 21(4):251--310, 2017. [ DOI | .pdf ]
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.
[131] Stavros Konstantinidis, Nelma Moreira, Rogério Reis, and Jeffrey Shallit, editors. The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski. World Scientific, 2017. ISBN 978-981-3148-19-2. [ http ]
[130] Sabine Broda, Markus Holzer, Eva Maia, Nelma Moreira, and Rogério Reis. On the mother of all automata: The position automaton. In Émilie Charlier, Julien Leroy, and Michel Rigo, editors, 21st DLT 2017, volume 10396 of LNCS, pages 134--146. Springer, 2017. [ DOI | .pdf ]
We contribute new relations to the taxonomy of different conversions from regular expressions to equivalent finite automata. In particular, we are interested in ordinary transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton apos, and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version aposr of the position automaton which plays a similar role as apos but now for the reverse expression. It turns out that although the conversion of regular expressions and reversal of regular expressions to finite automata seems quite similar, there are significant differences.
[129] Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the state complexity of partial derivative automata for semi-extended expressions. Journal of Automata, Languages and Combinatorics, 22(1-3):5--28, 2017. [ DOI | .pdf ]
Extended regular expressions (with complement and intersection) are used in many applications due to their succinctness. In particular, regular expressions extended with intersection only (also called semi-extended) can already be exponentially smaller than standard regular expressions or equivalent nondeterministic finite automata. For practical purposes it is important to study the average behaviour of conversions between these models. In this paper, we focus on the conversion of regular expressions with intersection to nondeterministic finite automata, using partial derivatives and the notion of support. We give a tight upper bound of 2^O(n) for the worst-case number of states of the resulting partial derivative automaton, where n is the size of the expression. Using the framework of analytic combinatorics, we establish an upper bound of (1.056 +o(1))^n for its asymptotic average-state complexity, which is significantly smaller than the one for the worst case. Some experimental results here presented suggest that, on average, the upper bound may not be exponential. Finally, we study the class of semi-extended regular expressions with only one occurrence of intersection at the top level. In this case, the worst-case state complexity of the partial derivative automaton is quadratic on the size of the expression, but we obtained an upper-bound that is, asymptotically and on average, O(n^(3/2)).
[128] Stavros Konstantinidis, Nelma Moreira, and Rogério Reis. Channels with synchronization/substitution errors and computation of error control codes. Preprint, 2016. [ http ]
We present a randomized algorithm that takes as input two positive integers N,l and a channel (=specification of the errors permitted), and computes an error-detecting, or -correcting, block code having up to N codewords of length l.The channel could allow any rational combination of substitution and synchronization errors.Moreover, if the algorithm finds less than N codewords then those codewords constitute a code that, with high probability, is close to maximal (in a certain precise sense defined here). We also present some components of an open source Python package in which several code related concepts have been implemented. A methodological contribution is the presentation of how various error combinations can be expressed formally and processed algorithmically.
[127] Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the state complexity of partial derivative automata for regular expressions with intersection. In Proceedings of the 18th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS16), volume 9777 of LNCS, pages 45--59. Springer, 2016. [ DOI | .pdf ]
Extended regular expressions (with complement and intersection) are used in many applications due to their succinctness. In particular, regular expressions extended with intersection only (also called semi-extended) can already be exponentially smaller than standard regular expressions or equivalent nondeterministic finite automata. For practical purposes it is important to study the average behaviour of conversions between these models. In this paper, we focus on the conversion of regular expressions with intersection to nondeterministic finite automata, using partial derivatives and the notion of support. First, we give a tight upper bound of 2^O(n) for the worst-case number of states of the resulting partial derivative automaton, where n is the size of the expression. Using the framework of analytic combinatorics, we then establish an upper bound of (1.056 +o(1))^n for its asymptotic average-state complexity, which is significantly smaller than the one for the worst case.
[126] Stavros Konstantinidis, Casey Meijer, Nelma Moreira, and Rogério Reis. Implementation of code properties via transducers. In Implementation and Application of Automata, 21th International Conference (CIAA 2016), 2016. [ DOI | .pdf ]
The FAdo system is a symbolic manipulator of formal language 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 one to query about a code property 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 improved algorithms on these objects.
[125] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Position automaton construction for regular expressions with intersection. In Srecko Brlek and Christophe Reutenauer, editors, Developments in Language Theory - 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings, volume 9840, pages 51--63, 2016. [ DOI | .pdf ]
Positions and derivatives are two essential notions in the conversion methods from regular expressions to equivalent finite automata. Partial derivative based methods have recently been extended to regular expressions with intersection. In this paper, we present a position automaton construction for those expressions. This construction generalizes the notion of position making it compatible with intersection. The resulting automaton is homogeneous and has the partial derivative automaton as its quotient.
[124] Miguel Ferreira, Nelma Moreira, and Rogério Reis. Automata Serialization for Manipulation and Drawing. In Marjan Mernik, José Paulo Leal, and Hugo Gonçalo Oliveira, editors, 5th Symposium on Languages, Applications and Technologies (SLATE'16), volume 51 of OpenAccess Series in Informatics (OASIcs), pages 1--7, Dagstuhl, Germany, 2016. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. [ DOI | http ]
GUItar is a GPL-licensed, cross-platform, graphical user interface for automata drawing and manipulation, written in C++ and Qt5. This tool offers support for styling, automatic layouts, several format exports and interface with any foreign finite automata manipulation library that can parse the serialized XML or JSON produced. In this paper we describe a new redesign of the GUItar framework and specially the method used to interface GUItar with automata manipulation libraries.
[123] Stavros Konstantinidis, Nelma Moreira, and Rogério Reis. Generating error control codes with automata and transducers. In Henning Bordihn, Rudolf Freund, Benedek Nagy, and György Vaszil, editors, Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016), volume 321, pages 211--226. Österreichische Computer Gesellschaft, 2016. [ .pdf ]
We introduce the concept of an f-maximal error-detecting block code, for some parameter f 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,l, a probability value f, 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 l. If the algorithm finds less than N codewords, then those codewords constitute a code that is -Maximalf with high probability. The error specification is modelled as a (nondeterministic) 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 error specifications. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.
[122] Cezar Câmpeanu, Nelma Moreira, and Rogério Reis. On the dissimilarity operation on finite languages. In Henning Bordihn, Rudolf Freund, Benedek Nagy, and György Vaszil, editors, Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016), volume 321, pages 105--120. Österreichische Computer Gesellschaft, 2016. [ .pdf ]
The distinguishability language of a regular language L is the set of words distinguishing between pairs of words under the Myhill-Nerode equivalence induced by L, i.e., between pairs of distinct left quotients of L. The similarity relation induced by a language L is a similarity relation inspired by the Myhill-Nerode equivalence and it was used to obtain compact representation of automata for a finite language L, i.e., deterministic finite cover automata, which are deterministic finite automata accepting all the words of L and possibly some other words that are longer than any word of L. The dissimilarity language of a finite language L is defined as the set of words that separate a pair of words which are not similar w.r.t. to a (finite) language L. In this paper we extend the study of distinguishability operation on regular languages to l-dissimilarity, for linN, and the dissimilarity operation on finite languages. We examine their properties, the state complexity, and relations that can be established between these operations.
[121] Rogério Reis and Emanuele Rodaro. Ideal regular languages and strongly connected synchronizing automata. Theoretical Computer Science, 653:97--107, 2016. [ DOI | .pdf ]
We introduce the notion of a reset left regular decomposition of an ideal regular language, and we prove that the category formed by these decompositions with the adequate set of morphisms is equivalent to the category of strongly connected synchronizing automata. We show that every ideal regular language has at least one reset left regular decomposition. As a consequence, every ideal regular language is the set of synchronizing words of some strongly connected synchronizing automaton. Furthermore, this one-to-one correspondence allows us to introduce the notion of reset decomposition complexity of an ideal from which follows a reformulation of Cerny's conjecture in purely language theoretic terms. Finally, we present and characterize a subclass of ideal regular languages for which a better upper bound for the reset decomposition complexity holds with respect to the general case.
Keywords: Cerny Conjecture
[120] Cezar Câmpeanu, Nelma Moreira, and Rogério Reis. Distinguishability operations and closures. Fundamenta Informaticae, 148(3--4):243--266, 2016. [ DOI | .pdf ]
Given a language L, we study the language of words 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. For the case of regular languages, 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 regular 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.
Keywords: Distinguishability, regular languages
[119] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Average size of automata constructions from regular expressions. Bulletin of the European Association for Theoretical Computer Science, 116:167--192, June 2015. [ http ]
Because of their succinctness and clear syntax, regular expressions are the common choice to represent regular languages. Deterministic finite au- tomata are an excellent representation for testing equivalence, containment or membership, as these problems are easily solved for this model. How- ever, minimal deterministic finite automata can be exponentially larger than the associated regular expression, while the corresponding nondeterministic finite automata can be linearly larger. The worst case of both the complexity of the conversion algorithms, and of the size of the resulting automata, are well studied. However, for practical purposes, estimates for the average case can provide much more useful information. In this paper we review recent results on the average size of automata resulting from several constructions and suggest several directions of research. Most results were obtained within the framework of analytic combinatorics.
[118] Helmut Jurgensen and Rogério Reis. Preface. Special Issue - Descriptional Complexity of Formal Languages (DCFS 2013). International Journal of Fundations of Computer Science, 25(7):803 -- 805, 2015. [ DOI ]
[117] Nelma Moreira, Giovanni Pighizzini, and Rogério Reis. Optimal state reductions of automata with partially specified behaviors. In 41st SOFSEM - the International Conference on Current Trends in Theory and Practice of Computer Science, number 8939 in LNCS, pages 339--351. Springer, 2015. [ DOI | http ]
Nondeterministic finite automata with don't care states, namely states which neither accept nor reject, are considered. A characterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. Finally, it is proved that the problem of minimizing nondeterministic and deterministic don't care automata is NP-complete.
[116] Eva Maia, Nelma Moreira, and Rogério Reis. Prefix and right-partial derivative automata. In Mariya Soskova and Victor Mitrana, editors, Computability in Europe (CiE 2015), number 9136 in LNCS, pages 258--267. Springer, 2015. [ DOI | http ]
Recently, Yamamoto presented a new method for the conversion from regular expressions (REs) to non-deterministic finite automata (NFA) based on the Thompson ε-NFA (AT). The AT automaton has two quotients considered: the suffix automaton Asuf and the prefix automaton, Apre. Eliminating ε-transitions in AT, the Glushkov automaton (Apos) is obtained. Thus, it is easy to see that Asuf and the partial derivative automaton are the same. In this paper, we characterise the Apre automaton as a solution of a system of left RE equations and express it as a quotient of Apos by a specific left-invariant equivalence relation. We define and characterise the right-partial derivative automaton. Finally, we study the average size of all these constructions both experimentally and from an analytic combinatorics point of view.
[115] Nelma Moreira, Giovanni Pighizzini, and Rogério Reis. Universal disjunctive concatenation and star. In Jeffrey Shallit and Alexander Okhotin, editors, Proceedings of the 17th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS15), number 9118 in LNCS, pages 197--208. Springer, 2015. [ DOI | http ]
Two language operations that can be expressed by suitable combining complement with concatenation and star, respectively, are introduced. The state complexity of those operations on regular languages is investigated. In the deterministic case, optimal exponential state gaps are proved for both operations. In the nondeterministic case, for one operation an optimal exponential gap is also proved, while for the other operation an exponential upper bound is obtained.
[114] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Partial derivative automaton for regular expressions with shuffle. In Jeffrey Shallit and Alexander Okhotin, editors, Proceedings of the 17th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS15), number 9118 in LNCS, pages 21--32. Springer, 2015. [ DOI | http ]
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 derivative automata is in the worst case at most 2m, where m is the number of letters in the expression, while asymptotically and on average it is no more than (4/3)m.
[113] Stavros Konstantinidis, Casey Meijer, Nelma Moreira, and Rogério Reis. Symbolic manipulation of code properties. Preprint, 2015. [ http ]
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.
[112] António Machiavelo and Rogério Reis. Uma introdução (ingénua) à criptografia. In Ana Paula Garr ao, Margarida Raposo Dias, and Ricardo Cunha Teixeira, editors, Investigar em Educação Matemática. Diálogos e Conjunções numa Perspectiva Interdisciplinar, chapter XIII, pages 257--270. Letras Lavadas Edições, Ponta Delgada, S. Miguel, Açores, 2015. [ .pdf ]
[111] Eva Maia, Nelma Moreira, and Rogério Reis. Incomplete transition complexity on finite and infinite regular languages. Information and Computation, 244:1--22, 2015. [ DOI | http ]
The state complexity of basic operations on regular languages considering complete deterministic finite automata (DFA) has been extensively studied in the literature. But, if incomplete DFAs are considered, transition complexity is also an significant measure. In this paper we study the incomplete (deterministic) state and transition complexity of boolean operations, concatenation, star, and reversal for regular languages and finite languages. For all operations we give tight upper bounds for both descriptional measures. For regular languages we give a new tight upper bound for the transition complexity of the union, which refutes the conjecture presented by Y. Gao et al.. For finite languages, we correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right operand is larger than the left one. In general the operational complexities depend not only on the complexities of the operands but also on other refined measures. For both families of languages we present some experimental results to test the behaviour of those operations on the average case, and we conjecture that for many operations and in practical applications the worst-case complexity is seldom reached.
[110] Ivone Amorim, António Machiavelo, and Rogério Reis. On the number of linear finite transducers. International Journal of Foundations of Computer Science, 26(7):873--893, 2015. [ DOI ]
The notion of linear finite transducer (LFT) plays a crucial role in some cryptographic systems. However, as far as we know, no study was ever conducted to count and enu- merate these transducers, which is essential to verify if the size of the key space, of the aforementioned systems, is large enough to prevent an exhaustive search attack. In this work we present a way to estimate the number and percentage of injective equiv- alence classes by introducing a canonical form for LFTs and a procedure to test LFTs equivalence.
[109] Rudolf Freund, Markus Holzer, Nelma Moreira, and Rogério Reis, editors. Seventh Workshop on Non-Classical Models of Automata and Applications (NCMA 2015). Österreichische Computer Gesellschaft, 2015. ISBN 978-3-903035-07-2.
[108] Marco Almeida, Nelma Moreira, and Rogério Reis. Incremental dfa minimisation. RAIRO - Theoretical Informatics and Applications, 48(2):173--186, 2014. [ DOI | http ]
We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.
[107] Ivone Amorim, António Machiavelo, and Rogério Reis. On the invertibility of finite linear transducers. RAIRO - Theoretical Informatics and Applications, 48(1):107--125, 2014. [ DOI ]
[106] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. A hitchhiker's guide to descriptional complexity through analytic combinatorics. Theoretical Computer Science, 528(0):85 -- 100, 2014. [ DOI | http ]
Nowadays, increasing attention is being given to the study of the descrip- tional complexity in the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. Additionally, new asymptotic average-case results for several ε-NFA constructions are presented, in a unified framework. It turns out that, asymptotically, and in the average case, the complexity gap between the several constructions is significantly larger than in the worst case. Furthermore, one of the ε-NFA constructions approaches the corresponding ε-free NFA construction, asymptotically and on average.
[105] Jason Bell, Janusz Brzozowski, Nelma Moreira, and Rogério Reis. Symmetric groups and quotient complexity of boolean operations. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes on Computer Science, pages 1--12, 2014. [ DOI | .pdf ]
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.
[104] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Automata for KAT Expressions. Technical Report DCC-2014-01, DCC-FC, Universidade do Porto, January 2014. [ .pdf ]
[103] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the Equivalence of Automata for KAT-expressions. In Arnold Beckmann, Erzsébet Csuhaj-Varjú, and Klaus Meer, editors, Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings, volume 8493 of LNCS, pages 73--83. Springer-Verlag, 2014. [ DOI | .pdf ]
Kleene algebra with tests (KAT) is a decidable equational system for program verification that uses both Kleene and Boolean algebras. In spite of KAT?s elegance and success in providing theoretical solutions for several problems, not many efforts have been made towards obtaining tractable decision procedures that could be used in practical software verification tools. The main drawback of the existing methods relies on the explicit use of all possible assignments to boolean variables. Recently, Silva introduced an automata model that extends Glushkov's construction for regular expressions. Broda et al. extended also Mirkin's equation automata to KAT expressions and studied the state complexity of both algorithms. Contrary to other automata constructions from KAT expressions, these two constructions enjoy the same descriptional complexity behaviour as their counterparts for regular expressions, both in the worst case as well as in the average case. In this paper, we generalize, for these automata, the classical methods of subset construction for nondeterministic finite automata, and the Hopcroft and Karp algorithm for testing deterministic finite automata equivalence. As a result, we obtain a decision procedure for KAT equivalence where the extra burden of dealing with boolean expressions avoids the explicit use of all possible assignments to the boolean variables. Finally, we specialize the decision procedure for testing KAT expressions equivalence without explicitly constructing the automata, by introducing a new notion of derivative and a new method of constructing the equation automaton.
[102] Eva Maia, Nelma Moreira, and Rogério Reis. Partial derivative and position bisimilarity automata. In Markus Holzer and Martin Kutrib, editors, Implementation and Application of Automata, 19th International Conference (CIAA 2014), volume 8587 of LNCS, pages 264--277. Springer-Verlag, 2014. [ DOI | .pdf ]
Minimization of nondeterministic finite automata (NFA) is a hard problem (PSPACE-complete). Bisimulations are then an attrac- tive alternative for reducing the size of NFAs, as even bisimilarity (the largest bisimulation) is almost linear using the Paige and Tarjan algo- rithm. NFAs obtained from REs can have the number of states linear with respect to (w.r.t) the size of the REs and conversion methods from REs to equivalent NFAs can produce NFAs without or with transitions labelled with the empty word (ε-NFA). The standard conversion without ε-transitions is the position automaton, Apos. Other conversions, such as partial derivative (Apd ) automata or follow automata (Af ), were proved to be quotients of the position automata (by some bisimulations). Recent experimental results suggested that for REs in (normalized) star normal form (snf) the position bisimilarity almost coincide with the Apd automaton. Our goal is to have a better characterization of Apd au- tomata and their relation with the bisimilarity of the position automata. In this paper, we consider Apd automata for regular expressions without Kleene star and establish under which conditions it is isomorphic to the bisimilarity of Apos.
[101] Ivone Amorim, António Machiavelo, and Rogério Reis. Counting equivalent linear finite transducers using a canonical form. In Markus Holzer and Martin Kutrib, editors, Implementation and Application of Automata, 19th International Conference (CIAA 2014), volume 8587 of LNCS, pages 70--83. Springer-Verlag, 2014. [ DOI | .pdf ]
The notion of Linear finite transducer (LFT) play a crucial role in a family of cryptosystems introduced in the 80's and 90's. However, as far as we know, no study was conducted towards the counting and enumeration of these transducers, which is essential to verify if the size of the key space, of the aforementioned systems, is large enough to prevent an exhaustive search attack. In this paper, we determine the cardinal of the equivalence classes on the set of the LFTs with a given size. This result is sufficient to get an approximate value, by random sampling, for the number of non-equivalent injective LFTs, and subsequently for the size of the key space. We introduce a notion of canonical LFT, give a method to verify if two LFTs are equivalent, and prove that every LFT has exactly one equivalent canonical LFT. We then show how this canonical LFT allows us to calculate the size of each equivalence class on the set of the LFTs with the same number of states.
[100] Cezar Câmpeanu, Nelma Moreira, and Rogério Reis. The distinguishability operation on regular languages. In Suna Bensch, Rudolf Freund, and Friedrich Otto, editors, Non-Classical Models of Automata and Applications (NCMA 2014), pages 85--100. Oesterreichische Computer Gesellschaft, 2014. [ .pdf ]
In this paper we study the language of the words that, for a given language L, 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, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different quotients of a language L is n - 1, where n is the state complexity of L. For this operation, we also study the properties of its iteration.
[99] Ivone Amorim, António Machiavelo, and Rogério Reis. Statistical study on the number of injective linear finite transducers. In Suna Bensch, Rudolf Freund, and Friedrich Otto, editors, Non-Classical Models of Automata and Applications (NCMA 2014), pages 57--72. Oesterreichische Computer Gesellschaft, 2014. [ .pdf ]
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 the number of non-equivalent injective LFTs. By introducing a recurrence relation to count canonical LFTs, we show how to estimate the percentage of τ-injective LFTs. Several experimental results are presented, which by itself constitutes an important step towards the evaluation of the key space of those systems.
[98] Nelma Moreira and Rogério Reis. Preface. Special Issue - Implementation and Application of Automata (CIAA 2012). International Journal of Fundations of Computer Science, 24(06):689--690, September 2013. [ DOI ]
[97] Rafaela Bastos, Nelma Moreira, and Rogério Reis. Manipulation of extended regular expressions with derivatives. Technical Report DCC-2013-11, DCC-FC, Universidade do Porto, September 2013. [ .pdf ]
[96] Helmut Jurgensen and Rogério Reis, editors. Descriptional Complexity of Formal Systems, 15th International Workshop (DCFS 2013), volume 8031 of LNCS, London, Ontario, Canada, July 2013. Springer. ISBN 978-3-642-39309-9. [ DOI | http ]
[95] Davide Nabais, Nelma Moreira, and Rogério Reis. Desco: a knowledge based system for descriptional complexity of formal languages. Technical Report DCC-2013-12, DCC-FC Universidade do Porto, July 2013. [ .pdf ]
[94] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Glushkov and Equation Automata for KAT Expressions. Technical Report DCC-2013-07, DCC-FC, Universidade do Porto, July 2013. [ .pdf ]
[93] Nelma Moreira, Davide Nabais, and Rogério Reis. Desco: a web based information system for descriptional complexity results. Technical Report DCC-2013-03, DCC-FC, Universidade do Porto, 2013. [ .pdf ]
[92] Eva Maia, Nelma Moreira, and Rogério Reis. Incomplete transition complexity of some basic operations. In Peter van Emde Boas, Frans C.A. Groen, Giuseppe F. Italiano, Jerzy Nawrocki, and Harald Sack, editors, SOFSEM 2013: Theory and Practice of Computer Science, number 7741 in Lecture Notes on Computer Science, pages 319--330. Springer-Verlag, 2013. MR3074101. [ DOI | .pdf ]
Y. Gao et al. studied for the first time the transition complexity of Boolean operations on regular languages based on not necessarily complete DFAs. For the intersection and the complementation, tight bounds were presented, but for the union operation the upper and lower bounds differ by a factor of two. In this paper we continue this study by giving tight upper bounds for the concatenation, the Kleene star and the reversal operations. We also give a new tight upper bound for the transition complexity of the union, which refutes the conjecture presented by Y. Gao et al..
[91] Eva Maia, Nelma Moreira, and Rogério Reis. Incomplete transition complexity of basic operations on finite languages. In Stavros Konstantinidis, editor, Implementation and Application of Automata, 18th International Conference (CIAA 2013), number 7982 in LNCS, pages 349--356. Springer-Verlag, 2013. [ DOI | .pdf ]
The state complexity of basic operations on finite languages (considering complete DFAs) has been extensively studied in 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 descriptional 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.
[90] Eva Maia, Nelma Moreira, and Rogério Reis. The operational incomplete transition complexity on finite languages. Technical Report DCC-2013-02, DCC - FC & CMUP, Universidade do Porto, January 2013. [ .pdf ]
[89] Rogério Reis and Emanuele Rodaro. Regular ideal languages and synchronizing automata. In Juhani Karhumäki and Luca Zamboni, editors, 9th International Conference on WORDS, LNCS. Springer-Verlag, 2013. [ DOI | .pdf ]
We introduce the notion of reset left regular decomposition of an ideal regular language and we prove that there is a one-to-one correspondence between these decompositions and strongly connected synchronizing automata. We show that each ideal regular language has at least a reset left regular decomposition. As a consequence each ideal regular language is the set of synchronizing words of some strongly connected synchronizing automaton. Furthermore, this one-to-one correspondence allows us to formulate Cerny's conjecture in a pure language theoretic framework.
[88] Rogério Reis and Emanuele Rodaro. On strongly connected ideal languages. Technical Report DCC-2013-01, DCC-FC Universidade do Porto, January 2013. [ .pdf ]
[87] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average size of Glushkov and equation automata for KAT expressions. In 19th International Symposium on Fundamentals of Computation Theory, number 8070 in LNCS, pages 72--83. Springer-Verlag, 2013. [ DOI | .pdf ]
Kleene algebra with tests (kat) is an equational system that extends Kleene algebra, the algebra of regular expressions, and that is specially suited to capture and verify properties of simple imperative programs. In this paper we study two constructions of automata from KAT expressions: the Glushkov automaton, and a new construction based on the notion of prebase (equation automata. Contrary to other automata constructions from KAT expressions, these two constructions enjoy the same descriptional complexity behaviour as their conterparts for regular expressions, both in the worst-case as well as in the average-case. In particular, our main result is to show that, asymptotically and on average the number of transitions of the nfa_Pos is linear in the size of the kat expression.
[86] Yuan Gao, Nelma Moreira, Rogério Reis, and Sheng Yu. A survey on state complexity. (Submitted), 2013. [ http ]
[85] Rogério Reis and Emanuele Rodaro. The language of initially connected deterministic finite automata (extended abstract). In Proceedings of 14th Italian Conference on Theoretical Computer Science, pages 179--184, 2013. [ .pdf ]
[84] Rogério Reis and Emanuele Rodaro. Reset regular decomposition complexity of regular ideal languages (extended abstract). In Proceedings of 14th Italian Conference on Theoretical Computer Science, pages 30--35, 2013. [ .pdf ]
[83] Marco Almeida, Nelma Moreira, and Rogério Reis. Finite automata minimization algorithms. In Jiacun Wang, editor, Handbook of Finite State Based Models and Applications, Discrete Mathematics and Its Applications, pages 145--170. Chapman and Hall/CRC Press, November 2012. MR3014621. [ http ]
[82] Martin Kutrib, Nelma Moreira, and Rogério Reis, editors. Descriptional Complexity of Formal Systems, 14th International Workshop (DCFS 2012), volume 7386 of LNCS, Braga, Portugal, July 2012. Springer. ISBN 978-3-642-31622-7. MR3087301. [ DOI | http ]
[81] Nelma Moreira and Rogério Reis, editors. Implementation and Application of Automata, 17th International Conference (CIAA 2012), volume 7381 of LNCS, Porto, Portugal, July 2012. Springer. ISBN 978-3-642-31605-0. MR3059553. [ DOI | http ]
[80] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. An introduction to descriptional complexity of regular languages through analytic combinatorics. Technical Report DCC-2012-05, DCC - FC, Universidade do Porto, July 2012. [ .pdf ]
[79] Eva Maia, Nelma Moreira, and Rogério Reis. On the incomplete transition complexity of some basic operations on regular languages. Technical Report DCC-2012-02, DCC-FC, Universidade do Porto, April 2012. [ .pdf ]
[78] Ivone Amorim, António Machiavelo, and Rogério Reis. Formal power series and the invertibility of finite linear transducers. In Rudolf Freund, Markus Holzer, Bianca Truthe, and Ulrich Ultes-Nitschs, editors, Fourth Workshop on Non-Classical Medels for Automata and Applications (NCMA 2012), pages 33--48. Oesterreichische Computer Gesellschaft, 2012. [ .pdf ]
Linear finite transducers underlie a series of schemes for Public Key Criptography (PKC) proposed in the 90s of the last century. The uninspiring and arid language then used, condemned these works to oblivion. Although some of these schemes were, after, shown to be insecure, the promise of a new system of PKC relying in different complexity assumptions is still quite exciting. The algorithms there used depend heavily on the results of invertibility of linear transducers. In this paper we introduce the notion of post-initial linear transducer, which is an extension of the notion of linear finite transducer with memory, and for which the previous fundamental results on invertibility still hold. Using this notion, we give a necessary and sufficient condition for left invertibility with fixed delay of finite transducers, as well as a new explicit method to obtain a left inverse.
[77] António Machiavelo and Rogério Reis. Turing e a enigma. Boletim da Sociedade Portuguesa de Matemática, SPM, 67, 2012. MR3059023. [ .pdf ]
[76] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average size of Glushkov and partial derivative automata. International Journal of Foundations of Computer Science, 23(5):969--984, 2012. MR2983363. [ DOI | .pdf ]
In this paper, the relation between the Glushkov automaton (nfaPos) and the partial derivative automaton (nfaPD) of a given regular expression, in terms of transition complexity, is studied. The average transition complexity of nfaPOS was proved by Nicaud to be linear in the size of the corresponding expression. This result was obtained using an upper bound of the number of transitions of nfaPOS. Here we present a new quadratic construction of nfaPOS that leads to a more elegant and straightforward implementation, and that allows the exact counting of the number of transitions. Based on that, a better estimation of the average size is presented. Asymptotically, and as the alphabet size grows, the number of transitions per state is on average 2. Broda et al. computed an upper bound for the ratio of the number of states of nfaPD to the number of states of nfaPOS, which is about (1)/(2) for large alphabet sizes. Here we show how to obtain an upper bound for the number of transitions in nfaPD, which we then use to get an average case approximation. In conclusion, assymptotically, and for large alphabets, the size of nfaPD is half the size of the nfaPOS. This is corroborated by some experiments, even for small alphabets and small regular expressions.
[75] Jürgen Dassow, Martin Kutrib, Nelma Moreira, and Rogério Reis. Preface. Selected papers of DCFS 2012. Journal of Automata, Languages and Combinatorics, 17(2--4):59--60, 2012. [ .html ]
[74] Rizó Isrof, Nelma Moreira, and Rogério Reis. GUITAR: Graphical User Interface Tool for Automata Representation. In Actas do IJUP. Universidade do Porto, 2012. [ .pdf ]
[73] Yuan Gao, Nelma Moreira, Rogério Reis, and Sheng Yu. A review on state complexity of individual operations. Technical Report dcc-2011-08, DCC - FC, Universidade do Porto,, December 2011. [ .pdf ]
[72] Ivone Amorim, António Machiavelo, and Rogério Reis. On linear finite automata and cryptography. Technical Report DCC-2011-11, DCC-FC, Universidade do Porto, August 2011. [ .pdf ]
[71] Marco Almeida, Nelma Moreira, and Rogério Reis. Incremental dfa minimisation. In Michael Domaratzki and Kai Salomaa, editors, Proceedings of the 15th International Conference on Implementation and Application of Automata (CIAA 2010), number 6482 in Lecture Notes on Computer Science, pages 39--48, Winnipeg, MA, Canada, August 2011. Springer-Verlag. MR2776275. [ DOI | .pdf ]
[70] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. The average transition complexity of Glushkov and partial derivative automata. In G. Mauri and A. Leporati, editors, Developments in Language Theory, 15th International Conference, DLT 2011, Milano, Italy, July 2011. Proceedings, volume 6795 of Lecture Notes on Computer Science, pages 93--104, Milano, Italy, July 2011. Springer-Verlag. MR2862718. [ DOI | .pdf ]
In this paper, the relation between the Glushkov automaton Nfapos and the partial derivative automaton (Nfapd) of a given regular expression, in terms of transition complexity, is studied. The average transition complexity of Nfapos was proved by Nicaud to be linear in the size of the corresponding expression. This result was obtained using an upper bound of the number of transitions of NFApos. Here we present a new quadratic construction of NFApos that leads to a more elegant and straightforward implementation, and that allows the exact counting of the number of transitions. Based on that, a better estimation of the average size is presented. Asymptotically, and as the alphabet size grows, the number of transitions per state is on average 2. Broda et al. computed an upper bound for the ratio of the number of states of NFApd to the number of states of NFApos, which is about 1/2 for large alphabet sizes. Here we show how to obtain an upper bound for the number of transitions in NFApd, which we then use to get an average case approximation. Some experimental results are presented that illustrate the quality of our estimate.
[69] Nelma Moreira, Davide Nabais, and Rogério Reis. DesCo: a web based information system for descriptional complexity results. Technical Report DCC-2011-10, DCC-FC, Universidade do Porto, 2011. [ .pdf ]
[68] Eva Maia, Nelma Moreira, and Rogério Reis. A static type inference for Python. In Proc. of DYLA'11, 5th Workshop on Dynamic Languages and Applications, co-located with 49th Intl Conf on Objects, Models, Components and Patterns (TOOLS 2011) July 1, 2011, Zürich, Switzerland, 2011. [ .pdf ]
Dynamic languages, like Python, are attractive because they guarantee that no correct program is rejected prematurely. However, this comes at a price of losing early error detection, and making both code optimization and certification harder tasks when compared with static typed languages. Having the static certification of Python programs as a goal, we developed a static type inference system for a subset of Python, known as RPython. Some dynamic features are absent from RPython, nevertheless it is powerful enough as a Python dialect and exhibits most of its main features. Our type inference system tackles with almost all language constructions, such as object inheritance and subtyping, polymorphic and recursive functions, exceptions, generators, modules, etc., and is itself written in Python.
[67] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average state complexity of partial derivative automata: an analytic combinatorics approach. International Journal of Foundations of Computer Science, 22(7):1593--1606, 2011. MR2865339. [ DOI | .pdf ]
The partial derivative automaton Apd is usually smaller than other nondeterministic finite automata constructed from a regular expression, and it can be seen as a quotient of the Glushkov automaton (Apos). By estimating the number of regular expressions that have epsilon as a partial derivative, we compute a lower bound of the average number of mergings of states in Apos and describe its asymptotic behaviour. This depends on the alphabet size, k, and for growing k's its limit approaches half the number of states in Apos. The lower bound corresponds to consider the Apd automaton for the marked version of the re, i.e. where all its letters are made different. Experimental results suggest that the average number of states of this automaton, and of the APd automaton for the unmarked re, are very close to each other.
[66] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Study of the average size of Glushkov and partial derivative automata. Technical Report DCC-2011-03, DCC-FC, Universidade do Porto, 2011. [ .pdf ]
[65] Cezar Câmpeanu, Nelma Moreira, and Rogério Reis. Expected compression ratio for dfca: experimental average case. Technical Report DCC-2011-07, DCC-FC, Universidade do Porto, January 2011. [ .pdf ]
In this paper we investigate from a statistical point of view the expected compression ratio between the size of a minimal Deterministic Finite Cover Automaton (DFCA) and the size of the minimal corresponding Determinitic Finite Automaton (DFA). Using sound statistical methods, we extend the experimental study done in [16], thus obtaining a much better picture of the compression power of DFCAs. We compute the expected ratio for the family of all finite languages, but also for various subfamilies of finite languages, such as prefix, suffix-free languages prefix and suffix closed languages, or (un)balanced languages. We also give an example of a family for which the expected compression ratio is very high.
Keywords: cover automata, automata theory, compression
[64] André Almeida, Nelma Moreira, and Rogério Reis. GUItar and FAgoo: Graphical interface for automata visualization, editing, and interaction. In Luís S. Barbosa and Miguel P. Correia, editors, Inforum, Simpósio de Informática, pages 317--328, Braga, Portugal, September 2010.
[63] Eva Maia, Nelma Moreira, and Rogério Reis. Inferência de tipos em Python. In Luís S. Barbosa and Miguel P. Correia, editors, Inforum, Simpósio de Informática, pages 515--518, Braga,Portugal, September 2010. Also at http://inforum.org.pt/INForum2010/papers/especificacao-verificacao-e-teste-sistemas-criticos/Paper040.pdf. [ .pdf ]
[62] Nuno Gaspar, Sim ao Melo de Sousa, and Rogério Reis. Timing analysis - from predictions to certificates. In Luís S. Barbosa and Miguel P. Correia, editors, Inforum, Simpósio de Informática, pages 491--502, Braga,Portugal, September 2010. Also at http://inforum.org.pt/INForum2010/papers/especificacao-verificacao-e-teste-sistemas-criticos/Paper070.pdf. [ .pdf ]
In real-time systems, timing constraints must be satisfied in order to guarantee that deadlines will be met. The calculation of each task?s worst-case execution time (WCET) is a prerequisite for the schedu- lability analysis, and hence of paramount importance for real-time sys- tems. However, an accurate prediction can be difficult if the underlying hardware architecture possesses features like caches and pipelines. In this paper we report our work in progress project on ACCEPT, an Abstraction-Carrying CodE Platform for Timing validation. Our ap- proach counts on information gathered at source-code level (e.g. loop bounds, infeasible paths), defined by annotations that also express the intended timing behaviour. Furthermore, in the context of mobile code safety and in order to minimize the trusted computing base, we produce a checkable certificate whose validity entails compliance with the calcu- lated WCET.
[61] André Almeida, Nelma Moreira, and Rogério Reis. GUItar and FAgoo: Graphical interface for automata visualization, editing, and interaction. In Luís S. Barbosa and Miguel P. Correia, editors, Inforum, Simpósio de Informática, pages 317--328, Braga,Portugal, September 2010. Also at http://inforum.org.pt/INForum2010/papers/computacao-grafica/Paper038.pdf. [ .pdf ]
GUItar is a graphical environment for graph visualization, editing, and interaction, that specially focuses in finite automata dia- grams. The application incorporates mechanisms to facilitate the editing of these graphs. It also provides a style manager that allows the cre- ation of rich state and arc styles to be used in the drawing of its ob- jects. This style manager allows the system to cope with complex styles, broaden the application scope to graphical representations of other com- putational models like transducers or Turing machines. GUItar also has a foreign function call (FFC) mechanism for the easy integration of exter- nal modules and libraries like automata symbolic manipulators or graph drawing libraries. For automatic graph drawing we are developing FA- goo, a package that seeks to provide tools capable of finding pleasant graph drawings. FAgoo implements graph drawing algorithms that find embeddings which the user, with minimal manual changes, can adjust to its aesthetically taste. Both GUItar and FAgoo are on going projects licensed under GPL.
[60] Nelma Moreira, Davide Nabais, and Rogério Reis. State elimination ordering strategies: Some experimental results. In I. MacQuillan, G. Pighizzini, and B. Trost, editors, Proc. of 11th Workshop on Descriptional Complexity of Formal Systems (DCFS10), pages 169--180, Saskatoon, Saskatchewan,Canada, August 2010. [ DOI | .pdf ]
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 heuris- tics presented in the literature and propose new ones. We also present some experimental comparative results based on uniform random gener- ated deterministic finite automata.
[59] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average number of states of partial derivative automata. In Yuan Gao, Hanlin Lu, Shinnosuke Seki, and Sheng Yu, editors, Developments in Language Theory, 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings, volume 6224 of Lecture Notes on Computer Science, pages 112--123, London, ON, Canada, August 2010. Springer-Verlag. MR2725637. [ DOI | .pdf ]
The partial derivative automaton (NFA_Pd) is usually smaller than other non-deterministic finite automata constructed from a regular expression, and it can be seen as a quotient of the Glushkov automaton (NFA_Pos). By estimating the number of regular expressions that have epsilon as a partial derivative, we compute a lower bound of the average number of mergings of states in NFA_Pos and describe its asymptotic behaviour. This depends on the alphabet size, k, and its limit, as k goes to infinity, is 1/2. The lower bound corresponds exactly to consider the NFA_Pd automaton for the marked version of the RE, i.e. where all its letters are made different. Experimental results suggest that the average number of states of this automaton, and of the NFA_Pos automaton for the unmarked RE, are very close to each other.
[58] Hugo Gouveia, Nelma Moreira, and Rogério Reis. Small nfas from regular expressions: Some experimental results. In Fernando Ferreira, Hélia Guerra, Elvira Mayordomo, and Jo ao Rasga, editors, Proceedings of 6th Conference on Computability in Europe (CIE 2010), pages 194--203, Ponta Delgada, Azores, Portugal, June 2010. CMATI. Also at ArXiv: http://arxiv.org/abs/1009.3599. [ .pdf ]
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 NFAs 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.
[57] Diogo Fialho, Nuno Gaspar, Sim ao Melo de Sousa, Rogério Reis, and Jorge Sousa Pinto. Towards a worst-case execution time calculation platform with certificate production. In Proceedings of the 8th European Dependable Computing Conference, Valencia, Spain, April 2010. Extended Abstract. [ .pdf ]
[56] António Machiavelo and Rogério Reis. Ainda o totobola: o singular caso dos 5. Boletim da Sociedade Portuguesa de Matemática,SPM, 2010. [ .pdf ]
[55] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average size of pd automata: an analytic combinatorics approach. Technical Report DCC-2010-04, DCC-FC, Universidade do Porto, 2010. [ .html ]
[54] José Alves, Nelma Moreira, and Rogério Reis. XML description for automata manipulations. In Alberto Sim oes, Daniela Cruz, and José Carlos Ramalho, editors, Actas XATA 2010, XML: aplicações e tecnologias associadas, pages 77--88, ESEIG, Vila do Conde, 2010. Also in http://hdl.handle.net/1822/10637. [ .pdf ]
GUItar is a visualization software tool for various types of automata (standard, weighted, pushdown, transducers, Turing machines, etc.). It provides interactive manipulation of diagrams, comprehensive graphic style creation, multiple export/import filters, and a generic “foreign function calls” (ffc) interface with external systems. In this paper we describe GUItar's XML framework and show how it allows for extensibility, modularity and interoperability.
[53] Marco Almeida, Nelma Moreira, and Rogério Reis. Testing equivalence of regular languages. Journal of Automata, Languages and Combinatorics, 15(1/2):7--25, 2010. [ .pdf ]
The minimal deterministic finite automaton is generally used to determine regular languages equality. Using Brzozowski's notion of derivative, Antimirov and Mosses proposed a rewrite system for deciding regular expressions equivalence of which Almeida et al. presented an improved variant. Hopcroft and Karp proposed an almost linear algorithm for testing the equivalence of two deterministic finite automata that avoids minimisation. In this paper we improve this algorithm's best-case running time, present an extension to non-deterministic finite automata, and establish a relationship with the one proposed in Almeida et al., for which we also exhibit an exponential lower bound. We also present some experimental comparative results.
[52] Marco Almeida, Nelma Moreira, and Rogério Reis. Antimirov and Mosses' rewrite system revisited. International Journal of Foundations of Computer Science, 20(4):669--684, August 2009. MR2555761. [ DOI | .pdf ]
[51] Marco Almeida, Nelma Moreira, and Rogério Reis. Testing equivalence of regular languages. In Workshop on Descriptional Complexity of Formal Systems (DCFS09), Magdeburg, Germany, July 2009. Also in Electronic Proceedings in Theoretical Computer Science (eptcs 3) http://www.eptcs.org. [ DOI | .pdf ]
[50] André Almeida, Marco Almeida, José Alves, Nelma Moreira, and Rogério Reis. Fado and guitar: tools for automata manipulation and visualization. In S. Maneth, editor, CIAA 2009: Fourteenth International Conference on Implementation and Application of Automata, volume 5642 of Lecture Notes on Computer Science, pages 65--74, Sydney, Australia, July 2009. Springer-Verlag. [ DOI | .pdf ]
FAdo is an ongoing project which aims to provide a set of tools for symbolic manipulation of formal languages. To allow high-level programming with complex data structures, easy prototyping of algorithms, and portability (to use in computer grid systems for example), are its main features. Our main motivation is the theoretical and experimental research, but we have also in mind the construction of a pedagogical tool for teaching automata theory and formal languages. For the graphical visualization and interactive manipulation a new interface application, GUItar, is being developed. In this paper, we describe the main components of the FAdo system as well as the basics of the graphical interface and editor, the export/import filters and its generic interface with external systems, such as FAdo.
[49] Nelma Moreira and Rogério Reis. Series-parallel automata and short regular expressions. Fundamenta Informaticae, 91(3-4):611--629, 2009. MR2518215. [ DOI | .pdf ]
Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n^2logn) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices.
[48] Nelma Moreira and Rogério Reis. Series-parallel automata and short regular expressions. Fundamenta Informaticae, 91(3-4):611--629, 2009. [ DOI | .pdf ]
Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n^2logn) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices.
[47] António Machiavelo and Rogério Reis. Um manuscrito perdido do Dr. Watson: Sherlock Holmes e o sudoku, parte ii. Boletim da Sociedade Portuguesa de Matemática,SPM, (60):47--65, 2009. [ .pdf ]
[46] António Machiavelo and Rogério Reis. O problema do totobola. Boletim da Sociedade Portuguesa de Matemática,SPM, (61):39--45, 2009. [ .pdf ]
[45] M. Ferreira, H. Conceiç ao, R. Fernandes, and R. Reis. Locating cars through a vision enabled VANET. In 2009 IEEE Intelligent Vehicles Symposium, pages 99--104. IEEE, 2009.
[44] Marco Almeida, Nelma Moreira, and Rogério Reis. Testing equivalence of regular languages. Technical Report DCC-2009-01, DCC-FC&LIACC, Universidade do Porto, 2009. [ .html ]
[43] Marco Almeida, Nelma Moreira, and Rogério Reis. Exact generation of minimal acyclic deterministic finite automata. International Journal of Foundations of Computer Science, 19(4):751--765, August 2008. MR2437812. [ DOI | .pdf ]
We give a canonical representation for minimal acyclic deterministic finite automata (Madfa) with n states over an alphabet of k symbols. Using this normal form, we present a method for the exact generation of Madfas. This method avoids a rejection phase that would be needed if a generation algorithm for a larger class of objects that contains the Madfas were used. We give upper and lower bounds for Madfas enumeration and some exact formulas for small values of n.
[42] Marco Almeida, Nelma Moreira, and Rogério Reis. Exact generation of acyclic deterministic finite automata. In Workshop on Descriptional Complexity of Formal Systems (DCFS08), Charlottetown, Canada, July 2008. [ .pdf ]
We give a canonical representation for trim acyclic deterministic finite automata (Adfas) with n states over an alphabet of k symbols. Using this normal form, we present a backtracking algorithm for the exact generation of Adfas. This algorithm is a non trivial adaptation of the algorithm for the exact generation of minimal acyclic deterministic finite automata , presented by Almeida et al..
[41] André Almeida, José Alves, Nelma Moreira, and Rogério Reis. Cgm: A context-free grammar manipulator. In Corta 08, Bragança, Portugal, July 2008. [ .pdf ]
We present an interactive graphical environment for the manipulation of context-free languages. The graphical environment allows the editing of a context-free grammar, the conversion to Chomsky normal form, word parsing and the (interactive) construction of parse trees. It is possible to store positive and negative datasets of words to be tested by a given grammar. The main goal of this system is to provide a pedagogical tool for studying grammar construction and parse trees.
[40] Marco Almeida, Nelma Moreira, and Rogério Reis. Antimirov and Mosses's rewrite system revisited. In O. Ibarra and B. Ravikumar, editors, CIAA 2008: Thirteenth International Conference on Implementation and Application of Automata, Lecture Notes on Computer Science, pages 46--56, San Francisco, CA, USA, July 2008. Springer-Verlag. MR2504697. [ DOI | .pdf ]
Antimirov and Mosses proposed a rewrite system for deciding the equivalence of two (extended) regular expressions. In this paper we present a functional approach to that method, prove its correctness, and give some experimental comparative results. Besides an improved version of AM's algorithm, we present a version using partial derivatives. Our preliminary results lead to the conclusion that, indeed, these methods are feasible and, generally, faster than the classical methods.
[39] António Machiavelo and Rogério Reis. Um manuscrito perdido do Dr. Watson: Sherlock Holmes e o sudoku parte i. Boletim da Sociedade Portuguesa de Matemática, SPM, (59):81--89, 2008. [ .pdf ]
[38] Silvestre Lacerda, Norberto Lopes, Nelma Moreira, and Rogério Reis. A toolkit for an oral history digital archive. In José Carlos Ramalho and Jo ao Correia Lopes, editors, Actas XATA 2008, XML: aplicações e tecnologias associadas, pages 40--51, Universidade de Évora, 2008. [ .pdf ]
[37] Marco Almeida, Nelma Moreira, and Rogério Reis. On the performance of automata minimization algorithms. In Arnold Beckmann, Costas Dimitracopoulos, and Benedikt Löwe, editors, CiE 2008: Abstracts and extended abstracts of unpublished papers., 2008. [ .pdf ]
[36] Marco Almeida, Nelma Moreira, and Rogério Reis. Testing regular expressions equivalence. Technical Report DCC-2007-07, DCC - FC, Universidade do Porto, October 2007. [ .pdf ]
[35] Marco Almeida, Nelma Moreira, and Rogério Reis. Exact generation of minimal acyclic deterministic finite automata. In Workshop on Descriptional Complexity of Formal Systems (DCFS07), pages 57--68, High Tatras, Slovakia, July 2007. [ .pdf ]
[34] Marco Almeida, Nelma Moreira, and Rogério Reis. Exact generation of minimal acyclic deterministic finite automata. Technical Report DCC-2007-05, DCC - FC & LIACC, Universidade do Porto, June 2007. [ .pdf ]
[33] Marco Almeida, Nelma Moreira, and Rogério Reis. On the performance of automata minimization algorithms. Technical Report DCC-2007-03, DCC - FC & LIACC, Universidade do Porto, June 2007. [ .pdf ]
[32] António Machiavelo and Rogério Reis. Automated ciphertext-only cryptanalysis of the bifid cipher. Cryptologia, 31(2):112--124, April 2007.
In this paper we describe a fully automated ciphertext-only cryptanalysis attack on the Bifid cipher, for which the original text language is known. We have implemented this attack using Python. We use an easily computable statistical function to find the period of the cipher, and then the key-table is generated in a fairly efficient way. The process is directed in such a way that strongly narrows the search space of possible solutions. This results in a feasible attack to a Bifid cryptogram, provided that its length is enough for accurate statistical analysis.
Keywords: Cryptanalysis Cryptography, Bifid
[31] Silvestre Lacerda, Norberto Lopes, Nelma Moreira, and Rogério Reis. Ferramentas para a construção de arquivos digitais de história oral. In Luís Carriço José Carlos Ramalho, João Correia Lopes, editor, Actas XATA 2007, XML: aplicações e tecnologias associadas. Universidade de Lisboa, February 2007.
[30] Rogério Reis. Autómatos finitos: manipulação, geração e contagem. PhD thesis, Faculdade de Ciências da Universidade do Porto, 2007.
[29] J. Barbosa, J. Caramelo, J. Cunha, A. Ferreira, S. Lacerda, N. Lopes, M. Loff, M. Matias, T. Medina, B. Monteiro, N. Moreira, C. Nogueira, R. Reis, I. Ribeiro, J. Rocha, C. F. Silva, and C. R. Silva. Education and language in memories of labour. Poster in “Investugação Científica na Pré-Graduação”, Universidade do Porto, 2007.
[28] Marco Almeida, Nelma Moreira, and Rogério Reis. Enumeration and generation with a string automata representation. Theoretical Computer Science, 387(2):93--102, 2007. MR2362181. [ DOI | .pdf ]
The representation of combinatorial objects is decisive for the feasibility of several enumerative tasks. In this work, we present a unique string representation for complete initially-connected deterministic automata (ICDFAs) with n states over an alphabet of k symbols. For these strings we give a regular expression and show how they are adequate for exact and random generation, allow an alternative way for enumeration and lead to an upper bound for the number of ICDFAs. The exact generation algorithm can be used to partition the set of ICDFAs in order to parallelize the counting of minimal automata, and thus of regular languages. A uniform random generator for ICDFAs is presented that uses a table of pre-calculated values. Based on the same table, an optimal coding for ICDFAs is obtained.
[27] Marco Almeida and Rogério Reis. Efficient representation of integer sets. Technical Report DCC-2006-06, DCC-FC & LIACC, Universidade do Porto, December 2006. [ .pdf ]
[26] Marco Almeida, Nelma Moreira, and Rogério Reis. Enumeration and generation of initially connected deterministic finite automata. Technical Report DCC-2006-07, DCC-FC & LIACC, Universidade do Porto, December 2006. [ .pdf ]
[25] Marco Almeida, Nelma Moreira, and Rogério Reis. Aspects of enumeration and generation with a string automata representation. In H. Leung and G.Pighizzini, editors, Proceedings of the 8th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS06), number NMSU-CS-2006-001 in Computer Science Technical Report, pages 58--69, Las Cruces, New Mexico, June 2006. NMSU. [ .pdf ]
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 (complete) initially-connected deterministic automata (ICDFA's) with n states over an alphabet of k symbols can be used for counting, exact enumeration, sampling and optimal coding, not only the set of ICDFA's but, to some extent, the set of regular languages. An exact generation algorithm can be used to partition the set of ICDFA's in order to parallelize the counting of minimal automata (and thus of regular languages). We present also a uniform random generator for ICDFA's that uses a table of pre-calculated values. Based on the same table it is also possible to obtain an optimal coding for ICDFA's.
[24] Sónia Sousa, Rogério Reis, and Luís Damas. Agisa: Ambiente de gestão integrado da sala de aulas. Revista de Ciências da Computação, 1(1):67--76, 2006.
[23] António Machiavelo and Rogério Reis. Automated ciphertext-only cryptanalysis of the bifid cipher. Technical Report DCC-2006-01, DCC - FC & LIACC, Universidade do Porto, 2006. [ DOI | .pdf ]
[22] Peter F. Blanchard, Frank Harary, and Rogério Reis. Partitions into sum-fee sets. INTEGERS:Electronic Journal of Combinatorial Number Theory, 6, 2006. MR2215351 (2006m:11029). [ .html ]
We define a sum as a set {x,y,z} of distinct natural numbers such that x+y=z, and let Nn={1,2,...,n}. We introduce a new sequence h(c) defined as the smallest s such that there is no partition of Ns into c sum-free parts. We determine h(c) for c=3,4 after easily noting that h(1)=3 and h(2)=9. We find that h(3)=24 and h(4)=67 using a subtle computer program.
Keywords: Ramsey Theory, Combinatorics
[21] Sónia Sousa, Luís Damas, and Rogério Reis. AGISA: An Integrateded System for Classroom Administration. In A. Méndez Vilas, B. Gonzalez Pereira, J. Mesa González, and J. A. Mesa González, editors, Recent Research Developments in Learning Technologies. III International Conference on multimedia & ICTs in Education, pages 1266--1271, June 2005.
[20] Rogério Reis, Nelma Moreira, and Marco Almeida. On the representation of finite automata. In G. Pighizzini C. Mereghetti, B. Palano and D. Wotschkes, editors, Proceedings of the 7th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS05), pages 269--276, Como, Italy, June 2005. For a extended version see Technical Report [17]. [ .pdf ]
[19] José João Morais, Nelma Moreira, and Rogério Reis. Acyclic automata with easy-to-find short regular expressions. In Igor Litovshy Jacques Farré and Sylvain Schmitz, editors, CIAA 2005, Tenth International Conference on Implementation and Application of Automata, volume 3845 of Lecture Notes on Computer Science, pages 349--350, Sophia-Anthiopolis, France, June 2005. Springer-Verlag. Also in Pre-proceedings of Tenth International Conference on Implementation and Application of Automata (CIAA05). [ .pdf ]
[18] José João Morais, Nelma Moreira, and Rogério Reis. Acyclic automata with easy-to-find short regular expressions. Technical Report DCC-2005-03, ,DCC-FC& LIACC, Universidade do Porto, April 2005. [ .pdf ]
[17] Marco Almeida, Nelma Moreira, and Rogério Reis. On the representation of finite automata. Technical Report DCC-2005-04, DCC - FC & LIACC, Universidade do Porto, April 2005. [ .pdf ]
[16] Nelma Moreira and Rogério Reis. Interactive manipulation of regular objects with FAdo. In Proceedings of 2005 Innovation and Technology in Computer Science Education (ITiCSE 2005). ACM, 2005. Based on Technical Report [9]. [ .pdf ]
FAdo is an ongoing project which aims the development of an interactive environment for symbolic manipulation of formal languages. In this paper we focus in the description of interactive tools for teaching and assisting research on regular languages, and in particular finite automata and regular expressions. Those tools implement most standard automata operations, conversion between automata and regular expressions, and word recognition. We illustrate their use in training and automatic assessment. Finally we present a graphical environment for editing and interactive visualisation.
Keywords: Automata theory, Interactive visual tools, e-learning
[15] Nelma Moreira and Rogério Reis. Fado:interactive tools for learning formal computational models. In Encontro Nacional de Visualização Científica, Centro Multimeios de Espinho, 2005. http://envc2005.multimeios.pt. [ .pdf ]
[14] Nelma Moreira and Rogério Reis. On the density of languages representing finite set partitions. Journal of Integer Sequences, 8(05.2.8), 2005. MR2152288. [ .html ]
[13] Nelma Moreira and Rogério Reis. On the density of languages representing finite set partitions. Technical Report DCC-2004-07, DCC-FC& LIACC, Universidade do Porto, August 2004. [ .pdf ]
[12] Rogério Reis, Nelma Moreira, and Jo ao Pedro Pedroso. Educated brute-force to get h(4). Technical Report DCC-2004-04, DCC-FC& LIACC, Universidade do Porto, July 2004. [ .pdf ]
[11] Jo ao Pedro Pedroso, Nelma Moreira, and Rogério Reis. A web-based system for multi-agent interactive timetabling. In ICKEDS 2004, First International Conference on Knowledge Engineering and Decision Support, Porto,21-23 of July, 2004. [ .pdf ]
We propose a web-based timetabling system for a typical situation in universities, where agents (usually departments or faculties) compete for a set of resources (class rooms) on a given number of time slots. Each agent (typically a person, on the behalf of a department) proposes the placement (room and time) for events. A dispatching system decides which event should be scheduled next, based on a pre-established set of rules, and asks its placement to the corresponding department. The system also includes a solver that suggests the placement of an event to each agent, thus allowing a completely automated timetable construction. We describe a prototype being implemented at the Faculty of Sciences, University of Porto.
[10] Rogério Reis and Nelma Moreira. Yappy: Yet another LR(1) parser generator for Python. DCC-FC & LIACC, Universidade do Porto, Portugal, 2003. http://www.ncc.up.pt/fado/Yappy/. [ .pdf ]
[9] Rogério Reis and Nelma Moreira. FAdo:tools for finite automata and regular expressions manipulation. Technical Report DCC-2002-2, DCC-FC& LIACC, Universidade do Porto, August 2002. [ .pdf ]
Keywords: Automata theory, Interactive visual tools, e-learning
[8] Rogério Reis and Nelma Moreira. Apoo: an environment for a first course in assembly language programming. SIGCSE Bulletin (ACM Special Interest Group on Computer Science Education), 33(2), December 2001. Extended version available as Technical Report [7].
[7] Rogério Reis and Nelma Moreira. Apoo: an environment for a first course in assembly language programming. Technical Report DCC-98-9, DCC-FC& LIACC, Universidade do Porto, 1998. [ .pdf.gz ]
Teaching the very basic concepts of a computer architecture, instruction set and operation based on a real microprocessor is usually an unfruitful task as the essential notions are obscured by the specific details of its architecture. A machine emulator has the benefit of providing a portable environment that can be run in several platforms and that can be easily adapted for pedagogical purposes. Apoo is a virtual machine with a very simple architecture and instruction set that mimics almost all the essential features of a modern microprocessor. The Apooi is an graphical environment that monitors the state of the machine during the execution of a program and allows the writing/editing/execution of programs in assembly language. The Apoot is a module that aims the grading of student programs based on a description of what should be the execution of the program for specified input data sets. This module was used to evaluate students programming skills in an interactive learning/grading system, not only allowing the detection of errors but trying to give extra information in order that the student could understand and correct his/her mistakes more easily.
Keywords: teaching, assembly language
[6] José Paulo Leal and Rogério Reis. Todo o que você sempre quis saber sobre correio electrónico mas não tinha ninguém a quem perguntar. In Fernando Silva e V.S. Costa, editor, A Universiade do Porto na Rede Global de Comunicações. CIUP, 1994.
[5] Rogério Reis. A infraestrutura de rede de comunicações. In Fernando Silva e V.S. Costa, editor, A Universiade do Porto na Rede Global de Comunicações. CIUP, 1994.
[4] Rogério Reis. Pine, um cliente amigável de email. In Fernando Silva e V.S. Costa, editor, A Universiade do Porto na Rede Global de Comunicações. CIUP, 1994.
[3] Rogério Reis. YAP: Estrutura interna. Master's thesis, Universidade do Porto, September 1990. Apresentado à Universidade do Porto no âmbito das Provas de acesso à categoria de assistente de investigação.
[2] M. Filgueiras, A.P. Tomás, N. Moreira, J.P. Leal, and R.Reis. Natural language and natural menus interfaces. In Preprints of the TC-7 IFIP International Conference Modelling the Innovation, Roma, March 1990. Also in M. Carnevale, M. Lucërtini, S. Nicosia (eds.), “Modelling the Innovation: Communications, Automation and Information Systems”, North-Holland, 1990.
[1] Luís Damas, Vitor Costa, Rogério Reis, and Rúben Azevedo. YAP Reference Manual, 1988.

This file was generated by bibtex2html 1.99.