Complexity of some problems from the theory of automata

DOI10.1016/S0019-9958(85)80058-9zbMath0603.68059MaRDI QIDQ3740247

Jacques Stern

Publication date: 1985

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

dot depth one event recognitionfinite automaton aperiodicitypiecewise testable event recognitionstar-free events

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (33)

On Boolean combinations forming piecewise testable languages ⋮ Some complexity results for polynomial rational expressions. ⋮ On the expressive power of temporal logic ⋮ Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ Complexity Analysis: Transformation Monoids of Finite Automata ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Characterization of idempotent transformation monoids ⋮ Testing membership: Beyond permutation groups ⋮ New results on the generalized star-height problem ⋮ 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 ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Deciding FO-definability of regular languages ⋮ Recent results on syntactic groups of prefix codes. ⋮ On the word problem for syntactic monoids of piecewise testable languages. ⋮ From cascade decompositions to bit-vector algorithms. ⋮ On shuffle products, acyclic automata and piecewise-testable languages ⋮ PSPACE-completeness of certain algorithmic problems on the subgroups of free groups ⋮ Efficient simplicity testing of automata ⋮ Some results on the generalized star-height problem ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Expressive power of existential first-order sentences of Büchi's sequential calculus ⋮ The descriptive complexity approach to LOGCFL ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Logic, semigroups and automata on words ⋮ Languages recognized by finite aperiodic groupoids ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata ⋮ LANGAGE: A Maple package for automaton characterization of regular languages ⋮ Finite-automaton aperiodicity is PSPACE-complete

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