Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
6
votes
2answers
175 views

Finite Automata with succinct representation of chains of states

Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this: could be represented in this ...
6
votes
1answer
159 views

Inverse of transducer compositions

Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an FSM transducer). These machines are closed under compositions. A composition of two GSMs $f(x)$ and $g(x)$ can be written ...
6
votes
1answer
162 views

Complexity of DFA intersection in this specific case?

In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible ...
6
votes
2answers
249 views

Deciding functionality of transducers over infinite words

Given a finite state transducer defining a rational relation over infinite words, it is known to be decidable whether or not the relation is a function, i.e. whether each infinite input word is ...
6
votes
1answer
426 views

Pumping Lemma over 2 way Automaton

Pumping Lemma essentially implies that for a NFA $N$ having $N_0$ states over a unary language $L_0$ any string belonging to $L_0$ can be obtained by 'pumping' one of the strings that have a length ...
6
votes
2answers
131 views

Characterization of union of DCFLs

We know that DCFL is not closed under the union operation and CFL is closed under union and contains the union of DCFLs. Is there a characterization of finite unions of DCFLs?
6
votes
3answers
423 views

Simplification of weighted NFA

What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then ...
6
votes
3answers
403 views

Chomsky hierarchy for tree structures

I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$. Is there a similar hierarchy for ...
6
votes
2answers
246 views

FSM transducer sequential composition decidability

this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word $x$....
6
votes
1answer
223 views

Has there been a study of circuits operating on arrays?

Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any ...
6
votes
2answers
352 views

Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions.

Adding extensions to automata has always been a fruitful domain. But usually, one wants to add weak capabilities, as undecidability comes quickly into the picture. Take FSM with added stacks. It is ...
6
votes
0answers
864 views

What would a PDA be with a queue instead of a stack?

A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton ...
6
votes
0answers
476 views

Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability

A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we ...
6
votes
0answers
178 views

Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words

Consider a deterministic transition structure having states in set $X$ and transition function $\rightarrow$, and an initial state $x \in X$. This structure is intended to be part of an automaton ...
6
votes
0answers
148 views

Are k+1 heads better than k for multiread finite automata?

Consider the deterministic (resp. non-deterministic) one-way finite automaton that is defined in the usual way except that it has k heads and in each step can decide which head to move. (It is allowed ...
6
votes
0answers
273 views

Language of stack configurations of a pushdown automaton

Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free language?...
5
votes
3answers
641 views

Formal definition of parser?

I'm looking for an accepted, formal definition of a parser as function $f$ returning an AST, but I cannot find any reference in literature; all I can find is the definition of a recognizer as a ...
5
votes
2answers
2k views

Why were Finite Automata and Turing Machines created?

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
5
votes
2answers
306 views

Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

Let $\Sigma$ be a finite alphabet. A trivial finite automaton can accept the language $L_1 = \{w\;|\;w\in \Sigma^*\}$. A simple pushdown automaton can accept the language $L_2 = \{ww^R\;|;w\in \...
5
votes
2answers
141 views

Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
5
votes
1answer
191 views

What is the motivation behind defining Deterministic Looping Automata?

I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it! I believe they ...
5
votes
1answer
876 views

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why? Details: http://en.wikipedia.org/wiki/Powerset_construction states that the worst-...
5
votes
1answer
440 views

What is the importance of linear languages?

What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have ...
5
votes
1answer
221 views

Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

I was reading this paper, about the complexity of decision problems for reversal bounded counter machines. I got to Theorem 1 on Page 6. The theorem shows that there's a log-space NTM which can ...
5
votes
2answers
271 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, ...
5
votes
2answers
158 views

Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
5
votes
1answer
166 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
5
votes
1answer
850 views

Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
5
votes
1answer
272 views

Equivalence problem for one-counter automata

I know that the equivalence problem for deterministic one counter automata is decidable, however does anyone know whether it is decidable for all one counter automata or just the deterministic ones? ...
5
votes
1answer
120 views

Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids. To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of ...
5
votes
1answer
174 views

Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

I want to have an overview of all the meaningful equivalence relations defined on $X^{\ast}$, in particular when the languages in question are regular. They typically arise in connection with the ...
5
votes
1answer
138 views

When does automaton stay unchanged after string homomorphism?

Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$. Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to ...
5
votes
1answer
116 views

Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?

It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them. However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most ...
5
votes
0answers
142 views

Mastery-based grading for Theory of Computation

I would be interested to learn of anyone's experience using mastery-based (or "mastery-level") grading in a Theory of Computation course. Usually this requires—at a minimum— a detailed ...
5
votes
0answers
96 views

Why do multi-stack visibly pushdown languages label each call/return with a particular stack?

In A Unifying Approach for Multistack Pushdown Automata, multistack visibly pushdown automata are defined in terms of an alphabet where each symbol is either a call or return for a particular stack or ...
5
votes
0answers
115 views

Learning Finite Automata Behavior by Experimentation

This conjecture is from an expert in Game Theory area, I post it here to draw more attentions of TCS experts. Discussions and comments are welcome. http://gtcenter.org/WCS_Call_for_papers.pdf An ...
4
votes
3answers
441 views

How to minimize a FSM transducer?

In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the ...
4
votes
1answer
1k views

Is Hartmanis-Stearns conjecture settled by this article?

The paper "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited" by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec https://arxiv.org/abs/1601....
4
votes
2answers
890 views

Finite state transducer that sorts

Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers ...
4
votes
3answers
235 views

Regular languages under change of encoding

Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$. Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other ...
4
votes
1answer
625 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...
4
votes
2answers
318 views

Inductive definition of ECTL*: how are recursive formulas forbidden?

In [1], the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi ...
4
votes
1answer
883 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 ...
4
votes
1answer
109 views

When does a set of infixes determine a set of ($\omega$-) words

If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for ...
4
votes
1answer
114 views

Applications of Christol theorem

I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
4
votes
1answer
162 views

Are endmarkers necessary for Deterministic Pushdown Automata?

In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to ...
4
votes
1answer
734 views

Minimal context-free grammar for a regular language

Are there any algorithms for solving exactly the following question? Given a regular language L, represented as a finite automaton say, what is a CFG with minimal number of nonterminals that generates ...
4
votes
1answer
250 views

What characterizations exist for the grammars that can express subsets of the context-free languages?

It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$. ...
4
votes
1answer
1k views

Emptiness of PDA without constructing the corresponding CFG

The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs. Therefore, given a PDA, the straightforward ...
4
votes
1answer
507 views

Decidability of membership in the fixed point of a rational relation

Given a finite alphabet $\Sigma$, a non-deterministic finite-state transducer representing rational a relation $T \subseteq \wp(\Sigma^* \times \Sigma^*)$, a finite state machine representing a ...