Publications

[1] Ivone Amorim, António Machiavelo, and Rogério Reis. On the number of non-equivalent linear transducers. In (Submitted), 2014.
[2] Ivone Amorim, António Machiavelo, and Rogério Reis. On the invertibility of finite linear transducers. RAIRO - Theoretical Informatics and Applications, 2014. (To appear).
[3] Marco Almeida, Nelma Moreira, and Rogério Reis. Incremental dfa minimisation. RAIRO - Theoretical Informatics and Applications, 2014. (To appear).
[4] Rizó Isrof. Guitar: um ambiente de vizualização de autómatos. Technical Report DCC-2013-12, DCC-FC, Universidade do Porto, September 2013. [ .pdf ]
[5] Rafaela Bastos, Nelma Moreira, and Rogério Reis. Manipulation of extended regular expressions with derivatives. Technical Report DCC-2013-13, DCC-FC, Universidade do Porto, September 2013. [ .pdf ]
[6] 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 ]
[7] 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. [ DOI | http ]
[8] David Pereira. Towards Towards Certified Program Logics for the Verification of Imperative Programs. PhD thesis, Universidade do Porto, April 2013. [ .pdf ]
[9] Ricardo Almeida, Sabine Broda, and Nelma Moreira. Kat and Hoare logic with derivatives. Technical Report DCC-2013-04, DCC - FC & CMUP, Universidade do Porto, February 2013. [ .pdf ]
[10] Jason Bell, Janusz Brzozowski, Nelma Moreira, and Rogério Reis. Symmetric groups and quotient complexity of boolean operations. (Submitted), 2013. [ http ]
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.

Keywords: boolean operation, quotient complexity, regular language, state complexity, symmetric group, transition semigroup
[11] Davide Nabais. Desco: a web-base knowledge system for descriptional complexity of formal languages. Master's thesis, Faculdade de Ciências da Universidade do Porto, Julho 2013. [ .pdf ]
[12] 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 ]
[13] 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 ]
[14] Eva Maia, Nelma Moreira, and Rogério Reis. Transition complexity of basic operations on infinite and finite regular languages. (Submitted), 2013.
Keywords: transition complexity, automata theory, finite languages, descriptional complexity
[15] Nelma Moreira, David Pereira, and Simão Melo de Sousa. Deciding Kleene algebra terms (in)equivalence in Coq. (Submitted), 2013.
[16] Yuan Gao, Nelma Moreira, Rogério Reis, and Sheng Yu. A survey on state complexity. (Submitted), 2013.
[17] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. A hitchhiker's guide to descriptional complexity through analytic combinatorics. (Submitted), 2013.
[18] Nelma Moreira and Rogério Reis. Preface. selected papers of ciaa 2012. International Journal of Fundations of Computer Science, 2013. (To appear).
[19] Martin Kutrib, Nelma Moreira, and Rogério Reis. Preface. selected papers of dcfs 2012. journal of automata, languages and combinatorics. JALC, 2013. (To appear).
[20] 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.

[21] Rogério Reis and Emanuele Rodaro. On strongly connected ideal languages. Technical Report DCC-2013-01, DCC-FC Universidade do Porto, January 2013. [ .pdf ]
[22] Emanuele Rodaro and Rogério Reis. On strongly connected ideal languages. In Juhani Karhumäki and Luca Zamboni, editors, 9th International Conference on WORDS, LNCS. Springer-Verlag, 2013.
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.

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

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

[26] Nelma Moreira, David Pereira, and Simão Melo de Sousa. On the mechanisation of rely-guarantee in Coq. Technical Report DCC-2013-03, DCC - FC & LIACC, Universidade do Porto, January 2013. [ .pdf ]
In this report we describe the formalisation of a simple imperative language with concurrent/parallel and atomic execution statements within the Coq theorem prover. Our formalisation includes the specification of a simple imperative programming language with statements for parallel and atomic execution of code, an underlying small-step structural semantics and a proof system that is sound with respect to such semantics. With this formalisation we give a first step towards the certified verification of shared- variable concurrent/parallel programs under the context of Cliff Jones? Rely-Guarantee reasoning and in the logic of Coq.

[27] 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. [ http ]
[28] Ricardo Almeida, Sabine Broda, and Nelma Moreira. Deciding KAT and Hoare logic with derivatives. In 3rd International Symposium on Games, Automata, Logics, and Formal Verification, Proceedings, volume 96, page 127?140, Napoli, Italy, September 6th-8th 2012. Electronic Proceedings in Theoretical Computer Science. [ DOI | .pdf ]
Kleene algebra with tests (KAT) is an equational system for program verification, which is the combination of Boolean algebra (BA) and Kleene algebra (KA), the algebra of regular expressions. In particular, KAT subsumes the propositional fragment of Hoare logic (PHL) which is a formal system for the specification and verification of programs, and that is currently the base of most tools for checking program correctness. Both the equational theory of KAT and the encoding of PHL in KAT are known to be decidable. In this paper we present a new decision procedure for the equivalence of two KAT expressions based on the notion of partial derivatives. We also introduce the notion of derivative modulo particular sets of equations. With this we extend the previous procedure for deciding PHL. Some experimental results are also presented.

