- 2-Head 2D Returning Finite Automata
2026/06/25 by Henning Fernau, Benedek Nagy, R. Jennifer Rose +4 · 1 voice
Biochemistry, Genetics and Molecular Biology · Computer Science · #Abstract family of languages #Automata theory #Class (philosophy) #Closure (psychology) #DNA and Biological Computing #Deterministic pushdown automaton #Finite-state machine #Machine Learning and Algorithms #Nested word #Quantum finite automata #Regular language #cs.FL #semigroups and automata theory
- Shuffles of Context-Free Languages along Regular Trajectories
2026/03/27 by Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund · 1 voice
Computer Science · #Embedded Systems Design Techniques #Interconnection Networks and Systems #Lemma (botany) #Parallel Computing and Optimization Techniques #Regular language #Salient #Set (abstract data type) #Trichotomy (philosophy) #Word (group theory) #cs.FL
- Quotient Complexity of Closed Languages
2009/12/05 by Janusz Brzozowski, J. Brzozowski, Galina Jirásková +3 · 12 citations
Computer Science · Mathematics · #Abstract family of languages #Advanced Algebra and Logic #Algorithm #Arithmetic #Automaton #Closure (psychology) #Combinatorics #Complement (music) #Computer science #Concatenation (mathematics) #Discrete mathematics #Formal language #Linguistics #Mathematics #Natural Language Processing Techniques #Prefix #Programming language #Quotient #Regular language #Suffix #Theoretical computer science #Transitive closure #Word (group theory) #cs.FL #semigroups and automata theory
- State Complexity of Basic Operations on Finite Languages
2001/01/01 by Cezar Câmpeanu, C. Câmpeanu, K. Culik +3 · 83 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Alphabet #Automaton #Catenation #Combinatorics #Computer science #Cone (formal languages) #DNA and Biological Computing #Deterministic finite automaton #Discrete mathematics #Finite state #Finite-state machine #Focus (optics) #Linguistics #Mathematics #Physics #Regular language #State (computer science) #Theoretical computer science #Upper and lower bounds #semigroups and automata theory
- Succinct representation of regular languages by boolean automata II
1985/01/01 by Ernst L. Leiss, Ernst Leiss · 14 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Automata theory #Automaton #Boolean function #Büchi automaton #Combinatorics #Computer science #DNA and Biological Computing #Deterministic automaton #Deterministic finite automaton #Discrete mathematics #Finite-state machine #Formal Methods in Verification #Mathematics #Mobile automaton #Nondeterministic algorithm #Nondeterministic finite automaton #Quantum finite automata #Regular language #Succinctness #Theoretical computer science #Timed automaton #Two-way deterministic finite automaton #semigroups and automata theory #ω-automaton
- Succinct representation of regular languages by boolean automata
1981/01/01 by Ernst L. Leiss, Ernst Leiss · 119 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algebra over a field #Algorithm #Automata theory #Automaton #Boolean expression #Boolean function #Büchi automaton #Combinatorics #Computer science #DFA minimization #DNA and Biological Computing #Deterministic automaton #Deterministic finite automaton #Discrete mathematics #Finite-state machine #Formal Methods in Verification #Mathematics #Nested word #Nondeterministic algorithm #Nondeterministic finite automaton #Product term #Pure mathematics #Quantum finite automata #Regular language #Succinctness #Theoretical computer science #Two-element Boolean algebra #Two-way deterministic finite automaton #semigroups and automata theory #ω-automaton
- On Isomorphisms and Density of NP and Other Complete Sets
1977/06/01 by L. Berman, Juris Hartmanis · 460 citations
Computer Science · Mathematics · #semigroups and automata theory #Algorithms and Data Compression #Machine Learning and Algorithms #Combinatorics #Mathematics #Alphabet #Simple (philosophy) #Time complexity #Context (archaeology) #Discrete mathematics #Regular language #NP-complete #Computer science #Theoretical computer science #Automaton