Tag: fl.formal-languages
Found 204 results for 'fl.formal-languages'.
1) fl.formal-languages - Conditioning Probability on a Language With Measure 0
2) reference-request - What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?
3) reference-request - Lower bounds on the size of CFGs for specific finite languages
4) co.combinatorics - A property of suffix-free regular languages of maximal state complexity for the reverse operation
5) reference-request - "Embedding" a language in itself
6) fl.formal-languages - Büchi automata with acceptance strategy
7) fl.formal-languages - Does a given regular language contain an infinite prefix-free subset?
8) co.combinatorics - What is the number of languages accepted by a DFA of size $n$?
9) fl.formal-languages - Is this generalization of context free grammars known and strict?
10) cc.complexity-theory - Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?
11) reference-request - largest language class for which inclusion is decidable
12) fl.formal-languages - Regular expressions without alternation
13) fl.formal-languages - star height of star-free languages
14) fl.formal-languages - Are there "small" machines which can efficiently match regular expressions?
15) automata-theory - Taxonomy of notable regular expression automata
16) cc.complexity-theory - Assessing complexity of a language using subset relations
17) cc.complexity-theory - Two way deterministic multihead counter automata or logspace TM with counter
18) cc.complexity-theory - How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?
19) fl.formal-languages - Natural examples of context-sensitive languages from practice
20) reference-request - Is there a book/survey-paper outlining language class hierarchies, closure properties, etc
21) fl.formal-languages - Languages whose Parikh image is recognizable
22) fl.formal-languages - Non-CFL closure properties
23) fl.formal-languages - Ambiguity in regular and context-free languages
24) fl.formal-languages - Asymptotic density of ambiguous context-free grammars (CFGs)
25) fl.formal-languages - What is the state complexity of the copy language?
26) reference-request - Reference for Dyck languages being $\mathsf{TC}_0$-complete
27) cc.complexity-theory - What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?
28) fl.formal-languages - Separating lists of words
29) fl.formal-languages - What is the enlightenment I'm supposed to attain after studying finite automata?
30) cc.complexity-theory - Context-sensitive grammar for SAT?
31) fl.formal-languages - What formalisms exist to describe the translation of an abstract syntax tree into another formal language?
32) cc.complexity-theory - Is the Chomsky-hierarchy outdated?
33) fl.formal-languages - 1-way Quantum Finite Automata Example Question
34) fl.formal-languages - What class of languages is recognized by finite-state automata with $k$ heads?
35) fl.formal-languages - Status of Cerny Conjecture?
36) fl.formal-languages - The number of states of local automata
37) fl.formal-languages - Maximum shortest word accepted by pushdown automata
38) fl.formal-languages - Proof of the pumping lemma for context-free languages using pushdown automata
39) fl.formal-languages - Shortest string in the intersection of a context-free language and a regular language
40) fl.formal-languages - Complexity lower bound for regular languages
41) fl.formal-languages - The significance of state complexity in automata and regular languages?
42) fl.formal-languages - What is the motivation behind defining Deterministic Looping Automata?
43) fl.formal-languages - The class CFL\cap co-CFL
44) fl.formal-languages - What kind of language is needed to recognize an ordered list? [multihead automata, apparently]
45) lo.logic - Measurable language which is not $\omega$-regular
46) fl.formal-languages - What notable automaton models have polynomially-decidable containment?
47) fl.formal-languages - Size bound on Büchi automaton for complement
48) fl.formal-languages - Deterministic Parity Automata require unbounded index
49) fl.formal-languages - Giving a finite collection of infinite words "complex" enough with respect to automata measure
50) fl.formal-languages - Extension of a partial order to a total of partitions of a weak alternating automaton