@InProceedings{MRV99,
address   = "Tokyo, Japan",
author    = "McKenzie, Pierre and Reinhardt, Klaus and Vinay, V.",
booktitle = "Computing and Combinatorics",
doi       = "10.1007/3-540-48686-0_19",
editor    = "Asano, Takano and Imai, Hideki and Lee, D. T. and Nakano, Shin-ichi and Tokuyama, Takeshi",
month     = "7",
pages     = "194--203",
publisher = "Springer Berlin, Heidelberg",
title     = "Circuits and Context-Free Languages",
volume    = "5",
year      = "1999",
}

@Article{Y23,
author    = "Tomoyuki Yamakami",
doi       = "10.1080/23799927.2023.2166872",
journal   = "International Journal of Computer Mathematics: Computer Systems Theory",
number    = "1",
pages     = "1--31",
publisher = "Taylor \& Francis",
title     = "Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata",
volume    = "8",
year      = "2023",
}

@Book{HU79,
author    = "Hopcroft, John E. and Ullman, Jeffrey D.",
edition   = "1",
publisher = "Addison-Wesley",
title     = "Introduction to Automata Theory, Languages, and Computation",
year      = "1979",
}

@InProceedings{FLR96,
address   = "Hyderabad, India",
author    = "Fernau, Henning and Lange, Klaus-Jörn and Reinhardt, Klaus",
booktitle = "Foundations of Software Technology and Theoretical Computer Science",
doi       = "10.1007/3-540-62034-6_57",
editor    = "Chandru, V. and Vinay, V.",
month     = "12",
pages     = "286--297",
publisher = "Springer Berlin, Heidelberg",
title     = "Advocating Ownership",
volume    = "16",
year      = "1996",
}

@Article{R01,
author  = "Reynolds, M.",
doi     = "10.2307/2695091",
journal = "Journal of Symbolic Logic",
number  = "3",
pages   = "1011--1057",
title   = "An Axiomatization of Full Computation Tree Logic",
volume  = "66",
year    = "2001",
}

@Article{BC91,
author  = "David A. {Mix Barrington} and James Corbett",
doi     = "10.1016/0304-3975(91)90357-8",
journal = "Theoretical Computer Science",
number  = "2",
pages   = "357--362",
title   = "A note on some languages in uniform ACC0",
url     = "https://www.sciencedirect.com/science/article/pii/0304397591903578",
volume  = "78",
year    = "1991",
}

@Article{MT07,
author  = "Meena Mahajan and Jacobo Toran",
issn    = "0252-9742",
journal = "Bulletin of the European Association for Theoretical Computer Science",
number  = "91",
pages   = "42--56",
title   = "Polynomial Size Log Depth Circuits : Between NC1 and AC1",
url     = "https://www.eatcs.org/images/bulletin/beatcs91.pdf",
year    = "2007",
}

@InProceedings{CM20,
address   = "New York, NY, USA",
author    = "Cook, James and Mertz, Ian",
booktitle = "Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing",
doi       = "10.1145/3357713.3384316",
isbn      = "9781450369794",
location  = "Chicago, IL, USA",
pages     = "752--760",
publisher = "Association for Computing Machinery",
series    = "STOC 2020",
title     = "Catalytic approaches to the tree evaluation problem",
year      = "2020",
}

@InProceedings{S77,
address   = "Berlin, Heidelberg",
author    = "Sudborough, I. H.",
booktitle = "Mathematical Foundations of Computer Science 1977",
editor    = "Gruska, Jozef",
isbn      = "978-3-540-37285-1",
pages     = "493--503",
publisher = "Springer Berlin Heidelberg",
title     = "Time and tape bounded auxiliary pushdown automata",
year      = "1977",
}

@InProceedings{C70,
address   = "New York, NY, USA",
author    = "Cook, Stephen A.",
booktitle = "Proceedings of the Second Annual ACM Symposium on Theory of Computing",
doi       = "10.1145/800161.805151",
isbn      = "9781450374699",
location  = "Northampton, Massachusetts, USA",
pages     = "70--72",
publisher = "Association for Computing Machinery",
series    = "STOC '70",
title     = "Path systems and language recognition",
year      = "1970",
}

@InProceedings{CM24,
address   = "New York, NY, USA",
author    = "Cook, James and Mertz, Ian",
booktitle = "Proceedings of the 56th Annual ACM Symposium on Theory of Computing",
doi       = "10.1145/3618260.3649664",
pages     = "1268--1278",
publisher = "ACM",
title     = "Tree Evaluation Is in Space O(log n · log log n)",
year      = "2024",
}

