scientific article; zbMATH DE number 3560737
From MaRDI portal
Publication:4131648
Cited in
(only showing first 100 items - show all)- Isomorphism of regular trees and words
- Hardness of approximation for knapsack problems
- From decidability to undecidability by considering regular sets of instances
- A complexity analysis of bisimilarity for value-passing processes
- Well-abstracted transition systems: Application to FIFO automata.
- Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997
- Complexity results for prefix grammars
- Problems on finite automata and the exponential time hypothesis
- Expressive capacity of subregular expressions
- Expansive automata networks
- Verifying polymer reaction networks using bisimulation
- Multi-linear iterative \(K\)-\(\Sigma\)-semialgebras.
- Distributed graph problems through an automata-theoretic lens
- Problems on finite automata and the exponential time hypothesis
- Comparing the notions of opacity for discrete-event systems
- Computing observers from observation policies in discrete-event systems
- On Boolean combinations forming piecewise testable languages
- Spanning the spectrum from safety to liveness
- scientific article; zbMATH DE number 7228403 (Why is no real title available?)
- The robustness of LWPP and WPP, with an application to graph reconstruction
- The recognition complexity of decidable theories
- Functions definable by arithmetic circuits
- Checking equivalences between concurrent systems of finite agents (extended abstract)
- Ranking function synthesis for bit-vector relations
- Lower bound techniques for QBF expansion
- scientific article; zbMATH DE number 7350780 (Why is no real title available?)
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Logics for unordered trees with data constraints
- A formal methods approach to predicting new features of the eukaryotic vesicle traffic system
- On quantified propositional logics and the exponential time hierarchy
- On the complexity of formulas in semantic programming
- scientific article; zbMATH DE number 7450037 (Why is no real title available?)
- Minimal NFA and biRFSA Languages
- Fast algorithms for revision of some special propositional knowledge bases
- Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
- Descriptional complexity of regular languages
- Max-plus automata
- Distributed graph problems through an automata-theoretic Lens
- The complexity of PDL with interleaving
- Reset complexity of ideal languages over a binary alphabet
- Reasoning About Substructures and Games
- Learning residual alternating automata
- Preprocessing for DQBF
- Size, cost and capacity: a semantic technique for hard random QBFs
- Characterization and complexity results on jumping finite automata
- Quantifier alternation for infinite words
- An axiomatic semantics for \(\mathsf{ioco} \underline{\mathsf{s}}\) conformance relation
- Reinterpreting dependency schemes: soundness meets incompleteness in DQBF
- Bounding queries in the analytic polynomial-time hierarchy
- Stable-unstable semantics: Beyond NP with normal logic programs
- Space-bounded reducibility among combinatorial problems
- On the complexity of typechecking top-down XML transformations
- Tree-size bounded alternation
- On verification of D-detectability for discrete event systems
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Observations on complete sets between linear time and polynomial time
- The quantifier complexity of polynomial-size iterated definitions in first-order logic
- Integer circuit evaluation is PSPACE-complete
- Ordered vertex removal and subgraph problems
- Deciding equivalence of finite tree automata
- Frontiers of tractability for typechecking simple XML transformations
- Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
- Observations on the complexity of regular expression problems
- Optimizing the region algebra is PSPACE-complete
- The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- Playing disjunctive sums is polynomial space complete
- Abduction from logic programs: Semantics and complexity
- Gobang is PSPACE-complete
- Complexity of some problems concerningL systems
- Descriptional and Computational Complexity of Finite Automata
- Polynomial and abstract subrecursive classes
- Playing Savitch and cooking games
- On the complexity of chess
- Fair simulation
- The complexity of node blocking for dags
- Decision algorithms for multiplayer noncooperative games of incomplete information
- Backtracking games and inflationary fixed points
- The parallel complexity of finite-state automata problems
- Equivalence problems for circuits over sets of natural numbers
- Visibly linear temporal logic
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- A covering system with least modulus 25
- Satisfiability of algebraic circuits over sets of natural numbers
- Transformations into normal forms for quantified circuits
- On termination and invariance for faulty channel machines
- On the shortest path game
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Some connections between bounded query classes and non-uniform complexity.
- Practical verification of multi-agent systems against \textsc{Slk} specifications
- The Analytic Polynomial-Time Hierarchy
- The complexity of online manipulation of sequential elections
- Distributed XML design
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- PSPACE-Hardness of some combinatorial games
- On time-space classes and their relation to the theory of real addition
- Automata for unordered trees
- Complexity of validity for propositional dependence logics
- Finite complete rewriting systems and the complexity of word problem
- Limitations of acyclic causal graphs for planning
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4131648)
