Relatório Anual 2012
Área: Semigroups, Automata and Languages
| Ano |
2012 |
| |
|
| Resumo |
|
| |
|
| Abstract |
J. Almeida (with O. Klíma) worked on representations of relatively free profinite semigroups, and applications to irreducibility, and order primitivity of pseudovarieties, and proved that complexity pseudovarieties are join irreducible.
J. Almeida (with A. Costa) studied geometric interpretation of Schützenberger groups of minimal subshifts as profinite Poincaré groups.
J. Almeida (with J. C. Costa, and partly with O. Klíma) worked on the Pin-Reutenauer procedure for the description of profinite closures of regular languages with respect to various pseudovarieties and related properties, and on the effective algebraic recognition of such closures for R.
S. Broda, N. Moreira, and R. Reis (with A. Machiavelo) wrote a review paper on the use of analytic combinatorics methods for the average analysis of regular languages.
S. Broda (with S. Alves) studied the Formula-Tree Proof method in terms of game-semantics.
S. Broda and N. Moreira (with R. Almeida) worked on decision procedures for propositional Hoare Logic based on derivatives.
A. J. Cain (with R. Gray & A. Malheiro) constructed a finite Gröbner-Shirshov basis for the Plactic algebra and used this to prove the Plactic monoid is biautomatic, thus proving a conjecture by Zelmanov. This work was extended to a more general study of monoids with homogeneous presentations, such as Chinese and hypoplactic monoids.
A. J. Cain (with N. Rukuc) proved that unary FA-presentable algebras are closed under forming finitely generated subalgebras, but that this does not hold in the non-unary case.
A. J. Cain (with V. Maltcev) studied of connections between the various generalizations of hyperbolicity from groups to semigroups, and proved that, unlike a group, a monoid with linear Dehn function need not have a regular language of normal forms.
M. Delgado worked on creating open source visualisation software for GAP objects.
M. Delgado researched on numerical semigroups.
N. Moreira (with D. Pereira & S. Sousa) worked on the formalization of decidability procedures for equivalence of Kleene Albegra with Tests expressions in the Coq proof assistant.
N. Moreira and R. Reis (with E. Maia) studied of the worst-case operational transition and state complexity on incomplete deterministic finite automata.
A. Moura studied the pseudovariety DA, and, in particular, worked on proving that DA is omega-reducible which, together with the result of the decidability of the word problem for omega-terms over DA (already achieved), leads to the result of the tameness of the pseudovariety DA.
L. Oliveira studied of the set of ideals of a biordered set: the main result obtained states that this set of ideals together with a natural operation becomes a pseudosemilattice.
L. Oliveira worked on embedding semigroups into semibands, obtained a new embedding and compared it with other known embeddings.
L. Oliveira (with K. Auinger) discovered a new model of the free pseudosemilattice that seems to be more transparent than older models and used it to obtain interesting results about pseudosemilattices and about locally inverse semigroups: for example, a finite pseudosemilattice is finitely based if and only if it is a finite semigroup.
L. Oliveira studied the lattice of varieties of pseudosemilattices and used the new model of the free pseudosemilattice to obtain improvements of results presented in his Ph.D. dissertation.
R. Reis (with I. Amorim and A. Machiavelo) studied linear and quasi-linear invertible automata.
R. Reis and E. Rodaro studied strongly connected ideal languages.
E. Rodaro studied the use of Schutzenberger automata in the study of algorithmic problems and structural properties of amalgams of inverse semigroups.
E. Rodaro studied the descriptional complexity of some operators in the class of DFA.
E. Rodaro studied of the computational complexity in recognizing synchronizing automata with finitely many synchronizing words and never-minimal automata.
E. Rodaro worked on an attempt to solve Frankl's conjecture obtaining some bounds and some results for finite families of upper closed sets.
E. Rodaro studied the use of stochastic continous cellular automata for modeling a highway via fuzzy decision rules and implemented a simulator using python.
E. Rodaro worked on solving the Cerny conjecture via the study of synchronizing automata.
E. Rodaro and P. V. Silva studied fixed points of endomorphisms and automorphism in graph groups (with Sykiotis), and in trace monoids and free inverse monoids.
P. V. Silva studied the fixed points of virtually free group endomorphism.
P. V. Silva (with J. Rhodes) studied boolean representations of graphs and simplicial complexes. |
| |
|
Indicadores de Execução
| A - Publicações |
Previsto |
Realizado |
Livros
|
0 |
0 |
Artigos em revistas internacionais
|
0 |
17 |
Artigos em revistas nacionais
|
0 |
0 |
| B - Comunicações |
Previsto |
Realizado |
Em congressos científicos internacionais
|
0 |
11 |
Em congressos científicos nacionais
|
0 |
0 |
| C- Relatórios |
0 |
22 |
| D - Organização de seminários e conferências |
0 |
6 |
| E - Formação avançada |
Previsto |
Realizado |
Teses de doutoramento
|
0 |
1 |
Teses de mestrado
|
0 |
1 |
Outra
|
0 |
0 |
| F - Modelos |
0 |
0 |
| G - Aplicações computacionais |
0 |
0 |
| H - Instalações piloto |
0 |
0 |
| I - Protótipos laboratoriais |
0 |
0 |
| J - Patentes |
0 |
0 |
Publicações
Publicações
(publicadas de facto ) |
J. Almeida, A. Costa, On the transition semigroups of centrally labeled Rauzy graphs, Internat. J. Algebra Comput. 22 (2012). DOI:10.1142/S021819671250018X.
J. Almeida, A. Costa, Presentations of SchĂźtzenberger groups of minimal subshifts, Israel J. Math. (2012). DOI:10.1007/s11856-012-0139-4.
M. Almeida, N. Moreira, R. Reis, Finite automata minimization algorithms, in J. Wang, editor, Handbook of Finite State Based Models and Applications, Discrete Mathematics and Its Applications, pages 145-170. Chapman and Hall/CRC Press, 2012.
R. Almeida, S. Broda, N. Moreira, Deciding KAT and Hoare logic with derivatives, in 3rd International Symposium on Games, Automata, Logics, and Formal Verification, Proceedings, vol. 96, pages 127-140, Napoli, Italy, September 6th-8th 2012. Electronic Proceedings in Theoretical Computer Science. DOI: 10.4204/EPTCS.96.10
I. Amorim, A. Machiavelo, R. Reis. Formal power series and the invertibility of finite linear transducers, in R. Freund, M. Holzer, B. Truthe, U. Ultes-Nitschs, editors, Fourth Workshop on Non-Classical Medels for Automata and Applications (NCMA 2012), pages 33-48. Austrian Computer Society, 2012.
S. Broda, A. Machiavelo, N. Moreira, R. Reis, On the average size of Glushkov and partial derivative automata, Internat. J. Found. Comput. Sci. 23, no. 5 (2012), 969-984.
A. J. Cain, N. Ruskuc, R. M. Thomas, Unary FA-presentable semigroups, Internat. J. Algebra Comput. 22, no. 4 (2012). DOI:10.1142/S0218196712500385.
A. J. Cain, R. Gray, N. Ruskuc, Green index in semigroup theory: generators, presentations, and automatic structures, Semigroup Forum 85, no. 3 (2012), 448-476.
A. J. Cain, V. Maltcev, Context-free rewriting systems and word-hyperbolic structures with uniqueness, Internat. J. Algebra Comput. 22, no. 7 (2012). DOI:10.1142/S0218196712500610.
A. Cherubini, C. Nuccio, E. Rodaro, Multilinear equations in amalgams of finite inverse semigroups, Internat. J. of Algebra Comput. 21, no. 1-2 (2011), 35-59.
A. Cherubini, C. Nuccio, E. Rodaro, Amalgams of finite inverse semigroups and deterministic context-free languages, Semigroup Forum 85, no. 1 (2012), 129-146.
A. Moura, E-local pseudovarieties, Semigroup Forum, 85, no. 1 (2012), 169-181.
D. Pereira, N. Moreira, S. 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, 2012. DOI: 10.1007/978-3-642-33314-9_7
N. Pinto, P. V. Silva, A. Amorim, A general method to infer the usefulness of the X-chromosomal markers in kinship testing, Forensic Science International: Genetics 6 (2012), 198-207.
E. Pribavkina, E. Rodaro, Synchronizing automata with finitely many minimal synchronizing words, Inform. and Comput., 209, no. 3 (2011), 568-579.
E. V. Pribavkina, E. Rodaro, State complexity for code operators,
Internat. J. Found. Comput. Sci. 22, no. 7 (2011), 1669-1681.
E. Pribavkina, E. Rodaro, Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-Complete, LNCS 6735, CiE 2011, 230-238.
J. Rhodes, P. V. Silva, Further results on monoids acting on trees, Internat. J. Algebra Comput. 22, no.4 (2012), 1250034 (69 pages).
E. Rodaro, P. V. Silva, Amalgams of inverse semigroups and reversible two-counter machines, J. Pure Appl. Algebra, 217 (2013), 585-597.
E. Rodaro, P.V. Silva, Never minimal automata and the rainbow bipartite subgraph problem, LNCS, 6795, DLT 2011, 374-385.
E. Rodaro, O. Yeldan, A continuous cellular automata approach to highway traffic modeling (Extended abstract for ICTCS 2012 Electronic proceedings).
P. V. Silva, Fixed points of endomorphisms of certain free products, RAIRO Theoret. Inf. Appl. 46 (2012), 165-179.
P. V. Silva, Groups and automata: a perfect match, In: M. Kutrib, N. Moreira, R. Reis, editors, DCFS 2012, LNCS 7386, Springer, pages 50-63, 2012.
A. Yeldan, A. Colorni, A. Lué, E. Rodaro, A stochastic continuous cellular automata traffic flow model with a multi-agent fuzzy system, Procedia - Social and Behavioral Sciences 54 (2012), 1350-1359. |
| |
|
Publicações
(aceites para publicação) |
J. Almeida, A. Cardoso, A sequence of weakly monotonic automata with increasing level, Int. J. Algebra, to appear.
A. J. Cain, Hyperbolicity of monoids presented by confluent monadic rewriting systems, Beiträge zur Algebra und Geometrie, to appear. DOI: 10.1007/s13366-012-0116-4.
M. Delgado, J. I. Farrán, P. A. García-Sánchez, D. Llena, On the generalized Feng-Rao numbers of numerical semigroups generated by intervals, Mathematics of Computation, to appear.
E. Maia, N. Moreira, R. Reis, Incomplete transition complexity of some basic operations, in P. van Emde Boas et al., editor, SOFSEM 2013: Theory and Practice of Computer Science, no. 7741 in Lecture Notes on Computer Science, pages 319-330. Springer-Verlag, 2013, to appear.
E. Rodaro, P. V. Silva, M. Sykiotis, Fixed points of endomorphisms of graph groups, J. Group Theory, to appear.
P. V. Silva, Fixed points of endomorphisms of virtually free groups, Pacific J. Math, to appear.
|
| |
|
| Pré-publicações |
J. Almeida, J. C. Costa, M. Zeitoun, McCammonds normal forms for free aperiodic semigroups revisited, preprint CMUP 2012-3.
M. Almeida, N. Moreira and R. Reis, Incremental DFA minimization.
K. Auinger, L. Oliveira, On the variety of strict pseudosemilattices.
S. Broda, A. Machiavelo, N. Moreira, R. Reis, An Introduction to Descriptional Complexity of Regular Languages through Analytic Combinatorics, Technical Report DCC-2012-05, DCC-FC, Univ. Porto, July, 2012.
A. J. Cain, R. Gray, A. Malheiro, Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids. arXiv: 1205.4885.
A. J. Cain, V. Maltcev. Finitely presented monoids with linear Dehn
function need not have regular cross-sections. arXiv:1203.0473.
A. J. Cain, N. Ruskuc, Subalgebras of FA-presentable algebras arXiv:1206.5548.
A.J. Cain, R. Gray, A. Malheiro, Complete rewriting systems and biautomaticity for Chinese and hypoplactic monoids.
A. Cherubini, T. Jajcayova, E. Rodaro, Maximal subgroups of amalgams of finite inverse semigroups.
M. Delgado, V. H. Fernandes, Rees quotients of numerical semigroups. arXiv:1210.2910.
Y. Gao, N. Moreira, R. Reis, S. Yu. A Survey on State Complexity.
M. Ladra, P. V. Silva, E. Ventura, Bounding the gap between a free group (outer) automorphism and its inverse. arXiv:1212.6749, preprint, CMUP 2012-39.
N. Moreira, D. Pereira, S. Melo de Sousa, Mechanization of an algorithm for deciding KAT terms equivalence. Technical Report DCC-2012-04, DCC-FC, Univ. Porto, May 2012.
L. Oliveira, On the question of embedding a semigroup into a semiband.
J.-E. Pin, P. V. Silva, A noncommutative extension of Mahler's theorem on interpolation series, HAL:00654030, preprint, CMUP 2012-1.
J. Rhodes, P. V. Silva, A new notion of vertex independence and rank for finite graphs, arXiv:1201.3984, preprint, CMUP 2012-8.
J. Rhodes, P. V. Silva, Matroids, hereditary collections and simplicial complexes having boolean representations, arXiv:1210.7064, preprint, 2012.
E. Rodaro, Union-Closed Families vs Upward-closed families of sets. arXiv:1208.5371.
E. Rodaro, P. V. Silva, Fixed points of endomorphisms of trace monoids. arXiv:1211.4517.
E. Rodaro, P. V. Silva, On periodic points of free inverse monoid endomorphisms. arXiv: 1212.4284.
P. V. Silva, Groups and automata: a perfect match, preprint, CMUP 2012-16.
P. V. Silva, X. Soler-Escrivá, E. Ventura, Finite automata for Schreier graphs of virtually free groups, arXiv:1112.5709, preprint, CMUP 2012-2.
|
|
|