6 citations · 15 across the 7 of their papers we have counts for
11 papers
Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)
Florian Starke
We show that the constraint satisfaction problem of any finite conservative structure that can not pp-construct st-Con (whose CSP is NL-complete) or 3Lin2 (whose CSP is Mod2L-compl…
Almost Symmetric Linear Arc Monadic Datalog and Transitive Tournaments
Sebastian Meyer, Florian Starke
We introduce -almost symmetric Datalog and study -almost symmetric linear arc monadic Datalog. We characterize the finite relational structures whose constraint satisfaction…
Finite Simple Groups in the Primitive Positive Constructability Poset
Sebastian Meyer, Florian Starke
We show that any clone over a finite domain that has a quasi Maltsev operation and fully symmetric operations of all arities has an incoming minion homomorphism from I, the clone o…
Symmetric Linear Arc Monadic Datalog and Gadget Reductions
Manuel Bodirsky, Florian Starke
A Datalog program solves a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three D…
Digraphs modulo primitive positive constructability
Florian Starke
This is my dissertation about digraphs ordered by pp-constructability. We study in particular smooth digraphs, i.e., digraphs without sources or sinks, tournaments and semicomplete…
The Smallest Hard Trees
Manuel Bodirsky, Jakub Bulín, Florian Starke +1
We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientat…
Maximal Digraphs With Respect to Primitive Positive Constructibility
Florian Starke, Manuel Bodirsky
We study the class of all finite directed graphs up to primitive positive constructability. The resulting order has a unique greatest element, namely the graph with one verte…
ASNP: a tame fragment of existential second-order logic
Manuel Bodirsky, Simon Knäuer, Florian Starke
Amalgamation SNP (ASNP) is a fragment of existential second-order logic that strictly contains binary connected MMSNP of Feder and Vardi and binary guarded monotone SNP of Bienvenu…
On associative operations on commutative integral domains
Erkko Lehtonen, Florian Starke
We describe the associative multilinear polynomial functions over commutative integral domains. This extends Marichal and Mathonet's result on infinite integral domains and provide…
Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
Manuel Bodirsky, Florian Starke, Albert Vucaj
Finite smooth digraphs, that is, finite directed graphs without sources and sinks, can be partially ordered via pp-constructability. We give a complete description of this poset an…
Exploring the Topological Entropy of Formal Languages
Florian Starke
We introduce the notions of topological entropy of a formal language and of a topological automaton. We show that the entropy function is surjective and bound the entropy of langua…