Weakly recognizing morphisms from free semigroups onto finite semigroups are a classical way for defining the class of ω-regular languages, i.e., a set of infinite words is weakly recognizable by such a morphism if and only if it is accepted by some Büchi automaton. We study the descriptional complexity of various constructions and the computational complexity of various decision problems for weakly recognizing morphisms. The constructions we consider are the conversion from and to Büchi automata, the conversion into strongly recognizing morphisms, as well as complementation. We also show that the fixed membership problem is NC1-complete, the general membership problem is in L and that the inclusion, equivalence and universality problems are NL-complete. The emptiness problem is shown to be NL-complete if the input is given as a non-surjective morphism.
Accepté le :
DOI : 10.1051/ita/2018006
Mots-clés : semigroup, regular language, automata, decision problem, descriptional complexity, computational complexity, operations
@article{ITA_2019__53_1-2_1_0,
author = {Fleischer, Lukas and Kufleitner, Manfred},
title = {The complexity of weakly recognizing morphisms},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {1--17},
publisher = {EDP-Sciences},
volume = {53},
number = {1-2},
year = {2019},
doi = {10.1051/ita/2018006},
mrnumber = {3920824},
zbl = {1483.68166},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2018006/}
}
TY - JOUR AU - Fleischer, Lukas AU - Kufleitner, Manfred TI - The complexity of weakly recognizing morphisms JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2019 SP - 1 EP - 17 VL - 53 IS - 1-2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2018006/ DO - 10.1051/ita/2018006 LA - en ID - ITA_2019__53_1-2_1_0 ER -
%0 Journal Article %A Fleischer, Lukas %A Kufleitner, Manfred %T The complexity of weakly recognizing morphisms %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2019 %P 1-17 %V 53 %N 1-2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2018006/ %R 10.1051/ita/2018006 %G en %F ITA_2019__53_1-2_1_0
Fleischer, Lukas; Kufleitner, Manfred. The complexity of weakly recognizing morphisms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 1-2, pp. 1-17. doi : 10.1051/ita/2018006. http://archive.numdam.org/articles/10.1051/ita/2018006/
[1] , A syntactic congruence for rational ω-languages. Theor. Comput. Sci. 39 (1985) 333–335. | DOI | MR | Zbl
[2] , Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, in Proc.of the 18th Annual ACM Symposium on Theory of Computing, May 28–30, 1986, Berkeley, California, USA, edited by . ACM, NY (1986) 1–5. | Zbl
[3] , and , On uniformity within NC1. J. Comput. Syst. Sci. 41 (1990) 274–306. | DOI | MR | Zbl
[4] , Weak second-order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 6 (1960) 66–92. | DOI | MR | Zbl
[5] , The boolean formula value problem is in ALOGTIME, in Proc. of the 19th Annual ACM Symposium on Theory of Computing, New York, USA (1987) 123–131.
[6] and , The parallel complexity of finite-state automata problems. Inform. Comput. 97 (1992) 1–22. | DOI | MR | Zbl
[7] , Finite automata and unary languages. Theor. Comput. Sci. 47 (1986) 149–158. | DOI | MR | Zbl
[8] , Generating sets of the semigroup of all binary relations in a finite set. Doklady Akademii Nauk BSSR 12 (1968) 765–768. | MR | Zbl
[9] and , On deterministic finite automata and syntactic monoid size. Theor. Comput. Sci. 327 (2004) 319–347. | DOI | MR | Zbl
[10] , Nondeterministic space is closed under complementation. SIAM J. Comput. 17 (1988) 935–938. | DOI | MR | Zbl
[11] , Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11 (1975) 68–85. | DOI | MR | Zbl
[12] , and , New problems complete for nondeterministic log space. Math. Syst. Theory 10 (1976) 1–17. | DOI | MR | Zbl
[13] and , Two-generator semigroups of binary relations. J. Math. Psychol. 17 (1978) 236–246. | DOI | MR | Zbl
[14] , A proof of Devadze’s theorem on generators of the semigroup of boolean matrices. Semigroup Forum 83 (2011) 281–288. | DOI | MR | Zbl
[15] and , The equivalence problem for regular expressions with squaring requires exponential space, in 13th Annual Symposium on Switching and Automata Theory, IEEE Computer Society, Washington, DC, USA (1972) 125–129.
[16] , Computational Complexity. Addison Wesley, MA, USA (1994). | MR | Zbl
[17] , Variétés de semis groupes et mots infinis, in STACS 1986, Proceedings (1986) 180–191. | MR | Zbl
[18] and , Infinite words. Vol. 141 of Pure and Applied Mathematics. Elsevier, Berlin, Heidelberg, Germany, (2004). | Zbl
[19] , Varieties of Formal Languages. North Oxford Academic, London and Plenum, New-York (1986). | DOI | MR | Zbl
[20] and , Nondeterminism and the size of two way finite automata, in STOC 1978, Proceedings. ACM Press, San Diego, California, USA (1978) 275–286. | MR | Zbl
[21] , Introduction to the Theory of Computation. 1st edition, International Thomson Publishing, Boston, MA, USA (1996). | Zbl
[22] , The method of forced enumeration for nondeterministic automata. Acta Inform. 26 (1988) 279–284. | DOI | MR | Zbl
[23] , Automata on infinite objects, in Handbook of Theoretical Computer Science, chapter 4. Elsevier (1990) 133–191. | MR | Zbl
[24] , Introduction to Circuit Complexity. Springer, Berlin, Germany (1999). | DOI | MR | Zbl
[25] , Lower bounds for complementation of omega-automata via the full automata technique. Log. Meth. Comput.Sci. 4 (2008) lmcs:992. | DOI | MR | Zbl
Cité par Sources :
