{'fraction_non_alphanumeric': 0.015625, 'fraction_numerical': 0.0, 'mean_word_length': 4.959302325581396, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
L-Recursion and a new Logic for Logarithmic Space

We extend first-order logic with counting by a new operator that allows it to
formalise a limited form of recursion which can be evaluated in logarithmic
space. The resulting logic LREC has a data complexity in LOGSPACE, and it
defines LOGSPACE-complete problems like deterministic reachability and Boolean
formula evaluation. We prove that LREC is strictly more expressive than
deterministic transitive closure logic with counting and incomparable in
expressive power with symmetric transitive closure logic STC and transitive
closure logic (with or without counting). LREC is strictly contained in
fixed-point logic with counting FPC. We also study an extension LREC= of LREC
that has nicer closure properties and is more expressive than both LREC and
STC, but is still contained in FPC and has a data complexity in LOGSPACE. Our
main results are that LREC captures LOGSPACE on the class of directed trees and
that LREC= captures LOGSPACE on the class of interval graphs.