Das, Anupam From QBFs to MALL and back via focussing. (English) Zbl 07268900 J. Autom. Reasoning 64, No. 7, 1221-1245 (2020). MSC: 68V15 PDF BibTeX XML Cite \textit{A. Das}, J. Autom. Reasoning 64, No. 7, 1221--1245 (2020; Zbl 07268900) Full Text: DOI
Place, Thomas; Zeitoun, Marc Going higher in first-order quantifier alternation hierarchies on words. (English) Zbl 1427.03050 J. ACM 66, No. 2, Article No. 12, 65 p. (2019). MSC: 03D05 03B25 03C13 PDF BibTeX XML Cite \textit{T. Place} and \textit{M. Zeitoun}, J. ACM 66, No. 2, Article No. 12, 65 p. (2019; Zbl 1427.03050) Full Text: DOI
D’Agostino, Giovanna; Lenzi, Giacomo The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs. (English) Zbl 1395.03009 Theor. Comput. Sci. 737, 40-61 (2018). MSC: 03B45 03B70 03D05 05C10 68Q45 91A43 PDF BibTeX XML Cite \textit{G. D'Agostino} and \textit{G. Lenzi}, Theor. Comput. Sci. 737, 40--61 (2018; Zbl 1395.03009) Full Text: DOI
Kufleitner, Manfred; Wächter, Jan Philipp The word problem for omega-terms over the Trotter-Weil hierarchy. (English) Zbl 1435.20065 Theory Comput. Syst. 62, No. 3, 682-738 (2018). MSC: 20M05 03B25 03D05 03D40 20M07 PDF BibTeX XML Cite \textit{M. Kufleitner} and \textit{J. P. Wächter}, Theory Comput. Syst. 62, No. 3, 682--738 (2018; Zbl 1435.20065) Full Text: DOI
Yakaryılmaz, A. Quantum alternation. (English) Zbl 1407.68182 Lobachevskii J. Math. 37, No. 6, 637-649 (2016). MSC: 68Q05 68Q12 81P68 PDF BibTeX XML Cite \textit{A. Yakaryılmaz}, Lobachevskii J. Math. 37, No. 6, 637--649 (2016; Zbl 1407.68182) Full Text: DOI
Lehtinen, Karoliina; Quickert, Sandra Deciding the first levels of the modal \(\mu\) alternation hierarchy by formula construction. (English) Zbl 1434.03073 Kreutzer, Stephan (ed.), 24th EACSL annual conference and 29th workshop on computer science logic, CSL’15, Berlin, Germany, September 7–10, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 41, 457-471 (2015). MSC: 03B45 03B70 68Q60 PDF BibTeX XML Cite \textit{K. Lehtinen} and \textit{S. Quickert}, LIPIcs -- Leibniz Int. Proc. Inform. 41, 457--471 (2015; Zbl 1434.03073) Full Text: DOI
Berkholz, Christoph; Krebs, Andreas; Verbitsky, Oleg Bounds for the quantifier depth in finite-variable logics: alternation hierarchy. (English) Zbl 1354.03038 ACM Trans. Comput. Log. 16, No. 3, Article No. 21, 26 p. (2015). MSC: 03C07 03C13 PDF BibTeX XML Cite \textit{C. Berkholz} et al., ACM Trans. Comput. Log. 16, No. 3, Article No. 21, 26 p. (2015; Zbl 1354.03038) Full Text: DOI
Haase, Christoph Subclasses of Presburger arithmetic and the weak EXP hierarchy. (English) Zbl 1394.68153 Proceedings of the joint meeting of the twenty-third EACSL annual conference on computer science logic, CSL, and the 2014 29th annual ACM/IEEE symposium on logic in computer science, LICS 2014, Vienna, Austria, July 14–18, 2014. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4503-2886-9). Paper No. 47, 10 p. (2014). MSC: 68Q15 03F30 68Q42 PDF BibTeX XML Cite \textit{C. Haase}, in: Proceedings of the joint meeting of the twenty-third EACSL annual conference on computer science logic, CSL, and the 2014 29th annual ACM/IEEE symposium on logic in computer science, LICS 2014, Vienna, Austria, July 14--18, 2014. Los Alamitos, CA: IEEE Computer Society. Paper No. 47, 10 p. (2014; Zbl 1394.68153) Full Text: DOI
Gutierrez, Julian; Klaedtke, Felix; Lange, Martin The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity. (English) Zbl 1327.03016 Theor. Comput. Sci. 560, Part 3, 292-306 (2014). Reviewer: Giacomo Lenzi (Fisciano) MSC: 03B45 05C90 05C20 PDF BibTeX XML Cite \textit{J. Gutierrez} et al., Theor. Comput. Sci. 560, Part 3, 292--306 (2014; Zbl 1327.03016) Full Text: DOI
Berkholz, Christoph; Krebs, Andreas; Verbitsky, Oleg Bounds for the quantifier depth in finite-variable logics: alternation hierarchy. (English) Zbl 1356.03077 Ronchi della Rocca, Simona (ed.), Computer science logic 2013. Selected papers of the 27th CSL workshop and 22nd annual conference of the European Association for Computer Science Logic (EACSL), Torino, Italy, September 2–5, 2013. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-60-6). LIPIcs – Leibniz International Proceedings in Informatics 23, 61-80 (2013). MSC: 03C07 03C13 PDF BibTeX XML Cite \textit{C. Berkholz} et al., LIPIcs -- Leibniz Int. Proc. Inform. 23, 61--80 (2013; Zbl 1356.03077) Full Text: DOI
Kufleitner, Manfred; Lauser, Alexander Around dot-depth one. (English) Zbl 1308.68071 Int. J. Found. Comput. Sci. 23, No. 6, 1323-1339 (2012). MSC: 68Q45 03D05 03B10 20M35 PDF BibTeX XML Cite \textit{M. Kufleitner} and \textit{A. Lauser}, Int. J. Found. Comput. Sci. 23, No. 6, 1323--1339 (2012; Zbl 1308.68071) Full Text: DOI
Kufleitner, Manfred; Weil, Pascal On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages. (English) Zbl 1256.03043 Log. Methods Comput. Sci. 8, No. 3, Paper No. 11, 30 p. (2012). MSC: 03D05 03B20 03B25 68Q70 PDF BibTeX XML Cite \textit{M. Kufleitner} and \textit{P. Weil}, Log. Methods Comput. Sci. 8, No. 3, Paper No. 11, 30 p. (2012; Zbl 1256.03043) Full Text: DOI
D’agostino, Giovanna; Lenzi, Giacomo On the \(\mu \)-calculus over transitive and finite transitive frames. (English) Zbl 1208.68145 Theor. Comput. Sci. 411, No. 50, 4273-4290 (2010). MSC: 68Q60 03B45 PDF BibTeX XML Cite \textit{G. D'agostino} and \textit{G. Lenzi}, Theor. Comput. Sci. 411, No. 50, 4273--4290 (2010; Zbl 1208.68145) Full Text: DOI
Sakamoto, Makoto; Katamune, Ryoju; Matsukawa, Tomoya; Furutani, Hiroshi; Kono, Michio; Ikeda, Satoshi; Ito, Takao; Uchida, Yasuo; Yoshinaga, Tsunehiro Some results about hierarchy and recognizability of four-dimensional synchronized alternating Turing machines. (English) Zbl 1339.68085 Lagakos, Stephen (ed.) et al., Recent advances in applied mathematics. Proceedings of the American conference on applied mathematics (AMERICAN-MATH ’10), Harvard University, Cambridge, MA, USA, January 27–29, 2010. Athens: WSEAS Press (ISBN 978-960-474-150-2). Mathematics and Computers in Science and Engineering, 201-205 (2009). MSC: 68Q05 PDF BibTeX XML Cite \textit{M. Sakamoto} et al., in: Recent advances in applied mathematics. Proceedings of the American conference on applied mathematics (AMERICAN-MATH '10), Harvard University, Cambridge, MA, USA, January 27--29, 2010. Athens: WSEAS Press. 201--205 (2009; Zbl 1339.68085)
Alberucci, Luca; Facchini, Alessandro The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems. (English) Zbl 1191.03012 J. Symb. Log. 74, No. 4, 1367-1400 (2009). Reviewer: Clemens Kupke (London) MSC: 03B45 03B70 05C57 68Q85 PDF BibTeX XML Cite \textit{L. Alberucci} and \textit{A. Facchini}, J. Symb. Log. 74, No. 4, 1367--1400 (2009; Zbl 1191.03012) Full Text: DOI
Weis, Philipp; Immerman, Neil Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. (English) Zbl 1168.03019 Log. Methods Comput. Sci. 5, No. 3, Paper 4, 23 p. (2009). MSC: 03C13 03B44 03C07 03D05 68Q17 68Q19 PDF BibTeX XML Cite \textit{P. Weis} and \textit{N. Immerman}, Log. Methods Comput. Sci. 5, No. 3, Paper 4, 23 p. (2009; Zbl 1168.03019) Full Text: DOI
Selivanov, Victor L. Hierarchies and reducibilities on regular languages related to modulo counting. (English) Zbl 1174.03016 Theor. Inform. Appl. 43, No. 1, 95-132 (2009). Reviewer: Daniela Marinescu (Braşov) MSC: 03D05 03C13 68Q15 PDF BibTeX XML Cite \textit{V. L. Selivanov}, Theor. Inform. Appl. 43, No. 1, 95--132 (2009; Zbl 1174.03016) Full Text: DOI EuDML
Manyem, Prabhu Syntactic characterizations of polynomial time optimization classes. (English) Zbl 1286.68216 Chic. J. Theor. Comput. Sci. 2008, Article No. 3, 24 p. (2008). MSC: 68Q19 68Q15 68Q25 90C60 PDF BibTeX XML Cite \textit{P. Manyem}, Chic. J. Theor. Comput. Sci. 2008, Article No. 3, 24 p. (2008; Zbl 1286.68216) Full Text: DOI
Weis, P.; Immerman, N. Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. (English) Zbl 1168.03328 Duparc, Jacques (ed.) et al., Computer science logic. 21st international workshop, CSL 2007, 16th annual conference of the EACSL, Lusanne, Switzerland, September 11–15, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74914-1/pbk). Lecture Notes in Computer Science 4646, 343-357 (2007). MSC: 03C13 03B44 03C07 03D05 68Q17 68Q19 PDF BibTeX XML Cite \textit{P. Weis} and \textit{N. Immerman}, Lect. Notes Comput. Sci. 4646, 343--357 (2007; Zbl 1168.03328) Full Text: DOI
Inoue, Atsuyuki; Ito, Akira; Inoue, Katsushi; Okazaki, Tokio Some properties of one-pebble Turing machines with sublogarithmic space. (English) Zbl 1081.68020 Theor. Comput. Sci. 341, No. 1-3, 138-149 (2005). MSC: 68Q05 PDF BibTeX XML Cite \textit{A. Inoue} et al., Theor. Comput. Sci. 341, No. 1--3, 138--149 (2005; Zbl 1081.68020) Full Text: DOI
Kreutzer, Stephan Expressive equivalence of least and inflationary fixed-point logic. (English) Zbl 1052.03012 Ann. Pure Appl. Logic 130, No. 1-3, 61-78 (2004). MSC: 03B70 03C98 PDF BibTeX XML Cite \textit{S. Kreutzer}, Ann. Pure Appl. Logic 130, No. 1--3, 61--78 (2004; Zbl 1052.03012) Full Text: DOI
Santocanale, Luigi The alternation hierarchy for the theory of \(\mu\)-lattices. (English) Zbl 0987.03057 Theory Appl. Categ. 9, 166-197 (2001). MSC: 03G30 06B25 68Q60 91A43 03B70 03C05 PDF BibTeX XML Cite \textit{L. Santocanale}, Theory Appl. Categ. 9, 166--197 (2001; Zbl 0987.03057) Full Text: EMIS EuDML
Bradfield, J. C. Fixpoint alternation: Arithmetic, transition systems, and the binary tree. (English) Zbl 0945.68126 Theor. Inform. Appl. 33, No. 4-5, 341-356 (1999). MSC: 68Q60 03D55 03D70 03D80 PDF BibTeX XML Cite \textit{J. C. Bradfield}, Theor. Inform. Appl. 33, No. 4--5, 341--356 (1999; Zbl 0945.68126) Full Text: DOI EuDML
Arnold, André The \(\mu\)-calculus alternation-depth hierarchy is strict on binary trees. (English) Zbl 0945.68118 Theor. Inform. Appl. 33, No. 4-5, 329-339 (1999). MSC: 68Q45 03D05 PDF BibTeX XML Cite \textit{A. Arnold}, Theor. Inform. Appl. 33, No. 4--5, 329--339 (1999; Zbl 0945.68118) Full Text: DOI EuDML
Bradfield, J. C. The modal mu-calculus alternation hierarchy is strict. (English) Zbl 0915.03017 Theor. Comput. Sci. 195, No. 2, 133-153 (1998). MSC: 03B45 PDF BibTeX XML Cite \textit{J. C. Bradfield}, Theor. Comput. Sci. 195, No. 2, 133--153 (1998; Zbl 0915.03017) Full Text: DOI
Schweikardt, Nicole The monadic quantifier alternation hierarchy over grids and pictures. (English) Zbl 0909.03009 Nielsen, Mogens (ed.) et al., Computer science logic. 11th international workshop, CSL ’97. Annual conference of the EACSL, Aarhus, Denmark, August 23–29, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1414, 441-460 (1998). MSC: 03B15 03D15 68R10 PDF BibTeX XML Cite \textit{N. Schweikardt}, Lect. Notes Comput. Sci. 1414, 441--460 (1998; Zbl 0909.03009)
Matz, Oliver One quantifier will do in existential monadic second-order logic over pictures. (English) Zbl 0912.03004 Brim, Luboš (ed.) et al., Mathematical foundations of computer science 1998. 23rd international symposium, MFCS ’98. Brno, Czech Republic, August 24–28, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1450, 751-759 (1998). MSC: 03B15 68Q45 03C13 PDF BibTeX XML Cite \textit{O. Matz}, Lect. Notes Comput. Sci. 1450, 751--759 (1998; Zbl 0912.03004)
Bradfield, J. C. Simplifying the modal mu-calculus alternation hierarchy. (English) Zbl 0892.03005 Morvan, Michel (ed.) et al., STACS 98. 15th annual symposium on Theoretical aspects of computer science. Paris, France, February 25–27, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1373, 39-49 (1998). MSC: 03B45 03F30 PDF BibTeX XML Cite \textit{J. C. Bradfield}, Lect. Notes Comput. Sci. 1373, 39--49 (1998; Zbl 0892.03005)
Geffert, Viliam A hierarchy that does not collapse: Alternations in low level space. (English) Zbl 0884.68054 RAIRO, Inform. Théor. Appl. 28, No. 5, 465-512 (1994). MSC: 68Q15 PDF BibTeX XML Cite \textit{V. Geffert}, RAIRO, Inform. Théor. Appl. 28, No. 5, 465--512 (1994; Zbl 0884.68054) Full Text: DOI EuDML
Rich, Craig A.; Slutzki, Giora The complexity of optimizing finite-state transducers. (English) Zbl 0830.68047 Theor. Comput. Sci. 129, No. 2, 323-336 (1994). Reviewer: P.van Emde Boas (Amsterdam) MSC: 68Q15 68Q45 PDF BibTeX XML Cite \textit{C. A. Rich} and \textit{G. Slutzki}, Theor. Comput. Sci. 129, No. 2, 323--336 (1994; Zbl 0830.68047) Full Text: DOI
von Braunmühl, Burchard Alternation for two-way machines with sublogarithmic space. (English) Zbl 0797.68056 Enjalbert, Patrice (ed.) et al., STACS 93. 10th annual symposium on theoretical aspects of computer science, Würzburg, Germany, February 25-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 665, 5-15 (1993). MSC: 68Q05 68Q15 03D10 PDF BibTeX XML Cite \textit{B. von Braunmühl}, Lect. Notes Comput. Sci. 665, 5--15 (1993; Zbl 0797.68056)
Istrail, Sorin An arithmetical hierarchy in propositional dynamic logic. (English) Zbl 0671.03022 Inf. Comput. 81, No. 3, 280-289 (1989). Reviewer: M.K.Valiev MSC: 03B70 68N01 68Q65 PDF BibTeX XML Cite \textit{S. Istrail}, Inf. Comput. 81, No. 3, 280--289 (1989; Zbl 0671.03022) Full Text: DOI
Jenner, Birgit; Kirsig, Bernd; Lange, Klaus-Jörn The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\). (English) Zbl 0668.68055 Inf. Comput. 80, No. 3, 269-288 (1989). Reviewer: U.Schöning MSC: 68Q05 68Q25 03D15 PDF BibTeX XML Cite \textit{B. Jenner} et al., Inf. Comput. 80, No. 3, 269--288 (1989; Zbl 0668.68055) Full Text: DOI
Jenner, Birgit; Kirsig, Bernd Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. (English) Zbl 0665.68038 RAIRO, Inf. Théor. Appl. 23, No. 1, 87-99 (1989). MSC: 68Q25 68Q45 03D15 PDF BibTeX XML Cite \textit{B. Jenner} and \textit{B. Kirsig}, RAIRO, Inform. Théor. Appl. 23, No. 1, 87--99 (1989; Zbl 0665.68038) Full Text: DOI EuDML
Jenner, Birgit; Kirsig, Bernd Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. (English) Zbl 0644.68056 STACS 88, Theoretical aspects of computer science, Proc. 5th Annu. Symp., Bordeaux/France 1988, Lect. Notes Comput. Sci. 294, 118-125 (1988). MSC: 68Q25 68Q45 03D15 PDF BibTeX XML
Rosier, Louis E.; Yen, Hsu-Chun Logspace hierarchies, polynomial time and the complexity of fairness problems concerning \(\omega\)-machines. (English) Zbl 0638.68031 SIAM J. Comput. 16, 779-807 (1987). Reviewer: E.Heinrich MSC: 68Q25 68Q45 68Q05 PDF BibTeX XML Cite \textit{L. E. Rosier} and \textit{H.-C. Yen}, SIAM J. Comput. 16, 779--807 (1987; Zbl 0638.68031) Full Text: DOI
McAloon, Ken Separation results for bounded alternation. (English) Zbl 0638.03037 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 265-271 (1986). Reviewer: E.Heinrich MSC: 03D15 68Q05 68Q25 PDF BibTeX XML
Perrin, Dominique; Pin, Jean-Eric First-order logic and star-free sets. (English) Zbl 0618.03015 J. Comput. Syst. Sci. 32, 393-406 (1986). Reviewer: Z.Stachniak MSC: 03D05 03B10 68Q45 PDF BibTeX XML Cite \textit{D. Perrin} and \textit{J.-E. Pin}, J. Comput. Syst. Sci. 32, 393--406 (1986; Zbl 0618.03015) Full Text: DOI
Lange, Klaus-Jörn Two characterizations of the logarithmic alternation hierarchy. (English) Zbl 0616.68050 Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 518-526 (1986). MSC: 68Q25 68Q05 03D15 PDF BibTeX XML
Rosier, Louis E.; Yen, Hsu-Chun Logspace hierarchies, polynomial time and the complexity of fairness problems concerning \(\omega\)-machines. (English) Zbl 0615.68041 Theoretical aspects of computer science, 3rd Annu. Symp., Orsay/France 1986, Lect. Notes Comput. Sci. 210, 306-320 (1986). Reviewer: Michal Chytil (Praha) MSC: 68Q25 68Q05 68Q45 PDF BibTeX XML Full Text: DOI
Woods, Alan Bounded arithmetic formulas and Turing machines of constant alternation. (English) Zbl 0615.03022 Logic colloq. ’84, Proc. Colloq., Manchester/U.K. 1984, Stud. Logic Found. Math. 120, 355-377 (1986). Reviewer: D.Mundici MSC: 03D10 03D15 03F30 PDF BibTeX XML
Ruzzo, Walter L.; Simon, Janos; Tompa, Martin Space-bounded hierarchies and probabilistic computations. (English) Zbl 0573.68021 J. Comput. Syst. Sci. 28, 216-230 (1984). Reviewer: A.Slisenko MSC: 68Q25 68Q05 PDF BibTeX XML Cite \textit{W. L. Ruzzo} et al., J. Comput. Syst. Sci. 28, 216--230 (1984; Zbl 0573.68021) Full Text: DOI
Ruohonen, Keijo On machine characterization of nonrecursive hierarchies. (English) Zbl 0562.03023 Ann. Univ. Turku., Ser. A I 186, 87-101 (1984). Reviewer: C.Calude MSC: 03D55 PDF BibTeX XML Cite \textit{K. Ruohonen}, Ann. Univ. Turku, Ser. A I 186, 87--101 (1984; Zbl 0562.03023)
Volger, Hugo A new hierarchy of elementary recursive decision problems. (English) Zbl 0531.03006 Methods. Oper. Res. 45, 509-519 (1983). Reviewer: A.Mullin MSC: 03B25 03D10 03D55 03B10 03D15 68Q25 68Q05 90C99 PDF BibTeX XML Cite \textit{H. Volger}, Methods Oper. Res. 45, 509--519 (1983; Zbl 0531.03006)