@InProceedings{GG65,
author    = "Ginsburg, Seymour and Greibach, Sheila",
booktitle = "6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965)",
doi="10.1109/FOCS.1965.7",
pages     = "203--220",
title     = "Deterministic Context Free Languages",
year      = "1965",
}

@Article{GKM08,
author    = "Gál, Anna and Koucký, Michal and McKenzie, Pierre",
doi       = "10.1007/s00224-007-9049-y",
journal   = "Theory of Computing Systems",
number    = "2",
pages     = "159--184",
title     = "Incremental Branching Programs",
volume    = "43",
year      = "2008",
}

@Article{G73,
author  = "Greibach, Sheila A.",
doi     = "10.1137/0202025",
journal = "SIAM Journal on Computing",
pages   = "304--310",
number  = "4",
title   = "The Hardest Context-Free Language",
volume  = "2",
year    = "1973",
}

@MastersThesis{Li05,
author  = "Limaye, Nutan",
month   = "April",
school  = "Anna University, Chennai",
title   = "Parallel Complexity Classes Around LogCFL",
year    = "2005",
}

@InProceedings{C73,
address   = "New York, NY, USA",
author    = "Cook, Stephen A.",
booktitle = "Proceedings of the Fifth Annual ACM Symposium on Theory of Computing",
doi       = "10.1145/800125.804032",
isbn      = "9781450374309",
pages     = "29--33",
publisher = "Association for Computing Machinery",
title     = "An observation on time-storage trade off",
year      = "1973",
series    = "STOC '73",
}

@Article{S78,
author    = "Sudborough, Ivan Hal",
journal   = "Journal of the ACM (JACM)",
number    = "3",
pages     = "405--414",
publisher = "ACM New York, NY, USA",
title     = "On the Tape Complexity of Deterministic Context-Free Languages",
volume    = "25",
year      = "1978",
}

@Article{BC89,
author  = "David A. {Mix Barrington} and James Corbett",
doi     = "10.1016/0020-0190(89)90052-5",
journal = "Information Processing Letters",
number  = "5",
pages   = "251--256",
title   = "On the Relative Complexity of Some Languages in NC1",
volume  = "32",
year    = "1989",
}

@InProceedings{LMM08,
address   = "Moscow, Russia",
author    = "Limaye, Nutan and Mahajan, Meena and Meyer, Antoine",
booktitle = "CSR 2008",
doi       = "10.1007/978-3-540-79709-8\_25",
pages     = "240--251",
publisher = "Springer",
series    = "Lecture Notes in Computer Science",
title     = "On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata",
volume    = "5010",
year      = "2008",
}

@Article{LMM09,
author  = "Limaye, Nutan and Mahajan, Meena and Meyer, Antoine",
journal = "Journal of Automata Languages and Combinatorics",
title   = "On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata",
volume  = "14",
year    = "2009",
}

@InCollection{H92,
author    = "Michael A. Harrison",
booktitle = "Theoretical Studies in Computer Science",
doi       = "https://doi.org/10.1016/B978-0-12-708240-0.50007-1",
editor    = "Jeffrey D. Ullman",
isbn      = "978-0-12-708240-0",
pages     = "15--71",
publisher = "Academic Press",
title     = "Proving Nonmembership in Certain Families of Context Free Languages",
year      = "1992",
}

@Book{U92,
author    = "Ullman, Jeffrey D.",
isbn      = "9780127082400",
publisher = "Academic Press Inc.",
title     = "Theoretical Studies in Computer Science",
year      = "1992",
}

@Article{C71a,
author    = "Cook, Stephen A.",
journal   = "Journal of the ACM (JACM)",
number    = "1",
pages     = "4--18",
publisher = "ACM New York, NY, USA",
title     = "Characterizations of pushdown machines in terms of time-bounded computers",
volume    = "18",
year      = "1971",
}

@Article{JL76,
author  = "Jones, Neil D. and Laaser, William T.",
doi     = "10.1016/0304-3975(76)90068-2",
journal = "Theoretical Computer Science",
number  = "1",
pages   = "105--117",
title   = "Complete Problems for Deterministic Polynomial Time",
volume  = "3",
year    = "1976"
}

@Book{GHR95,
author    = "Greenlaw, Raymond and Hoover, H James and Ruzzo, Walter L",
publisher = "Oxford University Press, USA",
title     = "Limits to Parallel Computation: P-completeness Theory",
year      = "1995",
}

