{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q809608","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q809608","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q809608","kernelVersion":"v1","immutable":true,"modified":"2026-01-07T14:35:27Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q809608","name":"Finite-automaton aperiodicity is PSPACE-complete","headline":"Finite-automaton aperiodicity is PSPACE-complete","description":"scientific article; zbMATH DE number 4213449","url":"https://portal.mardi4nfdi.de/entity/Q809608","datePublished":"1991-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q809607"},{"@id":"https://portal.mardi4nfdi.de/entity/Q391197"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q123643"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0304-3975(91)90075-D","url":"https://doi.org/10.1016/0304-3975(91)90075-D"},"sameAs":["https://doi.org/10.1016/0304-3975(91)90075-D"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1186807"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5772619"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3862379"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3821586"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2537313"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5339335"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4077455"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3740247"}]},"provenance":{"prov:generatedAtTime":"2026-01-07T14:35:27Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}