How to describe Deterministic Transitive Closure in FOL

In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE.

Hence, taking into account that FOL captures LOGSPACE, it should be possible to:

  • Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
  • It should be possible to define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)")

I would like to know how to define such predicate. This would be quite easy in Datalog, using recursion, but it should be possible to define it without recursion, which is the question that puzzles me.

Closure of disjoint sets

I am trying to solve the following problem but I cannot figure out two disjoint sets such that their closures are equal.
Find languages S and T over the alphabet {a, b} such that $ S \not\subset T $ and $ T \not\subset\ S $ (S is not contained in T and T is not contained in S) but S* = T*. It might be trivial, but I would appreciate some help. Thanks.

Proving a language is context free without closure rules or grammar?

I know how to prove a language is context free through closure rules and through providing a grammar. However, in my exercises I’ve come across a language not suitable for either:

$ L = \{uc^nv\ \ |\ \ (2|v|_a + 3|v|_b) = (4|u|_a + |u|_b), n ≥ 1\}$

I know that pushdown automatons recognize context free languages, so providing a PDA that accepts this language would be enough to prove that it is context free.

How can I construct a PDA for this language?

I think rewriting the language contraint as the following would help, but I’m not sure how:

$ 2|v|_a + 3|v|_b – 4|u|_a – |u|_b = 0$

I can imagine it being something along the lines of "every time you see an "a" in v, push 2 onto the stack, every time you see an "a" in u, pop 4 off the stack", and something similar for b. If the stack has 0 elements, we’re in an accepting state.

However, I do not have experience with PDAs and I am having trouble drawing a diagram or formalizing this.

Induction details for proof of closure of regular languages under unions

I was reading M. Sipser, Introduction to the theory of computation 3ed. where he presents a proof by construction that the class of regular languages is closed under unions (Theorem 1.25). However, he omits the induction details for a formal proof of correctness. I tried filling in the details myself but it was a mess; how is this usually done?

HP pavillion gaming laptop accelerometer, lid closure, and constant fan throttleing

So I’ve recently been forced to upgrade laptops after an unexpected deluge killed my last one. My wife, who plans for everything, managed to score an upgrade to an HP Pavilion 15 gaming laptop, and the bios reports it as

HP Pavilion Gaming Laptop 15-cx0xxx 

Though some googling makes me believe it’s a

HP Pavilion Gaming Laptop 15-dk0010nr 

The specs are identical, except the OS reports the GPU as a 1050TI not a 1050, though I’m not too familiar with the naming conventions of nvidia. The specs of the 1050TI vs the 1050 seem unimportant for the issues I’m having.

So I install linux mint and the it doesn’t like the lid switch, causing it to overheat in its protective sleeve, because it doesn’t go to sleep. I was also having issues wrangling the nvidia drivers, and the accelerometer was causing the laptop to take forever to shutdown. So I turn it off. Which causes my brightness keys (F2 and F3) to stop functioning correctly, and dmesg tells me them and the lidswitch aren’t mapped.

I decide to switch to Pop!_OS because they really try to integrate the nvidia drivers. Anyway on the clean install it works great, I can tell the accelerometer is working because the screen rotates. Everything sleeps when the lid closes and the brightness keys function, and the processor isn’t constantly overheating causing the fans to run mostly continuously. I restart the laptop and, with the exception of nvidia drivers, the previous problems reappear.

I hunt through dmesg and I find that the accelerometer has a good ol’ fashioned failure to chooch.

[   11.500311] hp_accel: laptop model unknown, using default axes configuration [   11.519990] lis3lv02d: unknown sensor type 0x0 [   11.519993] hp_accel: probe of HPQ6007:00 failed with error -22 [   11.536372] hp_wmi: query 0xd returned error 0x5 [   11.536403] input: HP WMI hotkeys as /devices/virtual/input/input9 

However, I have found that sometimes when I boot up the laptop the accelerometer initializes properly and everything works.

I have done some digging and have found out that it is a known bug in the kernel.

My question is, is their some sort of work around to get

  1. The lid switch working (closure of the lid triggers a sleep event, and opening the lid causes it to wake back up)
  2. Help keep the processor from constantly throttling
  3. Get the brightness keys working

What additional information do we need to find a possible work around?

Doubt in definition of closure under concatenation operation in Recursive Enumerative languages

I recently started studying theory of computation.

Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this.

Please Note – RE shortform i am taking for Recusively enumerative language

One way –> If L1, and L2 are RE s then L1.L2 is RE then RE is closed under concatenation.

Another way if we talk interms of strings, If for all ‘a’ belongs to L1 and for all ‘b’ belongs to L2 then w=a.b belongs to L1.L2.

What about the other side? Please see if this is correct?

For closure under concatenation, If w belongs to L1.L2 then all or some string splits of w into 2 make 1st part acceptance under L1 and 2nd string split acceptance under L2?

I was thinking, as L1 and L2 are REs we can make L1.L2 RE by concatenating L1 and L2 turing machines and make start state as start state of L1 and endstate as final state of L2. But when i am thinking in terms of string input i am getting confused

THe proof in my textbook says that we can non-deterministically split w into 2 parts so that each part accepted by Turing machines for L1 and L2 respectively. If string length is n, then we can have (n+1) kinds of 2 splits of w-string. Will the L1.L2 turing machine accepts all these n+1 types of w-splits? But this is what we need to prove right?