BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Petra Wolf

Petra Wolf contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityFormal Languages and Automata TheoryArtificial IntelligenceComputation and LanguageComputational GeometryEmerging Technologiesquant-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2023arXiv

Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing

The Kemeny Rank Aggregation (KRA) problem is a well-studied problem in the field of Social Choice with a variety of applications in many different areas like databases and search engines. Intuitively, given a set of votes over a set of candidates, the problem asks to find an aggregated ranking of candidates that minimizes the overall dissatisfaction concerning the votes. Recently, a diverse version of KRA was considered which asks for a sufficiently diverse set of sufficiently good solutions. The framework of diversity of solutions is a young and thriving topic in the field of artificial intelligence. The main idea is to provide the user with not just one, but with a set of different solutions, enabling her to pick a sufficiently good solution that satisfies additional subjective criteria that are hard or impossible to model. In this work, we use a quantum annealer to solve the KRA problem and to compute a representative set of solutions. Quantum annealing is a meta search heuristic that does not only show promising runtime behavior on currently existing prototypes but also samples the solutions space in an inherently different way, making use of quantum effects. We describe how KRA instances can be solved by a quantum annealer and provide an implementation as well as experimental evaluations. As existing quantum annealers are still restricted in their number of qubits, we further implement two different data reduction rules that can split an instance into a set of smaller instances. In our evaluation, we compare classical heuristics that allow to sample multiple solutions such as simulated annealing and local search with quantum annealing performed on a physical quantum annealer. We compare runtime, quality of solution, and diversity of solutions, with and without applying preceding data reduction rules.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

All Paths Lead to Rome

All roads lead to Rome is the core idea of the puzzle game Roma. It is played on an $n \times n$ grid consisting of quadratic cells. Those cells are grouped into boxes of at most four neighboring cells and are either filled, or to be filled, with arrows pointing in cardinal directions. The goal of the game is to fill the empty cells with arrows such that each box contains at most one arrow of each direction and regardless where we start, if we follow the arrows in the cells, we will always end up in the special Roma-cell. In this work, we study the computational complexity of the puzzle game Roma and show that completing a Roma board according to the rules is an \NP-complete task, counting the number of valid completions is #Ptime-complete, and determining the number of preset arrows needed to make the instance \emph{uniquely} solvable is $Σ_2^P$-complete. We further show that the problem of completing a given Roma instance on an $n\times n$ board cannot be solved in time $\mathcal{O}\left(2^{{o}(n)}\right)$ under ETH and give a matching dynamic programming algorithm based on the idea of Catalan structures.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Learning from Positive and Negative Examples: New Proof for Binary Alphabets

One of the most fundamental problems in computational learning theory is the the problem of learning a finite automaton $A$ consistent with a finite set $P$ of positive examples and with a finite set $N$ of negative examples. By consistency, we mean that $A$ accepts all strings in $P$ and rejects all strings in $N$. It is well known that this problem is NP-complete. In the literature, it is stated that this NP-hardness holds even in the case of a binary alphabet. As a standard reference for this theorem, the work of Gold from 1978 is either cited or adapted. But as a crucial detail, the work of Gold actually considered Mealy machines and not deterministic finite state automata (DFAs) as they are considered nowadays. As Mealy automata are equipped with an output function, they can be more compact than DFAs which accept the same language. We show that the adaptions of Gold's construction for Mealy machines stated in the literature have some issues and give a new construction for DFAs with a binary alphabet ourselves.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs

We study the computational complexity of determining structural properties of edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge $e$ of the graph, a binary string $s_e$ determines in which time steps the edge is present, namely $e$ is present in time step $t$ if and only if $s_e$ contains a $1$ at position $t \mod |s_e|$. Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the new concept of EPGs such as what is the shortest traversal time between two vertices; is there a time step in which the graph (1) is minor-free; (2) contains a minor; (3) is subgraph-free; (4) contains a subgraph; with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several parameterized algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Synchronization under Dynamic Constraints

Imagine an assembly line where a box with a lid and liquid in it enters in some unknown orientation. The box should leave the line with the open lid facing upwards with the liquid still in it. To save costs there are no complex sensors or image recognition software available on the assembly line, so a reset sequence needs to be computed. But how can the dependencies of the deforming impact of a transformation of the box, such as 'do not tilt the box over when the lid is open' or 'open the lid again each time it gets closed' be modeled? We present three attempts to model constraints of these kinds on the order in which the states of an automaton are transitioned by a synchronizing word. The first two concepts relate the last visits of states and form constraints on which states still need to be reached, whereas the third concept concerns the first visits of states and forms constraints on which states might still be reached. We examine the computational complexity of different variants of the problem, whether an automaton can be synchronized with a word that respects the constraints defined in the respective concept, and obtain nearly a full classification. While most of the problems are PSPACE-complete we also observe NP-complete variants and variants solvable in polynomial time. We will also observe a drop of the complexity if we track the orders of states on several paths simultaneously instead of tracking the set of active states. Further, we give upper bounds on the length of a synchronizing word depending on the size of the input relation and show that the Cerny conjecture holds for partial weakly acyclic automata.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

From Decidability to Undecidability by Considering Regular Sets of Instances

We are lifting classical problems from single instances to regular sets of instances. The task of finding a positive instance of the combinatorial problem $P$ in a potentially infinite given regular set is equivalent to the so called intreg-problem of $P$, which asks for a given DFA $A$, whether the intersection of $P$ with $L(A)$ is non-empty. The intreg-problem generalizes the idea of considering multiple instances at once and connects classical combinatorial problems with the field of automata theory. While the question of the decidability of the intreg-problem has been answered positively for several NP- and even PSPACE-complete problems, we are presenting natural problems even from L with an undecidable intreg-problem. We also discuss alphabet sizes and different encoding-schemes elaborating the boundary between problem-variants with a decidable respectively undecidable intreg-problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata

The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton M as input, whether the language L(M) accepted by M contains any positive instance of the problem P. We consider the Int_reg-problem for a number of different graph problems and give general criteria that give decision procedures for these Int_reg-problems. To achieve this goal, we consider a natural graph encoding so that the language of all graph encodings is regular. Then, we draw the connection between classical pumping- and interchange-arguments from the field of formal language theory with the graph operations induced on the encoded graph. Our techniques apply among others to the Int_reg-problem of well-known graph problems like Vertex Cover and Independent Set, as well as to subgraph problems, graph-edit problems and graph-partitioning problems, including coloring problems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Synchronization of Deterministic Visibly Push-Down Automata

We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a synchronizing word w does not only map all states to the same state but also fulfills some conditions on the stack content of each run after reading w. We consider three types of these stack constraints: after reading w, the stack (1) is empty in each run, (2) contains the same sequence of stack symbols in each run, or (3) contains an arbitrary sequence which is independent of the other runs. We show that in contrast to general deterministic push-down automata, it is decidable for deterministic visibly push-down automata whether there exists a synchronizing word with each of these stack constraints, i.e., the problems are in EXPTIME. Under the constraint (1) the problem is even in P. For the sub-classes of deterministic very visibly push-down automata the problem is in P for all three types of constraints. We further study variants of the synchronization problem where the number of turns in the stack height behavior caused by a synchronizing word is restricted, as well as the problem of synchronizing a variant of a sequential transducer, which shows some visibly behavior, by a word that synchronizes the states and produces the same output on all runs.

0 citations0 reviewsNo code linkedOpen access