The method of forced enumeration for nondeterministic automata
From MaRDI portal
Publication:1099620
DOI10.1007/BF00299636zbMath0638.68046OpenAlexW1590283810WikidataQ56386805 ScholiaQ56386805MaRDI QIDQ1099620
Publication date: 1988
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00299636
complementnondeterministic automatanondeterministic Turing machinesclosure of context-sensitive languagesforced enumeration
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (only showing first 100 items - show all)
On Boolean combinations forming piecewise testable languages ⋮ Alternating and empty alternating auxiliary stack automata. ⋮ On the complexity of the word problem for automaton semigroups and automaton groups ⋮ Census techniques collapse space classes ⋮ Deterministic versus nondeterministic space in terms of synchronized alternating machines ⋮ Bounded MSC communication ⋮ Collapsing degrees via strong computation ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ Weak and strong one-way space complexity classes ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ Hierarchical information and the synthesis of distributed strategies ⋮ The complexity of planarity testing ⋮ On the Complexity of k-Piecewise Testability and the Depth of Automata ⋮ Infinite vs. finite size-bounded randomized computations ⋮ A survey of two-dimensional automata theory ⋮ Linearly bounded infinite graphs ⋮ Complementing two-way finite automata ⋮ A note on logspace optimization ⋮ DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ The complexity of membership problems for circuits over sets of integers ⋮ Structure and importance of logspace-MOD class ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ Some modifications of auxiliary pushdown automata ⋮ A communication hierarchy of parallel computations ⋮ A computation model with automatic functions and relations as primitive operations ⋮ A note on balanced immunity ⋮ Positive and negative proofs for circuits and branching programs ⋮ Space hierarchy theorem revised. ⋮ The complexity of the characteristic and the minimal polynomial. ⋮ Model-checking hierarchical structures ⋮ Observations on complete sets between linear time and polynomial time ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Catalytic space: non-determinism and hierarchy ⋮ The complexity of regular DNLC graph languages ⋮ On the computational complexity of problems related to distinguishability sets ⋮ An alternating hierarchy for finite automata ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ Computing with cells: membrane systems – some complexity issues ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ A note on algebras of languages ⋮ Optimal Reachability in Divergent Weighted Timed Games ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ On deciding some equivalences for concurrent processes ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ On ``inherently context-sensitive languages -- an application of complexity cores ⋮ Interval graph representation with given interval and intersection lengths ⋮ The parallel complexity of finite-state automata problems ⋮ On the acceptance power of regular languages ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Multihead two-way probabilistic finite automata ⋮ The complexity of circuit value and network stability ⋮ Planarity Testing Revisited ⋮ Capturing complexity classes by fragments of second-order logic ⋮ A survey of space complexity ⋮ Further remarks on DNA overlap assembly ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ A lower bound for the nondeterministic space complexity of context-free recognition ⋮ The parallel complexity of coarsest set partition problems ⋮ Finite-model theory -- A personal perspective ⋮ A closed-form evaluation for Datalog queries with integer (gap)-order constraints ⋮ A very hard log-space counting class ⋮ The equational complexity of Lyndon's algebra ⋮ What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\) ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Unnamed Item ⋮ Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems ⋮ Homonym population protocols ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Planar and grid graph reachability problems ⋮ Complexity of deciding detectability in discrete event systems ⋮ Clocked population protocols ⋮ Orbit expandability of automaton semigroups and groups ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Unnamed Item ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space ⋮ Complexity Theory Basics: NP and NL ⋮ Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs ⋮ Sorting, linear time and the satisfiability problem ⋮ Logic, semigroups and automata on words ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Comparing the notions of opacity for discrete-event systems ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ On verification of D-detectability for discrete event systems ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs ⋮ A variant of inductive counting ⋮ Positive versions of polynomial time ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space ⋮ Varieties ⋮ A note on closure properties of logspace MOD classes ⋮ Note on the complexity of Las Vegas automata problems ⋮ Succinctness as a source of complexity in logical formalisms ⋮ For completeness, sublogarithmic space is no space. ⋮ The complexity of the exponential output size problem for top-down and bottom-up tree transducers ⋮ Context-free languages can be accepted with absolutely no space overhead ⋮ The alternation hierarchy for sublogarithmic space is infinite ⋮ A taxonomy of fairness and temporal logic problems for Petri nets ⋮ Iteration of rational transductions ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
Cites Work
This page was built for publication: The method of forced enumeration for nondeterministic automata
