Complexity of atoms, combinatorially. (English) Zbl 1352.68130
Summary: Atoms of a (regular) language \(L\) were introduced by J. Brzozowski and H. Tamm in [Lect. Notes Comput. Sci. 6795, 105–116 (2011; Zbl 1221.68117)] as intersections of complemented and uncomplemented quotients of \(L\). They derived tight upper bounds on the complexity of atoms in [J. Brzozowski and H. Tamm, ibid. 7410, 50–61 (2012; Zbl 1352.68127)]. In [“Maximally atomic languages”, in: Proceedings of the 14th international conference on automata and formal languages, AFL 2014, Szeged, Hungary,
May 27–29, 2014, in: Electron. Proc. Theor. Comput. Sci. 151, 151–161 (2014)], J. Brzozowski and G. Davies characterized the regular languages meeting these bounds. To achieve these results, they used the so-called “átomaton” of a language, introduced by Brzozowski and Tamm in [Zbl 1221.68117]. In this note we give an alternative proof of their characterization, via a purely combinatorial approach.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
regular language; atoms of a language; syntactic left-congruence classes; automata theory; formal languagesReferences:
| [1] | André, Jorge M., Semigroups that contain all singular transformations, Semigroup Forum, 68, 2, 304-307 (2004) · Zbl 1069.20058 |
| [2] | Brzozowski, Janusz; Davies, Sylvie, Quotient complexities of atoms in regular ideal languages, Acta Cybern., 22, 2, 293-311 (2015) · Zbl 1349.68122 |
| [3] | Brzozowski, Janusz; Szykuła, Marek, Complexity of suffix-free regular languages, (Kosowski, Adrian; Walukiewicz, Igor, Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 9210 (2015), Springer International Publishing), 146-159 · Zbl 1434.68239 |
| [4] | Brzozowski, Janusz A.; Davies, Gareth, Maximal syntactic complexity of regular languages implies maximal quotient complexities of atoms (2012), CoRR |
| [5] | Brzozowski, Janusz A.; Davies, Gareth, Maximally atomic languages, (Ésik, Zoltán; Fülöp, Zoltán, Proceedings 14th International Conference on Automata and Formal Languages. Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 27-29, 2014. Proceedings 14th International Conference on Automata and Formal Languages. Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 27-29, 2014, EPTCS, vol. 151 (2014)), 151-161 · Zbl 1464.68156 |
| [6] | Brzozowski, Janusz A.; Tamm, Hellis, Theory of átomata, (Mauri, Giancarlo; Leporati, Alberto, Developments in Language Theory. Developments in Language Theory, Lecture Notes in Computer Science, vol. 6795 (2011), Springer: Springer Berlin, Heidelberg), 105-116 · Zbl 1221.68117 |
| [7] | Brzozowski, Janusz A.; Tamm, Hellis, Quotient complexities of atoms of regular languages, (Yen, Hsu-Chun; Ibarra, Oscar H., Developments in Language Theory. Developments in Language Theory, Lecture Notes in Computer Science, vol. 7410 (2012), Springer), 50-61 · Zbl 1352.68127 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