@InProceedings{MPPS20,
author    = "Mraz, Frantisek and Pardubska, Dana and Platek, Martin and Sima, Jiri",
booktitle = "ITAT",
pages     = "51--58",
title     = "Pumping Deterministic Monotone Restarting Automata and DCFL",
year      = "2020",
}

@Article{THM04,
author = "Tantau, Till and Hemaspaandra, Lane and Mukherji, Proshanto",
title  = "Overhead-Free Computation, DCFLs, and CFLs",
year   = "2004",
}

@Article{BM91,
author    = "Barrington, David A Mix and McKenzie, Pierre",
journal   = "Information and Computation",
pages     = "96--115",
publisher = "Elsevier",
title     = "Oracle Branching Programs and Logspace versus P",
volume    = "95",
year      = "1991",
}

@Article{CMWBS12,
address   = "New York, NY, USA",
author    = "Cook, Stephen and McKenzie, Pierre and Wehr, Dustin and Braverman, Mark and Santhanam, Rahul",
doi       = "10.1145/2077336.2077337",
journal   = "ACM Trans. Comput. Theory",
number    = "2",
publisher = "Association for Computing Machinery",
title     = "Pebbles and Branching Programs for Tree Evaluation",
volume    = "3",
year      = "2012",
}

@InProceedings{L01,
address   = "Berlin, Heidelberg",
author    = "Lohrey, Markus",
booktitle = "Rewriting Techniques and Applications",
editor    = "Middeldorp, Aart",
isbn      = "978-3-540-45127-3",
pages     = "201--215",
publisher = "Springer Berlin Heidelberg",
title     = "On the Parallel Complexity of Tree Automata",
year      = "2001",
}

@InProceedings{RM97,
author    = "Raz, R. and McKenzie, P.",
booktitle = "Proceedings 38th Annual Symposium on Foundations of Computer Science",
doi       = "10.1109/SFCS.1997.646112",
pages     = "234--243",
title     = "Separation of the Monotone NC Hierarchy",
year      = "1997",
}

@Article{JS21,
author  = "Jancar, Petr and Sima, Jiri",
title   = "Simplest Non-Regular Deterministic Context-Free Language",
journal = "arXiv preprint arXiv:2102.10416",
year    = "2021",
}

@Article{CM87,
author    = "Cook, Stephen A and McKenzie, Pierre",
journal   = "Journal of Algorithms",
number    = "3",
pages     = "385--394",
publisher = "Elsevier",
title     = "Problems Complete for Deterministic Logarithmic Space",
volume    = "8",
year      = "1987",
}

@InProceedings{BCMSW09,
address   = "Berlin, Heidelberg",
author    = "Braverman, Mark and Cook, Stephen and McKenzie, Pierre and Santhanam, Rahul and Wehr, Dustin",
booktitle = "Mathematical Foundations of Computer Science 2009",
doi       = "10.1007/978-3-642-03816-7_16",
isbn      = "978-3-642-03816-7",
pages     = "175--186",
publisher = "Springer Berlin Heidelberg",
title     = "Branching Programs for Tree Evaluation",
year      = "2009",
}

@Article{R81,
author    = "Ruzzo, Walter L",
journal   = "Journal of Computer and System Sciences",
number    = "3",
pages     = "365--383",
publisher = "Elsevier",
title     = "On Uniform Circuit Complexity",
volume    = "22",
year      = "1981"
}

@InProceedings{CD06,
address   = "Berlin, Heidelberg",
author    = "Chakraborty, Tanmoy and Datta, Samir",
booktitle = "FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science",
doi       = "10.1007/11944836_8",
editor    = "Arun-Kumar, S. and Garg, Naveen",
isbn      = "978-3-540-49995-4",
pages     = "57--68",
publisher = "Springer Berlin Heidelberg",
title     = "One-Input-Face MPCVP Is Hard for L, But in LogDCFL",
year      = "2006"
}

@InProceedings{DG25,
address   = "Singapore",
author    = "Datta, Samir and Gupta, Chetan",
booktitle = "WALCOM: Algorithms and Computation",
doi       = "10.1007/978-981-96-2845-2_9",
editor    = "Nakano, Shin-ichi and Xiao, Mingyu",
isbn      = "978-981-96-2845-2",
pages     = "127--142",
publisher = "Springer Nature Singapore",
title     = "Evaluating Monotone Circuits on Surfaces",
year      = "2025"
}

