Rogério Reis


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


Publications

[132] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average complexity of strong star normal form. In Giovanni Pighizzini and Cezar Câmpeanu, editors, Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017, Proceedings, volume 10316 of Lecture Notes in Computer Science, pages 77--88. Springer, 2017. [ DOI ]
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 automa- ton, 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 automa- ton one is able to capture most of them. As a byproduct we define a dual version 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.

[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] 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.
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.

[129] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average complexity of strong star normal form. In Giovanni Pighizzini and Cezar Câmpeanu, editors, Description Complexity of Formal Systems (DCFS 2017), volume 10316 of LNCS, pages 77--88. Springer, 2017. [ .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 ε-follow automaton and the ratio of these expressions to standard regular expressions.

[128] Sabine Broda, António Machiavelo Nelma Moreira, and Rogério Reis. Automata for regular expressions with shuffle. Information and Computation, 2017.
[127] 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 ]
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
[126] Cezar Câmpeanu, Nelma Moreira, and Rogério Reis. Distinguishability operations and closures. Fundamenta Informaticae, 148(3--4):243--266, 2016. [ DOI ]
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
[125] Rogério Reis and Emanuele Rodaro. Ideal regular languages and strongly connected synchronizing automata. Theoretical Computer Science, 653:97--107, 2016. [ DOI ]
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
[124] 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.

[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] 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.

[121] 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 | http ]
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.

[120] 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.

[119] 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.

[118] 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.

[117] 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.

[116] 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.
[115] 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.

[114] 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.

[113] 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 ]
[112] 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.

[111] 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.

[110] 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.

[109] 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.

[108] 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.

[107] 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 ]
[106] 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.

[105] 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.

[104] 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.

[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] 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 ]
[101] 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.

[100] 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.

[99] 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 ]
[98] 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.

[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] 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 ]
[95] 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 ]
[94] 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 ]
[93] 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 ]
[92] 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 ]
[91] 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 ]
[90] Yuan Gao, Nelma Moreira, Rogério Reis, and Sheng Yu. A survey on state complexity. (Submitted), 2013. [ http ]
[89] 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.

[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] 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.

[86] 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 ]
[85] 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.

[84] 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..

[83] 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 ]
[82] 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 ]
[81] 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 ]
[80] 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 ]
[79] 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 ]
[78] 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 ]
[77] 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 ]
[76] 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 ]
[75] 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.

[74] António Machiavelo and Rogério Reis. Turing e a enigma. Boletim da Sociedade Portuguesa de Matemática, SPM, 67, 2012. MR3059023. [ .pdf ]
[73] 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.

[72] 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 ]
[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] 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 ]
[69] 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.

[68] 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
[67] 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 ]
[66] 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.

[65] 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.

[64] 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 ]
[63] 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.

[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] 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 ]
[60] 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.
[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] 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.

[57] 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.

[56] 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 ]
[55] 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.

[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] 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 ]
[52] 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 ]
[51] 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 ]
[50] 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 ]
[49] 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 ]
[48] 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.
[47] António Machiavelo and Rogério Reis. O problema do totobola. Boletim da Sociedade Portuguesa de Matemática,SPM, (61):39--45, 2009. [ .pdf ]
[46] 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 ]
[45] 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.

[44] 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.

[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. 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.

[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. 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..

[39] 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 ]
[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] 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 ]
[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. On the performance of automata minimization algorithms. Technical Report DCC-2007-03, DCC - FC & LIACC, Universidade do Porto, June 2007. [ .pdf ]
[33] 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 ]
[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] 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.

[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] Rogério Reis. Autómatos finitos: manipulação, geração e contagem. PhD thesis, Faculdade de Ciências da Universidade do Porto, 2007.
[27] 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 ]
[26] 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 ]
[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] 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
[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] 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.
[21] 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 ]
[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 [18]. [ .pdf ]
[19] 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.
[18] 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 ]
[17] 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 ]
[16] 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 ]
[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. 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
[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] 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.
[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] 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.
[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.98.