Bell, Paul C.; Reidenbach, Daniel; Shallit, Jeffrey O. Unique decipherability in formal languages. (English) Zbl 1508.68184 Theor. Comput. Sci. 804, 149-160 (2020). MSC: 68Q45 PDF BibTeX XML Cite \textit{P. C. Bell} et al., Theor. Comput. Sci. 804, 149--160 (2020; Zbl 1508.68184) Full Text: DOI Link
Kawachi, Akinori; Ogihara, Mitsunori; Uchizawa, Kei Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs. (English) Zbl 1434.68315 Theor. Comput. Sci. 762, 25-40 (2019). MSC: 68Q80 37B15 68Q25 PDF BibTeX XML Cite \textit{A. Kawachi} et al., Theor. Comput. Sci. 762, 25--40 (2019; Zbl 1434.68315) Full Text: DOI
Kawachi, Akinori; Ogihara, Mitsunori; Uchizawa, Kei Generalized predecessor existence problems for Boolean finite dynamical systems. (English) Zbl 1441.68140 Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 8, 13 p. (2017). MSC: 68Q80 37B15 68Q25 PDF BibTeX XML Cite \textit{A. Kawachi} et al., LIPIcs -- Leibniz Int. Proc. Inform. 83, Article 8, 13 p. (2017; Zbl 1441.68140) Full Text: DOI
Podolskii, Vladimir V. Bounds in ontology-based data access via circuit complexity. (English) Zbl 1378.68038 Theory Comput. Syst. 61, No. 2, 464-493 (2017). MSC: 68P15 68Q25 PDF BibTeX XML Cite \textit{V. V. Podolskii}, Theory Comput. Syst. 61, No. 2, 464--493 (2017; Zbl 1378.68038) Full Text: DOI
Bienvenu, Meghyn; Bourgaux, Camille Inconsistency-tolerant querying of description logic knowledge bases. (English) Zbl 1358.68285 Pan, Jeff Z. (ed.) et al., Reasoning web. Logical foundation of knowledge graph construction and query answering. 12th international summer school 2016, Aberdeen, UK, September 5–9, 2016. Tutorial lectures. Cham: Springer (ISBN 978-3-319-49492-0/pbk; 978-3-319-49493-7/ebook). Lecture Notes in Computer Science 9885, 156-202 (2017). MSC: 68T35 68T27 68T30 PDF BibTeX XML Cite \textit{M. Bienvenu} and \textit{C. Bourgaux}, Lect. Notes Comput. Sci. 9885, 156--202 (2017; Zbl 1358.68285) Full Text: DOI Link
Glaßer, Christian; Schmitz, Heinz; Selivanov, Victor Efficient algorithms for membership in Boolean hierarchies of regular languages. (English) Zbl 1348.68103 Theor. Comput. Sci. 646, 86-108 (2016). MSC: 68Q45 68Q15 PDF BibTeX XML Cite \textit{C. Glaßer} et al., Theor. Comput. Sci. 646, 86--108 (2016; Zbl 1348.68103) Full Text: DOI
Holzer, Markus; Jakobi, Sebastian Boundary sets of regular and context-free languages. (English) Zbl 1332.68114 Theor. Comput. Sci. 610, Part A, 59-77 (2016). MSC: 68Q45 68Q17 PDF BibTeX XML Cite \textit{M. Holzer} and \textit{S. Jakobi}, Theor. Comput. Sci. 610, Part A, 59--77 (2016; Zbl 1332.68114) Full Text: DOI
Bell, Paul C.; Reidenbach, Daniel; Shallit, Jeffrey Factorization in formal languages. (English) Zbl 1434.68232 Potapov, Igor (ed.), Developments in language theory. 19th international conference, DLT 2015, Liverpool, UK, July 27–30, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9168, 97-107 (2015). MSC: 68Q45 68R15 PDF BibTeX XML Cite \textit{P. C. Bell} et al., Lect. Notes Comput. Sci. 9168, 97--107 (2015; Zbl 1434.68232) Full Text: DOI arXiv Link
van Emde Boas, Peter Turing machines for dummies. Why representations do matter. (English) Zbl 1298.68092 Bieliková, Mária (ed.) et al., SOFSEM 2012: Theory and practice of computer science. 38th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 21–27, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-27659-0/pbk). Lecture Notes in Computer Science 7147, 14-30 (2012). MSC: 68Q05 PDF BibTeX XML Cite \textit{P. van Emde Boas}, Lect. Notes Comput. Sci. 7147, 14--30 (2012; Zbl 1298.68092) Full Text: DOI
Murphy, Niall; Woods, Damien The computational power of membrane systems under tight uniformity conditions. (English) Zbl 1214.68159 Nat. Comput. 10, No. 1, 613-632 (2011). MSC: 68Q05 68Q17 PDF BibTeX XML Cite \textit{N. Murphy} and \textit{D. Woods}, Nat. Comput. 10, No. 1, 613--632 (2011; Zbl 1214.68159) Full Text: DOI Link
Jacobé de Naurois, Paulin; Mogbil, Virgile Correctness of linear logic proof structures is NL-complete. (English) Zbl 1222.03069 Theor. Comput. Sci. 412, No. 20, 1941-1957 (2011). MSC: 03F52 03F07 68Q17 PDF BibTeX XML Cite \textit{P. Jacobé de Naurois} and \textit{V. Mogbil}, Theor. Comput. Sci. 412, No. 20, 1941--1957 (2011; Zbl 1222.03069) Full Text: DOI
Michail, Othon; Chatzigiannakis, Ioannis; Spirakis, Paul G. Mediated population protocols. (English) Zbl 1218.68082 Theor. Comput. Sci. 412, No. 22, 2434-2450 (2011). MSC: 68Q05 68M07 68Q15 PDF BibTeX XML Cite \textit{O. Michail} et al., Theor. Comput. Sci. 412, No. 22, 2434--2450 (2011; Zbl 1218.68082) Full Text: DOI
Williams, Ryan Parallelizing time with polynomial circuits. (English) Zbl 1209.68256 Theory Comput. Syst. 48, No. 1, 150-169 (2011). MSC: 68Q05 68Q10 68Q15 94C10 PDF BibTeX XML Cite \textit{R. Williams}, Theory Comput. Syst. 48, No. 1, 150--169 (2011; Zbl 1209.68256) Full Text: DOI
Glaßer, Christian; Schmitz, Heinz Languages of dot-depth 3/2. (English) Zbl 1141.68037 Theory Comput. Syst. 42, No. 2, 256-286 (2008). MSC: 68Q45 PDF BibTeX XML Cite \textit{C. Glaßer} and \textit{H. Schmitz}, Theory Comput. Syst. 42, No. 2, 256--286 (2008; Zbl 1141.68037) Full Text: DOI
Cai, J.-Y.; Sivakumar, D. Resolution of Hartmanis’ conjecture for NL-hard sparse sets. (English) Zbl 0945.68102 Theor. Comput. Sci. 240, No. 2, 257-269 (2000). MSC: 68Q45 PDF BibTeX XML Cite \textit{J. Y. Cai} and \textit{D. Sivakumar}, Theor. Comput. Sci. 240, No. 2, 257--269 (2000; Zbl 0945.68102) Full Text: DOI
Cai, Jin-Yi; Sivakumar, D. Sparse hard sets for P: Resolution of a conjecture of Hartmanis. (English) Zbl 0936.68046 J. Comput. Syst. Sci. 58, No. 2, 280-296 (1999). MSC: 68Q15 PDF BibTeX XML Cite \textit{J.-Y. Cai} and \textit{D. Sivakumar}, J. Comput. Syst. Sci. 58, No. 2, 280--296 (1999; Zbl 0936.68046) Full Text: DOI Link
Lisitsa, Alexei; Sazonov, Vladimir \(\Delta\)-languages for sets and LOGSPACE computable graph transformers. (English) Zbl 0903.68057 Theor. Comput. Sci. 175, No. 1, 183-222 (1997). MSC: 68P15 PDF BibTeX XML Cite \textit{A. Lisitsa} and \textit{V. Sazonov}, Theor. Comput. Sci. 175, No. 1, 183--222 (1997; Zbl 0903.68057) Full Text: DOI
Jukna, Stasys A note on read-\(k\) times branching programs. (English) Zbl 0889.68021 RAIRO, Inform. Théor. Appl. 29, No. 1, 75-83 (1995). MSC: 68N15 PDF BibTeX XML Cite \textit{S. Jukna}, RAIRO, Inform. Théor. Appl. 29, No. 1, 75--83 (1995; Zbl 0889.68021) Full Text: DOI EuDML
Lange, Klaus-Jörn; Reinhardt, Klaus Empty alternation. (English) Zbl 1493.68151 Privara, Igor (ed.) et al., Mathematical foundations of computer science 1994. 19th international symposium, MFCS ’94, Košice, Slovakia, August 22–26, 1994. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 841, 494-503 (1994). MSC: 68Q15 68Q04 68Q45 PDF BibTeX XML Cite \textit{K.-J. Lange} and \textit{K. Reinhardt}, Lect. Notes Comput. Sci. 841, 494--503 (1994; Zbl 1493.68151) Full Text: DOI
Condon, Anne; Hernek, Diane Random walks on colored graphs. (English) Zbl 0792.05123 Random Struct. Algorithms 5, No. 2, 285-303 (1994). MSC: 05C80 60G50 05C15 PDF BibTeX XML Cite \textit{A. Condon} and \textit{D. Hernek}, Random Struct. Algorithms 5, No. 2, 285--303 (1994; Zbl 0792.05123) Full Text: DOI
Andraşiu, Mircea; Păun, Gheroghe; Dassow, Jürgen; Salomaa, Arto Language-theoretic problems arising from Richelieu cryptosystems. (English) Zbl 0797.68094 Theor. Comput. Sci. 116, No. 2, 339-357 (1993). MSC: 68Q45 94A60 PDF BibTeX XML Cite \textit{M. Andraşiu} et al., Theor. Comput. Sci. 116, No. 2, 339--357 (1993; Zbl 0797.68094) Full Text: DOI
Borodin, A.; Razborov, A.; Smolensky, R. On lower bounds for read-\(k\)-times branching programs. (English) Zbl 0777.68043 Comput. Complexity 3, No. 1, 1-18 (1993). Reviewer: S.P.Yukna (Dortmund) MSC: 68Q25 68Q05 PDF BibTeX XML Cite \textit{A. Borodin} et al., Comput. Complexity 3, No. 1, 1--18 (1993; Zbl 0777.68043) Full Text: DOI
Krause, Matthias; Meinel, Christoph; Waack, Stephan Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines. (English) Zbl 0768.68017 RAIRO, Inform. Théor. Appl. 26, No. 4, 345-362 (1992). MSC: 68Q15 68Q05 PDF BibTeX XML Cite \textit{M. Krause} et al., RAIRO, Inform. Théor. Appl. 26, No. 4, 345--362 (1992; Zbl 0768.68017) Full Text: DOI EuDML
Stewart, Iain A. Using the Hamiltonian path operator to capture NP. (English) Zbl 0752.68041 J. Comput. Syst. Sci. 45, No. 1, 127-151 (1992). MSC: 68Q15 PDF BibTeX XML Cite \textit{I. A. Stewart}, J. Comput. Syst. Sci. 45, No. 1, 127--151 (1992; Zbl 0752.68041) Full Text: DOI
Wigderson, Avi The complexity of graph connectivity. (English) Zbl 1493.68163 Havel, Ivan M. (ed.) et al., Mathematical foundations of computer science 1992. 17th international symposium, Prague, Czechoslovakia, August 24–28, 1992. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 629, 112-132 (1992). MSC: 68Q25 05C40 PDF BibTeX XML Cite \textit{A. Wigderson}, Lect. Notes Comput. Sci. 629, 112--132 (1992; Zbl 1493.68163) Full Text: DOI
Slobodová, Anna Some properties of space-bounded synchronized alternating Turing machines with universal states only. (English) Zbl 0754.68047 Theor. Comput. Sci. 96, No. 2, 411-419 (1992). Reviewer: M.Zimand (Bucureşti) MSC: 68Q05 68Q15 PDF BibTeX XML Cite \textit{A. Slobodová}, Theor. Comput. Sci. 96, No. 2, 411--419 (1992; Zbl 0754.68047) Full Text: DOI
Krause, Matthias Separating \(\oplus{}L\), from \(L\), \(NL\), co-\(NL\), and \(AL=P\) for oblivious turing machines of linear access. (English) Zbl 0766.68042 RAIRO, Inform. Théor. Appl. 26, No. 6, 507-522 (1992). MSC: 68Q15 68Q05 PDF BibTeX XML Cite \textit{M. Krause}, RAIRO, Inform. Théor. Appl. 26, No. 6, 507--522 (1992; Zbl 0766.68042) Full Text: DOI EuDML
Barrington, David A. Mix; McKenzie, Pierre Oracle branching programs and Logspace versus \(P^*\). (English) Zbl 0744.68107 Inf. Comput. 95, No. 1, 96-115 (1991). Reviewer: C.Meinel MSC: 68R05 68Q15 68Q25 PDF BibTeX XML Cite \textit{D. A. M. Barrington} and \textit{P. McKenzie}, Inf. Comput. 95, No. 1, 96--115 (1991; Zbl 0744.68107) Full Text: DOI
Chen, Jianer; Cox, Jim; Mishra, Bud An NL hierarchy. (English) Zbl 0735.68030 Inf. Process. Lett. 39, No. 1, 21-26 (1991). MSC: 68Q15 PDF BibTeX XML Cite \textit{J. Chen} et al., Inf. Process. Lett. 39, No. 1, 21--26 (1991; Zbl 0735.68030) Full Text: DOI
Krause, Matthias; Meinel, Christoph; Waack, Stephan Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\). (English) Zbl 0749.68036 Theor. Comput. Sci. 86, No. 2, 267-275 (1991). Reviewer: A.V.Anisimov (Kiev) MSC: 68Q15 68Q05 PDF BibTeX XML Cite \textit{M. Krause} et al., Theor. Comput. Sci. 86, No. 2, 267--275 (1991; Zbl 0749.68036) Full Text: DOI
Buhrman, Harry; Homer, Steven; Torenvliet, Leen Completeness for nondeterministic complexity classes. (English) Zbl 0745.68046 Math. Syst. Theory 24, No. 3, 179-200 (1991). MSC: 68Q15 PDF BibTeX XML Cite \textit{H. Buhrman} et al., Math. Syst. Theory 24, No. 3, 179--200 (1991; Zbl 0745.68046) Full Text: DOI
Ranjan, Desh; Chang, Richard; Hartmanis, Juris Space bounded computations: Review and new separation results. (English) Zbl 0745.68051 Theor. Comput. Sci. 80, No. 2, 289-302 (1991). MSC: 68Q15 PDF BibTeX XML Cite \textit{D. Ranjan} et al., Theor. Comput. Sci. 80, No. 2, 289--302 (1991; Zbl 0745.68051) Full Text: DOI
Lautemann, Clemens The complexity of graph languages generated by hyperedge replacement. (English) Zbl 0725.68055 Acta Inf. 27, No. 5, 399-421 (1990). Reviewer: G.Slutzki (Ames) MSC: 68Q25 68Q42 PDF BibTeX XML Cite \textit{C. Lautemann}, Acta Inf. 27, No. 5, 399--421 (1990; Zbl 0725.68055) Full Text: DOI
Cai, Jin-yi; Hemachandra, Lane A. On the power of parity polynomial time. (English) Zbl 0718.68038 Math. Syst. Theory 23, No. 2, 95-106 (1990). MSC: 68Q15 03D15 68Q05 PDF BibTeX XML Cite \textit{J.-y. Cai} and \textit{L. A. Hemachandra}, Math. Syst. Theory 23, No. 2, 95--106 (1990; Zbl 0718.68038) Full Text: DOI
Toda, Seinosuke On the complexity of topological sorting. (English) Zbl 0713.68025 Inf. Process. Lett. 35, No. 5, 229-233 (1990). Reviewer: T.Walsh MSC: 68Q15 68Q25 68R10 68Q10 PDF BibTeX XML Cite \textit{S. Toda}, Inf. Process. Lett. 35, No. 5, 229--233 (1990; Zbl 0713.68025) Full Text: DOI
Meinel, Christoph Polynomial size \(\Omega\)-branching programs and their computational power. (English) Zbl 0705.68052 Inf. Comput. 85, No. 2, 163-182 (1990). MSC: 68Q15 68Q05 PDF BibTeX XML Cite \textit{C. Meinel}, Inf. Comput. 85, No. 2, 163--182 (1990; Zbl 0705.68052) Full Text: DOI
Engelfriet, Joost; Leih, George Complexity of boundary graph languages. (English) Zbl 0701.68062 RAIRO, Inform. Théor. Appl. 24, No. 3, 267-274 (1990). MSC: 68Q45 68Q15 68Q42 PDF BibTeX XML Cite \textit{J. Engelfriet} and \textit{G. Leih}, RAIRO, Inform. Théor. Appl. 24, No. 3, 267--274 (1990; Zbl 0701.68062) Full Text: DOI EuDML
Buntrock, Gerhard; Hoene, Albrecht Reversals and alternation. (English) Zbl 1492.68053 Monien, Burkhard (ed.) et al., STACS 89. 6th annual symposium on theoretical aspects of computer science, Paderborn, FRG, February 16–18, 1989. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 349, 218-228 (1989). MSC: 68Q15 68Q04 68Q45 PDF BibTeX XML Cite \textit{G. Buntrock} and \textit{A. Hoene}, Lect. Notes Comput. Sci. 349, 218--228 (1989; Zbl 1492.68053) Full Text: DOI
Shoudai, Takayoshi The lexicographically first topological order problem is NLOG-complete. (English) Zbl 0689.68070 Inf. Process. Lett. 33, No. 3, 121-124 (1989). MSC: 68Q25 68P10 03D15 PDF BibTeX XML Cite \textit{T. Shoudai}, Inf. Process. Lett. 33, No. 3, 121--124 (1989; Zbl 0689.68070) 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
Szelepcsényi, Róbert The method of forced enumeration for nondeterministic automata. (English) Zbl 0638.68046 Acta Inf. 26, No. 3, 279-284 (1988). Reviewer: R.Szelepcsényí MSC: 68Q45 68Q05 PDF BibTeX XML Cite \textit{R. Szelepcsényi}, Acta Inf. 26, No. 3, 279--284 (1988; Zbl 0638.68046) Full Text: DOI