@Article{BIS90,
author  = "Barrington, David A Mix and Immerman, Neil and Straubing, Howard",
doi     = "https://doi.org/10.1016/0022-0000(90)90022-D",
journal = "Journal of Computer and System Sciences",
number  = "3",
pages   = "274-306",
title   = "On uniformity within NC1",
volume  = "41",
year    = "1990"
}

@PhdThesis{K11,
author  = "Kintali, Shiva",
isbn    = "978-1-267-21250-4",
journal = "ProQuest Dissertations and Theses",
title   = "Realizable paths and the NL vs L problem",
pages   = "73",
year    = "2011"
}

@Article{BCGR92,
author  = "Buss, S. and Cook, S. and Gupta, A. and Ramachandran, V.",
doi     = "10.1137/0221046",
journal = "SIAM Journal on Computing",
number  = "4",
pages   = "755--780",
title   = "An Optimal Parallel Algorithm for Formula Evaluation",
volume  = "21",
year    = "1992"
}

@Book{St12,
author    = "Jukna, Stasys",
publisher = "Springer",
title     = "Boolean Function Complexity: Advances and Frontiers",
volume    = "27",
year      = "2012"
}

@Article{Lo05,
author  = "Lohrey, Markus",
doi     = "10.1142/S0129054105003248",
journal = "International Journal of Foundations of Computer Science",
number  = "04",
pages   = "707--722",
title   = "Decidability and Complexity in Automatic Monoids",
volume  = "16",
year    = "2005"
}

@InProceedings{R97,
address   = "Berlin, Heidelberg",
author    = "Reinhardt, Klaus",
booktitle = "STACS 97",
doi       = "10.1007/BFb0023470",
editor    = "Reischuk, Rüdiger and Morvan, Michel",
isbn      = "978-3-540-68342-1",
pages     = "329--338",
publisher = "Springer Berlin Heidelberg",
title     = "Strict Sequential P-Completeness",
year      = "1997"
}

@Article{G76,
author    = "Galil, Zvi",
journal   = "Mathematical systems theory",
number    = "1",
pages     = "211--228",
publisher = "Springer",
title     = "Some Open Problems in the Theory of Computation as Questions About Two-Way Deterministic Pushdown Automaton Languages",
volume    = "10",
year      = "1976"
}

@Article{BCDRT89,
author  = "Borodin, Allan and Cook, Stephen A. and Dymond, Patrick W. and Ruzzo, Walter L. and Tompa, Martin",
doi     = "10.1137/0218038",
journal = "SIAM Journal on Computing",
number  = "3",
pages   = "559--578",
title   = "Two Applications of Inductive Counting for Complementation Problems",
volume  = "18",
year    = "1989"
}

@Article{DR00,
address   = "New York, NY, USA",
author    = "Dymond, Patrick W. and Ruzzo, Walter L.",
doi       = "10.1145/331605.331607",
journal   = "J. ACM",
number    = "1",
pages     = "16--45",
publisher = "Association for Computing Machinery",
title     = "Parallel RAMs with Owned Global Memory and Deterministic Context-Free Language Recognition",
volume    = "47",
year      = "2000"
}

@InProceedings{V87,
address   = "New York, NY, USA",
author    = "Venkateswaran, H.",
booktitle = "Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing",
doi       = "10.1145/28395.28411",
isbn      = "0897912217",
pages     = "141--150",
publisher = "Association for Computing Machinery",
series    = "STOC '87",
title     = "Properties that Characterize LOGCFL",
volume    = "999",
year      = "1987"
}

@Article{C85,
author  = "Cook, Stephen A.",
doi     = "10.1016/S0019-9958(85)80041-3",
journal = "Information and Control",
number  = "1",
pages   = "2--22",
title   = "A Taxonomy of Problems with Fast Parallel Algorithms",
volume  = "64",
year    = "1985"
}

@Article{E97,
author  = "Etessami, Kousha",
doi     = "10.1006/jcss.1997.1485",
journal = "Journal of Computer and System Sciences",
number  = "3",
pages   = "400--411",
title   = "Counting Quantifiers, Successor Relations, and Logarithmic Space",
volume  = "54",
year    = "1997"
}

@Book{P14,
address   = "Paris, France",
author    = "Périfel, Sylvain",
language  = "fr",
month     = "4",
publisher = "Ellipses-Marketing",
title     = "Complexité Algorithmique",
year      = "2014"
}

@Article{I88,
author  = "Immerman, Neil",
doi     = "10.1137/0217058",
journal = "SIAM Journal on Computing",
number  = "5",
pages   = "935--938",
title   = "Nondeterministic Space is Closed under Complementation",
volume  = "17",
year    = "1988"
}