[29] Ricardo Almeida. Decision algorithms for Kleene algebra with tests and Hoare logic. Master's thesis, Faculdade de Ciências da Universidade do Porto, July 2012. [ .pdf ]
[30] 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 ]
Nowadays, an increasing attention is being given to the study of the descriptional complexity on 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. We finalize with some new asymptotic average case results for several ε-NFA constructions, presented in a unified framework.

[31] 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. [ DOI | http ]
[32] 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. [ DOI | http ]
[33] Davide Nabais, Nelma Moreira, and Rogério Reis. Desco: a web based information system for descriptional complexity results. DesCo: a Web Based Information System for Descriptional Complexity Results, University of Cambrige, June 2012.
[34] Nelma Moreira, David Pereira, and Simão Melo de Sousa. Mechanization of an algorithm for deciding KAT terms equivalence. Technical Report DCC-2012-04, DCC-FC, Universidade do Porto, May 2012. [ .pdf ]
[35] André de Matos Pedro, Maria João Frade, and Simão Melo de Sousa. Learning generalized semi-markov processes: From stochastic discrete event systems to testing and verification. Technical Report DCC-2012-01, DCC-FC, Universidade do Porto, April 2012. [ .pdf ]
[36] 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 ]
[37] 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 ]
[38] André de Matos Pedro, Paul Andrew Crocker, and Simão Melo de Sousa. Learning stochastic timed automata from sample executions. In Tiziana Margaria and Bernhard Steffen, editors, Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change - 5th International Symposium, ISoLA 2012, Heraklion, LNCS, pages 508-523. Springer-Verlag, 2012.
[39] David Pereira Nelma Moreira and Simão Melo de Sousa. Deciding regular expressions (in-)equivalence in Coq. In T. G. Griffin and W. Kahl, editors, 13th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS 13). Proceedings, volume 7560 of Lecture Notes on Computer Science, pages 98-113. Springer-Verlag, 2012. [ DOI | .pdf ]
This work presents a mechanically verified implementation of an algorithm for deciding regular expression (in-)equivalence within the COQ proof assistant. This algorithm decides regular expression equivalence through an iterated process of testing the equivalence of their partial derivatives and also does not construct the underlying automata. Our implementation has a refutation step that improves the general efficiency of the decision procedure by enforcing the in-equivalence of regular expressions at early stages of computation. Recent theoretical and experimental research provide evidence that this method is, on average, more efficient than the classical methods based in automata. We present some performance tests and comparisons with similar approaches.

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

[41] 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. Austrian Computer Society, 2012.
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.

[42] 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 ]
[43] 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, 2010. 2011. Springer-Verlag. [ DOI | .pdf ]
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.

[44] José Bacelar Almeida, Nelma Moreira, David Pereira, and Simão Melo de Sousa. Partial derivative automata formalized in Coq. 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 59-68, Winnipeg, MA, Canada, August, 2010. 2011. Springer-Verlag. [ DOI | .pdf ]
In this paper we present a computer assisted proof of the correctness of a partial derivative automata construction from a regular expression within the Coq proof assistant. This proof is part of a formalization of Kleene algebra and regular languages in Coq towards their usage in program certification.

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

[47] Marco Almeida. Equivalence of regular languages: an algorithmic approach and complexity analysis. PhD thesis, Universidade do Porto, April 2011. [ .pdf ]
[48] 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
[49] 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 ]
[50] Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average state complexity of partial derivative automata. International Journal of Foundations of Computer Science, 22(7):1593-1606, 2011. [ 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.

[51] Nelma Moreira, David Pereira, and Simão Melo de Sousa. Deciding regular expressions (in-)equivalence in coq. Technical Report DCC-2011-06, DCC-FC, Universidade do Porto, 2011.
[52] 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 ]
[53] 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. [ 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.

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

[55] 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ão Rasga, editors, Proceedings of 6th Conference on Computability in Europe (CIE 2010), pages 194-203, Ponta Delgada, Azores, Portugal, June/July 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] 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, 9-10 Setembro 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.

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

[58] José Alves, Nelma Moreira, and Rogério Reis. XML description for automata manipulations. In Alberto Simões, 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.

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

This file was generated by bibtex2html 1.97.