Complexity of some problems from the theory of automata

Recommendations

scientific article; zbMATH DE number 4041268
scientific article; zbMATH DE number 4026835
scientific article; zbMATH DE number 1507202
scientific article; zbMATH DE number 459361
Exact complexity of problems of incompletely specified automata
scientific article; zbMATH DE number 4117877
DNA Computing
On the computational complexity of P automata
scientific article; zbMATH DE number 3868622
Complexity and universality of iterated finite automata

Cited in

(50)

Characterizations of some classes of regular events
Characterization of idempotent transformation monoids
Efficient simplicity testing of automata
Some results on the generalized star-height problem
Languages recognized by finite aperiodic groupoids
From cascade decompositions to bit-vector algorithms.
\texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
LANGAGE: A Maple package for automaton characterization of regular languages
Computational complexity of decision problems on self-verifying finite automata
Problems on finite automata and the exponential time hypothesis
Separability by piecewise testable languages is \textsc{PTime}-complete
On shuffle products, acyclic automata and piecewise-testable languages
Expressive power of existential first-order sentences of Büchi's sequential calculus
Exact complexity of problems of incompletely specified automata
Logic, semigroups and automata on words
Some complexity results for polynomial rational expressions.
Automata and complexity. Essays presented to Eric Goles on the occasion of his 70th birthday
On Boolean combinations forming piecewise testable languages
On the expressive power of temporal logic
The complexity of interacting automata
Deciding FO-definability of regular languages
Problems on finite automata and the exponential time hypothesis
On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs
Efficient algorithms for membership in Boolean hierarchies of regular languages
The Complexity of Mean-Payoff Automaton Expression
Complexity Analysis: Transformation Monoids of Finite Automata
Running Time Complexity of Printing an Acyclic Automaton
Descriptional and Computational Complexity of Finite Automata
scientific article; zbMATH DE number 4026835 (Why is no real title available?)
scientific article; zbMATH DE number 4041268 (Why is no real title available?)
Recent results on syntactic groups of prefix codes.
On the word problem for syntactic monoids of piecewise testable languages.
scientific article; zbMATH DE number 2068876 (Why is no real title available?)
PSPACE-completeness of certain algorithmic problems on the subgroups of free groups
Testing membership: Beyond permutation groups
New results on the generalized star-height problem
scientific article; zbMATH DE number 5041651 (Why is no real title available?)
Descriptional and computational complexity of finite automata -- a survey
200 Problems on Languages, Automata, and Computation
On computational complexity of set automata
The descriptive complexity approach to LOGCFL
On the Simon's congruence neighborhood of languages
Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
Forbidden Patterns for FO² Alternation Over Finite and Infinite Words
Decision problems for subregular classes
A first taste of MeSCaL, a tool for solving membership problems for regular languages
Language membership problems for subregular classes
Finite-automaton aperiodicity is PSPACE-complete
Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words
On the computational complexity of P automata

This page was built for publication: Complexity of some problems from the theory of automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740247)