The language complexity of problems in algebra and logic

Project Member(s): Elder, M.

Funding or Partner Organisation: Australian Research Council (ARC Discovery Projects)
Australian Research Council (ARC Discovery Projects)

Start year: 2016

Summary: The language complexity of problems in algebra and logic. This project focuses on a major problem at the intersection of algebra, logic and computer science, concerning equations over free groups and free monoids. Expected outcomes include a language-theoretic characterisation of solutions of equations in a wide class of groups and monoids, a language-theoretic understanding of the existential and first-order theories of free groups, and a classification of groups with indexed multiplication tables and EDT0L word problem. The project is designed to expand the frontiers of knowledge in theoretical computer science and pure mathematics, but in the longer term to deepen our understanding of computers, their computational power and intrinsic limitations.

Publications:

Berdinsky, D, Elder, M & Kruengthomya, P 2022, 'Cayley polynomial–time computable groups', Information and Computation, vol. 288, pp. 104768-104768.
View/Download from: Publisher's site

Berdinsky, D, Elder, M & Taback, J 2022, 'On the geometry of Cayley automatic groups', International Journal of Algebra and Computation, vol. 32, no. 03, pp. 383-409.
View/Download from: Publisher's site

Bishop, A & Elder, M 2022, 'A virtually 2-step nilpotent group with polynomial geodesic growth', Algebra and Discrete Mathematics, vol. 33, no. 2, pp. 21-28.
View/Download from: Publisher's site

Ciobanu, L & Elder, M 2021, 'The complexity of solution sets to equations in hyperbolic groups', Israel Journal of Mathematics, vol. 245, no. 2, pp. 869-920.
View/Download from: Publisher's site

Elder, M & Goh, YK 2021, '$k$-Pop Stack Sortable Permutations and $2$-Avoidance', The Electronic Journal of Combinatorics, vol. 28, no. 1.
View/Download from: Publisher's site

Diekert, V & Elder, M 2020, 'Solutions to twisted word equations and equations in virtually free groups', International Journal of Algebra and Computation, vol. 30, no. 04, pp. 731-819.
View/Download from: Publisher's site

Bishop, A 2019, 'Geodesic growth in virtually abelian groups', Journal of Algebra.
View/Download from: Publisher's site

Ciobanu, L & Elder, M 1970, 'Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE', Leibniz International Proceedings in Informatics, LIPIcs, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, Patras, Greece.
View/Download from: Publisher's site

Berlai, F & Ferov, M 2018, 'Separating cyclic subgroups in graph products of groups', Journal of Algebra, vol. 531, pp. 19-56.
View/Download from: Publisher's site

Bishop, A & Elder, M 1970, 'Bounded Automata Groups are co-ET0L', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), International Conference on Language and Automata Theory and Applications, Springer International Publishing, St. Petersburg, Russia, pp. 82-94.
View/Download from: Publisher's site

Ciobanu, L, Elder, M & Ferov, M 2017, 'Applications of L systems to group theory', International Journal of Algebra and Computation, vol. 28, no. 2, pp. 309-329.
View/Download from: Publisher's site

Diekert, V & Elder, M 1970, 'Solutions to twisted word equations and equations in virtually free groups', Leibniz International Proceedings in Informatics, LIPIcs, International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Warsaw, Poland, pp. 96:1-96:14.
View/Download from: Publisher's site

Elder, M & Goh, YK 1970, 'Permutations sorted by a finite and an infinite stack in series', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Language and Automata Theory and Applications, Springer, Ramat Gan, Israel, pp. 220-231.
View/Download from: Publisher's site

Ciobanu, L, Diekert, V & Elder, M 2015, 'Solution sets for equations over free groups are EDT0L languages', International Journal of Algebra and Computation, vol. 26, no. 5, pp. 843-886.
View/Download from: Publisher's site

FOR Codes: Group Theory and Generalisations, Computational Logic and Formal Languages, Combinatorics and Discrete Mathematics (excl. Physical Combinatorics), Expanding Knowledge in the Mathematical Sciences, Expanding Knowledge in the Information and Computing Sciences

Acknowledgement of Country

UTS acknowledges the Gadigal people of the Eora Nation, the Boorooberongal people of the Dharug Nation, the Bidiagal people and the Gamaygal people, upon whose ancestral lands our university stands. We would also like to pay respect to the Elders both past and present, acknowledging them as the traditional custodians of knowledge for these lands.