Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linear-bounded-automata]

The tag has no usage guidance.

1
vote
1answer
44 views

Undecidability of emptiness of LBA

How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?
0
votes
0answers
27 views

Q: Calculating a MPI cluster throughtput from hardware latencies

Since i don't have a CS background in my career, Built up an openmpi compute platform which succesfully computes from a variable number of available nodes. call this whole, a mpi cluster having N^2 4-...
3
votes
2answers
230 views

Is it possible to convert LBA into DFA?

Today I learned about an abstract class of machines called linear bounded automata. It is intended to model real-world computers that have a limited amount of memory. I have always thought that real ...
0
votes
1answer
50 views

Show that $A_\mathrm{LBA}$ is PSPACE-Complete?

I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte. Say we proved it is in PSPACE. Now for PSPACE-HARD: I had an idea, which was very similar to some solution i found on the web- say we have a ...
1
vote
1answer
172 views

Prove that it is undecidable whether a given LBA accepts a regular set

I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ...
1
vote
2answers
351 views

Reduce undecidable language to decidable language?

What happens if I build the following mapping function from $A_{\mathrm{TM}}$ to $A_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A_{\mathrm{LBA}}$ is decidable): If $M$ accepts ...
1
vote
1answer
96 views

What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine?

During a lesson, our TA asked: What kind of languages can be recognized by a deterministic Turing Machine such that we can use only a tape portion that contains the input? My thoughts: my ...
2
votes
1answer
216 views

A confusion about the Reduction via Computation History

[Updates: Thanks for @Raphael 's notification, I delete the screenshot of the book and type the $LaTex$ materials] In Sisper's Intro to the theory of Computation, there is a reduction method via ...
3
votes
0answers
97 views

Algorithms to match regular expressions containing backreferences

I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like: ([a-c])x\1 which would match ...
0
votes
1answer
152 views

LBA for $L = \{a^nb^{2n} \mid n\geq1 \}$

I want to construct a linear bounded automata for the language $L = \{a^nb^{2n} \mid n\geq1 \}$ . I know how LBA works but I don't have an idea how it can count the numbers of a's and check if the b's ...
0
votes
0answers
59 views

Modified Linear Bounded Automata Language

We know that linear bounded automatons accept context-sensitive grammars. Now suppose that we modify the LBA such that any location of the tape except the input part can be changed.What language ...
10
votes
2answers
2k views

Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines. However, Linearly Bounded Turing Machines are also ...
3
votes
0answers
113 views

Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
2
votes
1answer
310 views

Why cannot we reduce the Emptiness problem of LBA to the Acceptance problem of LBA?

I am a little bit confused about the emptiness problem of the linear bounded automaton (LBA). I know that this problem is undecidable. However if we assume that is decidable, what could be wrong if we ...
5
votes
1answer
109 views

Is every language in PTime also context-sensitive?

Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, ...
3
votes
1answer
91 views

Restrictions to counter machines capturing LBA

As you know in computation theory, there is a simple programming language equivalent in power to Turing machines. It is described as follows: Values: natural numbers only, but of unlimited precision. ...
5
votes
0answers
110 views

Is $E_{LBA}$ a Turing-recognizable language? [closed]

I know that $E_{LBA} = \{\langle M \rangle ~ \mid ~ L(M) = \emptyset \}$ is an undecidable language, but is it recognizable (recursively enumerable)? It seems that it's complement is recognizable ...
17
votes
5answers
2k views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
0
votes
1answer
98 views

How does augmenting linear bounded automata tape alphabets increase memory?

A linear bounded automaton is a Turing machine that is restricted by memory. How would augmenting the tape alphabet of a linear bounded automaton increase its memory? While the memory that the ...
5
votes
1answer
681 views

Is a LBA with stack more powerful than a LBA without?

Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful. A LBA with stack should not be Turing complete, ...
3
votes
0answers
107 views

Is there a grammar type for deterministic LBA?

Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this ...
1
vote
1answer
63 views

How can an LBA check legality of TM transitions without extra memory?

In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$. The reduction is proposed in the following manner: we receive a TM $M$ and a ...
13
votes
3answers
4k views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
-2
votes
1answer
674 views

Why it is said that LBA is a non deterministic Turing Machine

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
2
votes
2answers
323 views

Complements of Linear Bounded Automata?

Would switching the accept and reject states of an LBA A create a new LBA we'll say A' in which the language of A' is the complement of the language of A? I believe the answer is yes just by working ...
3
votes
2answers
242 views

Recognizing loops in computation on LBA

In the case of LBAs (Linear Bounded Automaton), in writing a decider for the language $\qquad A = \{ \langle M,w\rangle \mid M\ \mathrm{LBA}, w \in \mathcal{L}(M) \}$ we reject the input after a ...