Finite-automaton aperiodicity is PSPACE-complete (Q809608)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Finite-automaton aperiodicity is PSPACE-complete |
scientific article; zbMATH DE number 4213449
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Finite-automaton aperiodicity is PSPACE-complete |
scientific article; zbMATH DE number 4213449 |
Statements
Finite-automaton aperiodicity is PSPACE-complete (English)
0 references
1991
0 references
The following three algorithmical problems are investigated. Given a minimum-state deterministic finite automaton M, is the language L(M) 1) a star-free language (a language expressible through regular expressions without *-operation)? 2) a dot-depth language? 3) a piecewise testable language? It is shown that Problem 1 is PSPACE-complete, and Problems 2 and 3 are logspace complete for NLOG. This solves the open problem from \textit{J. Stern} [Inf. Control 66, 163-176 (1985; Zbl 0603.68059)], where a polynomial space algorithm for Problem 1 and polynomial time algorithms for Problems 2 and 3 are presented.
0 references
finite automata
0 references
decision problems
0 references
0.870557427406311
0 references
0.8137040138244629
0 references
0.8071275949478149
0 references