@Article{S88,
author  = "Szelepcsényi, Róbert",
day     = "01",
doi     = "10.1007/BF00299636",
journal = "Acta Informatica",
month   = "11",
number  = "3",
pages   = "279--284",
title   = "The Method of Forced Enumeration for Nondeterministic Automata",
volume  = "26",
year    = "1988"
}

@Article{J75,
author  = "Jones, Neil D.",
doi     = "10.1016/S0022-0000(75)80050-X",
journal = "Journal of Computer and System Sciences",
number  = "1",
pages   = "68--85",
title   = "Space-bounded Reducibility Among Combinatorial Problems",
volume  = "11",
year    = "1975"
}

@Book{J17,
author    = "Johnsonbaugh, Richard",
language  = "en",
publisher = "Addison-Wesley Longman",
title     = "Discrete mathematics (8th ed.)",
year      = "2017"
}

@Book{R02,
author    = "Rosen, Kenneth H.",
publisher = "Chenelière McGraw-Hill",
title     = "Mathématiques Discrètes",
year      = "2002"
}

@Article{MP19,
author  = "van Melkebeek, Dieter and Prakriya, Gautam",
doi     = "10.1137/17M1130538",
journal = "SIAM Journal on Computing",
number  = "3",
pages   = "979-1021",
title   = "Derandomizing Isolation in Space-Bounded Settings",
volume  = "48",
year    = "2019"
}

@Article{NR95,
author  = "Niedermeier, Rolf and Rossmanith, Peter",
doi     = "10.1006/inco.1995.1064",
journal = "Information and Computation",
number  = "2",
pages   = "227--245",
title   = "Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits",
volume  = "118",
year    = "1995"
}

@Article{JLL76,
author  = "Jones, Neil D. and Lien, Y. Edmund and Laaser, William T.",
doi     = "10.1007/BF01683259",
journal = "Mathematical Systems Theory",
number  = "1",
pages   = "1--17",
title   = "New Problems Complete for Nondeterministic Log Space",
volume  = "10",
year    = "1976"
}

@Article{LP82,
author  = "Lewis, Harry R. and Papadimitriou, Christos H.",
doi     = "10.1016/0304-3975(82)90058-5",
journal = "Theoretical Computer Science",
number  = "2",
pages   = "161--187",
title   = "Symmetric Space-Bounded Computation",
volume  = "19",
year    = "1982"
}

@Article{S75,
author  = "Sudborough, Ivan Hal",
doi     = "10.1016/S0022-0000(75)80014-6",
journal = "Journal of Computer and System Sciences",
number  = "1",
pages   = "62--76",
title   = "On Tape-Bounded Complexity Classes and Multi-Head Finite Automata",
volume  = "10",
year    = "1975"
}

@Article{L75,
author  = "Ladner, Richard E.",
doi     = "10.1145/990518.990519",
journal = "ACM SIGACT News",
number  = "1",
pages   = "18--20",
title   = "The Circuit Value Problem is Log Space Complete for P",
volume  = "7",
year    = "1975"
}

@InCollection{K72,
author    = "Karp, Richard M.",
booktitle = "Complexity of Computer Computations",
pages     = "85--103",
publisher = "Plenum Press",
title     = "Reducibility Among Combinatorial Problems",
year      = "1972"
}

@Book{Si12,
author    = "Sipser, Michael",
edition   = "3",
publisher = "MIT Press",
title     = "Introduction to the Theory of Computation",
year      = "2012"
}

@InProceedings{C71b,
author    = "Cook, Stephen A.",
booktitle = "Proceedings of the Third Annual ACM Symposium on Theory of Computing",
doi       = "10.1145/800157.805047",
pages     = "151--158",
publisher = "ACM",
title     = "The Complexity of Theorem-Proving Procedures",
year      = "1971"
}

@Book{CLRS22,
author    = "Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford",
edition   = "4th",
isbn      = "978-0-262-04630-5",
publisher = "MIT Press",
title     = "Introduction to Algorithms",
year      = "2022"
}

@InProceedings{C69,
address   = "Marina del Rey, CA, USA",
author    = "Cook, Stephen A.",
booktitle = "Proceedings of the First Annual ACM Symposium on Theory of Computing",
doi       = "10.1145/800169.805437",
month     = "5",
pages     = "229--231",
publisher = "ACM",
title     = "Variations on Pushdown Machines (Detailed Abstract)",
year      = "1969"
}