Questions tagged [automata-theory]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

Filter by
Sorted by
Tagged with
4
votes
1answer
623 views

Synchronizing sequences for rubik's cube?

Are there any results on the existence of synchronizing sequences for a standard 3x3 rubik's cube? Like a proof that there are none? My google-skills failed me...
9
votes
2answers
290 views

Are non-deterministic tree-walking automata stronger than deterministic ones?

Update: It seems this problem has been studied and solved recently, see this wiki article: http://en.wikipedia.org/wiki/Tree_walking_automaton And also this survey: http://www.mimuw.edu.pl/~bojan/...
8
votes
2answers
477 views

What's the simplest to implement of all decent LTL-to-Buchi translation or other LTL verification algorithms?

I'm writing a toy modelchecker, and I'm at the point where it's time to implement LTL to Buchi automata translation. For a variety of obvious reasons, I wish the algorithm to be simple :) e.g. I want ...
0
votes
0answers
207 views

formal definition of “flowcharts”

I am looking for a formal definition of so-called "flowcharts" used as representation of programs or business processes. Is there some good one around ? Thx JCLL
17
votes
5answers
1k views

Ambiguity and Logic

In automata theory (finite automata, pushdown automata, ...) and in complexity, there is a notion of "ambiguity". An automaton is ambiguous if there is a word $w$ with at least two distinct accepting ...
-4
votes
3answers
517 views

Time-based mathematics or logic [closed]

The conventional systems of logic can only recognize or perform operations that transform or translate values in space. Ordinary logic treats time poorly through the necessity of translating all ...
10
votes
1answer
680 views

Closure of unambiguous context-free languages under pre- and postfix.

Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: ...
18
votes
0answers
465 views

To what extent MSO = WS1S, when adding relations?

[This question has been asked on MathOverflow with no luck a month ago.] Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma =\{a_1, \ldots, a_n\}$, I define two ...
0
votes
3answers
210 views

A fsm with temporal events

I have defined a finite state machine Q = {Σ, S, s0, δ, F} where Σ = {'[r]equest', '[o]ut', '[i]n', '[e]nd'} S = {'[R]eady', '[I]nitiating', '[W]aiting', 'Re[C]eived', 'Re[S]...
15
votes
1answer
331 views

Compared growth of the number of syntactic classes and Nerode classes.

For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. : u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L]. Now define the Nerode equivalence as the ...
-2
votes
2answers
379 views

Can every non-deterministic finite automate be changed into one with only one acceptance state? [closed]

How can an arbitrary non-deterministic finite automate be converted into one with only one accept stage? If so, what is the proof that this can always be done?
30
votes
4answers
1k views

Are there “small” machines which can efficiently match regular expressions?

It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially ...
9
votes
4answers
2k views

Why are linear bounded automata not as popular as other automata?

In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, ...
8
votes
1answer
382 views

What can I say about the Parikh map of a CSL?

Write $\Psi$ as the Parikh map--i.e., $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$, where $\#_\sigma(w)$ is the number of times $\sigma$ appears in $w$. It's well-known that, for a ...
9
votes
3answers
397 views

Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

Problem statement : Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?...
1
vote
0answers
177 views

Edit-Distance of weighted automata

I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at http://www.cs.nyu.edu/~mohri/pub/ (they are virtually identical so which of them doesn't matter). ...
4
votes
1answer
871 views

The class CFL\cap co-CFL

Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment ...
17
votes
3answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
3
votes
1answer
377 views

Extension of a partial order to a total of partitions of a weak alternating automaton

My problem is this: given a weak alternating automaton and its partitions, and given a partial order on these partitions, how do we extend the partial order to a total order? The partitions of weak ...
27
votes
2answers
1k views

Conditions for NFA universality

Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$. Now lets analyze the ...
10
votes
2answers
497 views

Taxonomy of notable regular expression automata

I'm trying to draw up a taxonomy of algorithms for transforming regular expressions into automata so as to perform some empirical tests of their complexity properties in specific domains. I'm aware ...
0
votes
1answer
1k views

Question about Mapping Reductions (Clarify Example)

I cannot for the life of me wrap my head around these reductions. Specifically, the example I'm wrestling with: ...
8
votes
3answers
2k views

Proving the set of powers of 2 over ternary alphabet to be non regular.

It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it. But the powers of 2 represented in ternary appears to be non regular. Pumping ...
25
votes
2answers
1k views

Context Sensitive Grammars and Types

1) What, if any, is the relationship between static typing and formal grammars? 2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was ...
5
votes
2answers
270 views

Why may the right hand sides in Chomsky Hierachy type 1 be larger?

I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|. Why? I would have said, ...
8
votes
1answer
439 views

Tool for translating PDAs to CFGs

We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
10
votes
5answers
3k views

Automata Theory / Formal Language Thesis Topic

Hey All, I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an ...
11
votes
1answer
489 views

Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages.

Immerman (Descriptive Complexity, 1999) presents the EF games for existential monadic second order (Ajtai-Fagin games) on page 127. As $\exists$MSO on words is equivalent to regular languages, the ...