Similar Journals
|
Acta Informatica
Journal Prestige (SJR): 0.517  Citation Impact (citeScore): 1 Number of Followers: 5  Hybrid journal (It can contain Open Access articles)ISSN (Print) 1432-0525 - ISSN (Online) 0001-5903 Published by Springer-Verlag  [2468 journals]
|
- A closer look at Hamiltonicity and domination through the lens of diameter
and convexity-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A bipartite graph G(X, Y) is called a star-convex bipartite graph with convexity on X if there is an associated star T(X, F), such that for each vertex in Y, its neighborhood in X induces a subtree in T. A graph G is said to be a split graph if G can be partitioned into a clique (K) and an independent set (I). The objective of this study is twofold: (i) to strengthen the complexity results presented in Chen et al. (J Comb Optim 32(1):95–110, 2016) for the Hamiltonian cycle (HCYCLE), the Hamiltonian path (HPATH), and the Domination (DS) problems on star-convex bipartite graphs (ii) to reinforce the results of Müller (Discret Math 156(1–3):291–298, 1996) for HCYCLE, and HPATH on split graphs by introducing a convex ordering on one of the partitions (K or I). As part of our fine-grained analysis study with the diameter being the parameter, we first show that the diameter of star-convex bipartite graphs is at most six. Next, we observe that the reduction instances of Chen et al. (J Comb Optim 32(1):95–110, 2016) are star-convex bipartite graphs with at most diameter 4, and hence HCYCLE and HPATH are NP-complete on star-convex bipartite graphs with at most diameter 4. We strengthen this result and establish the following results on star-convex bipartite graphs: (i) HCYCLE is NP-complete for diameter 3, and polynomial-time solvable for diameters 2, 5, and 6 (a transformation in complexity: P to NPC to P) (ii) HPATH is polynomial-time solvable for diameter 2, and NP-Complete, otherwise (a dichotomy). Further, with convexity being the parameter, for split graphs with convexity on K (resp. I), we show that HCYCLE and HPATH are NP-complete on star-convex (resp. comb) split graphs with convexity on K (resp. I). Further, we show that HCYCLE is NP-complete on \(k_{1,r}\) -free star-convex split graphs with convexity on I, \(r\ge 6\) . On the positive side, we show that for \(K_{1,5}\) -free star-convex split graphs with convexity on I, HCYCLE is polynomial-time solvable. Thus, we establish a dichotomy for HCYCLE on star-convex split graphs with convexity on I. We further show that the dominating set problem (DS) and its variants (resp. Connected, Total, Outer-Connected, and Dominating biclique) are NP-complete on star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6). On the parameterized complexity front, we prove that the parameterized version of the domination problem and its variants, with the parameter being the solution size, is not fixed-parameter tractable for star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6), whereas it is fixed-parameter tractable when the parameter is the number of leaves in the associated star. Further, we show that for star-convex bipartite graphs with diameters 5, and 6, the domination problem and its variants cannot be approximated within \((1-\epsilon )\) ln n unless NP \(\subseteq TIME(2^{n^ {o(1)}})\) .
PubDate: 2024-08-03
-
- Cycle encoding-based parameter synthesis for timed automata safety
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Parametric timed automata (PTA) extend timed automata (TA) with parameters instead of fixed timing constraints, providing the flexibility to accommodate uncertainties during the design phase. Once a parametric model is obtained, the next step is finding the optimal parameters such that the resulting TA satisfies the specifications. This paper introduces a new algorithm for determining parameters from safety specifications for PTA with bounded integer parameters and no nested cycles. The algorithm searches for unsafe paths through a depth-first search and generates parameter constraints. In particular, the realizability of simple and cyclic paths are encoded via mixed integer linear programming and non-linear programming problems. Then, the parameter constraints rendering the path unrealizable are derived via quantifier elimination. The accumulated constraints through the depth-first search guarantee that a parameter valuation satisfying these constraints solves the synthesis problem. The results are illustrated over benchmarks.
PubDate: 2024-07-30
-
- The longest letter-duplicated subsequence and related problems
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Motivated by computing duplication patterns in sequences, a new problem called the longest letter-duplicated subsequence (LLDS) is proposed. Given a sequence S of length n, a letter-duplicated subsequence is a subsequence of S in the form of \(x_1^{d_1}x_2^{d_2}\ldots x_k^{d_k}\) with \(x_i\in \Sigma \) , \(x_j\ne x_{j+1}\) and \(d_i\ge 2\) for all i in [k] and j in \([k-1]\) . A linear time algorithm for computing a longest letter-duplicated subsequence (LLDS) of S can be easily obtained. In this paper, we focus on two variants of this problem: (1) ‘all-appearance’ version, i.e., all letters in \(\Sigma \) must appear in the solution, and (2) the weighted version. For the former, we obtain dichotomous results: We prove that, when each letter appears in S at least 4 times, the problem and a relaxed version on feasibility testing (FT) are both NP-hard. The reduction is from \((3^+,1,2^-)\) -SAT, where all 3-clauses (i.e., containing 3 lals) are monotone (i.e., containing only positive literals) and all 2-clauses contain only negative literals. We then show that when each letter appears in S at most 3 times, then the problem admits an O(n) time algorithm. Finally, we consider the weighted version, where the weight of a block \(x_i^{d_i} (d_i\ge 2)\) could be any positive function which might not grow with \(d_i\) . We give a non-trivial \(O(n^2)\) time dynamic programming algorithm for this version, i.e., computing an LD-subsequence of S whose weight is maximized.
PubDate: 2024-07-20
-
- Invariant relations for affine loops
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Invariant relations are used to analyze while loops; while their primary application is to derive the function of a loop, they can also be used to derive loop invariants, weakest preconditions, strongest postconditions, sufficient conditions of correctness, necessary conditions of correctness, and termination conditions of loops. In this paper we present two generic invariant relations that capture the semantics of loops whose loop body applies affine transformations on numeric variables.
PubDate: 2024-05-13
DOI: 10.1007/s00236-024-00457-9
-
- Reachability analysis of linear systems
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we propose a decision procedure of reachability for a linear system \(\xi '=A\xi +u\) , where the matrix \(A's\) eigenvalues can be arbitrary algebraic number and the input u is a vector of trigonometric-exponential polynomials. If the initial set contains only one point, the reachability problem under consideration is reduced to the decidability of the sign of trigonometric-exponential polynomial and then achieved by being reduced to verification of a series of univariate polynomial inequalities through Taylor expansions of the related exponential functions and trigonometric functions. If the initial set is open semi-algebraic, we will propose a decision procedure based on OpenCAD and an algorithm of real root isolation derived from the sign-deciding procedure for the trigonometric-exponential polynomials. The experimental results indicate the efficiency of our approach. Under the assumption of Schanuel’s Conjecture, the above procedures are complete for bounded time except for several cases.
PubDate: 2024-04-09
DOI: 10.1007/s00236-024-00458-8
-
- Revisiting 2–3 red–black trees with a pedagogically sound yet
efficient deletion algorithm: parity-seeking-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Red–black (RB) trees are one of the most efficient variants of balanced binary search trees. However, they have often been criticized for being too complicated, hard to explain, and unsuitable for pedagogical purposes, particularly their delete operation. Sedgewick (in: Dagstuhl Workshop on Data Structures, 2008. https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf) identified the length of code as the root of the problems and introduced left-leaning red–black (LLRB) trees. The delete operation of LLRB trees has a compact recursive code. Unfortunately, it may perform many unnecessary operations. The crux of the deletion algorithm is dealing with a “deficient” subtree, that is one whose black-height has become one less than that of its sibling subtree. In this paper, we revisit 2–3 red–black trees and propose a parity-seeking delete algorithm with the basic idea of making a deficient subtree on a par with its sibling: either by fixing the deficient subtree or by turning the sibling deficient as well, ascending deficiency to the parent node. Interestingly, the proposed parity-seeking delete algorithm also works for 2–3–4 RB trees. Our experiments show that the proposed parity-seeking delete algorithm is as efficient as the best preceding RB trees. The proposed parity-seeking delete algorithm is easily understandable and suitable for pedagogical and practical purposes.
PubDate: 2024-03-29
DOI: 10.1007/s00236-023-00452-6
-
- Distance-edge-monitoring sets of networks
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract It is important to be able to monitor the network and detect this failure when a connection (an edge) fails. For a vertex set M and an edge e of the graph G, let P(M, e) be the set of pairs (x, y) with a vertex x of M and a vertex y of V(G) such that e belongs to all shortest paths between x and y. A vertex set M of the graph G is distance-edge-monitoring set if every edge e of G is monitored by some vertex of M, that is, the set P(M, e) is nonempty. The distance-edge-monitoring number of a graph G, recently introduced by Foucaud, Kao, Klasing, Miller, and Ryan, is defined as the smallest size of distance-edge-monitoring sets of G. In this paper, we determine the bounds of the distance-edge-monitoring number of grid-based pyramids and the exact value of distance-edge-monitoring number for M(t)-graph and Sierpiński-type graphs. We also compare the distance-edge-monitoring set with average degree, the size of edge set and the size of vertex set of G, where G is M(t)-graph or Sierpiński-type graphs.
PubDate: 2024-03-19
DOI: 10.1007/s00236-024-00453-z
-
- An encoding of the $$\lambda $$ -calculus in the String MultiSet Rewriting
calculus-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we present an encoding of the \(\lambda \) -calculus in a multiset rewriting system and provide a few applications of the construction. For this purpose, we choose the calculus named String MultiSet Rewriting, which was introduced in Barbuti et al. (Electron Notes Theor Comput Sci 194:19–34, 2008) by Barbuti et al. With the help of our encoding, we give alternative proofs for the standardization and the finiteness of developments theorems in the \(\lambda \) -calculus.
PubDate: 2024-03-13
DOI: 10.1007/s00236-024-00456-w
-
- Exact distributed quantum algorithm for generalized Simon’s problem
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Simon’s problem is one of the most important problems demonstrating the power of quantum algorithms, as it greatly inspired the proposal of Shor’s algorithm. The generalized Simon’s problem is a natural extension of Simon’s problem and also a special hidden subgroup problem: Given a function \(f:\{0,1\}^n \rightarrow \{0,1\}^m\) , it is promised that there exists a hidden subgroup \(S\le \mathbb {Z}_2^n\) of rank k such that for any \(x, y\in {\{0, 1\}}^n\) , \(f(x) = f(y)\) iff \(x \oplus y \in S\) . The goal of generalized Simon’s problem is to find the hidden subgroup S. In this paper, we present two key contributions. Firstly, we characterize the structure of the generalized Simon’s problem in distributed scenario and introduce a corresponding distributed quantum algorithm. Secondly, we refine the algorithm to ensure exactness due to the application of quantum amplitude amplification technique. Our algorithm offers exponential speedup compared to the distributed classical algorithm. When contrasted with the quantum algorithm for the generalized Simon’s problem, our algorithm’s oracle requires fewer qubits, thus making it easier to be physically implemented. Particularly, the exact distributed quantum algorithm we develop for the generalized Simon’s problem outperforms the best previously proposed distributed quantum algorithm for Simon’s problem in terms of generalizability and exactness.
PubDate: 2024-03-10
DOI: 10.1007/s00236-024-00455-x
-
- New families of Laplacian borderenergetic graphs
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Laplacian matrix and its spectrum are commonly used for giving a measure in networks in order to analyse its topological properties. In this paper, Laplacian matrix of graphs and their spectrum are studied. Laplacian energy of a graph G of order n is defined as \( \mathrm{{LE}}(G) = \sum _{i=1}^n \lambda _i(L)-{\bar{d}} \) , where \(\lambda _i(L)\) is the i-th eigenvalue of Laplacian matrix of G, and \({\bar{d}}\) is their average. If \(\mathrm{{LE}}(G) = \mathrm{{LE}}(K_n)\) for the complete graph \(K_n\) of order n, then G is known as L-borderenergetic graph. In the first part of this paper, we construct three infinite families of non-complete disconnected L-borderenergetic graphs: \(\Lambda _1 = \{ G_{b,j,k} = [(((j-2)k-2j+2)b+1)K_{(j-1)k-(j-2)}] \cup b(K_j \times K_k) b,j,k \in {{\mathbb {Z}}}^+\}\) , \( \Lambda _2 = \{G_{2,b} = [K_6 \nabla b(K_2 \times K_3)] \cup (4b-2)K_9 b\in {{\mathbb {Z}}}^+ \}\) , \( \Lambda _3 = \{G_{3,b} = [bK_8 \nabla b(K_2 \times K_4)] \cup (14b-4)K_{8b+6} b\in {{\mathbb {Z}}}^+ \}\) , where \(\nabla \) is join operator and \(\times \) is direct product operator on graphs. Then, in the second part of this work, we construct new infinite families of non-complete connected L-borderenergetic graphs \(\Omega _1= \{K_2 \nabla \overline{aK_2^r} \vert a\in {{\mathbb {Z}}}^+\}\) , \(\Omega _2 = \{\overline{aK_3 \cup 2(K_2\times K_3)}\vert a\in {{\mathbb {Z}}}^+ \}\) and \(\Omega _3 = \{\overline{aK_5 \cup (K_3\times K_3)}\vert a\in {{\mathbb {Z}}}^+ \}\) , where \({\overline{G}}\) is the complement operator on G.
PubDate: 2024-02-26
DOI: 10.1007/s00236-024-00454-y
-
- Approximating subset sum ratio via partition computations
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to 1 as possible. Our scheme makes use of exact and approximate algorithms for Partition, and clearly showcases the close relationship between the two algorithmic problems. Depending on the relationship between the size of the input set n and the error margin \(\varepsilon \) , we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity \(\mathcal {O} (n^4 / \varepsilon )\) . In particular, the exponent of n in our proposed scheme may decrease down to 2, depending on the Partition algorithm used.
PubDate: 2024-01-12
DOI: 10.1007/s00236-023-00451-7
-
- Neighborhood mutual remainder: self-stabilizing distributed implementation
and applications-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Motivated by the need to convert move-atomic assumption in LOOK-COMPUTE-MOVE (LCM) robot algorithms to be implemented in existing distributed systems, we define a new distributed fundamental task, the neighborhood mutual remainder (NMR). Consider a situation where each process has a set of operations \(O_p\) and executes each operation in \(O_p\) infinitely often in distributed systems. Then, let \(O_e\subset O_p\) be a subset of operations, which a process cannot execute, while its closed neighborhood executes operations in \(O_p\setminus O_e\) . The NMR is defined for such a situation. A distributed algorithm that satisfies the NMR requirement should satisfy the following two properties: (1) Liveness is satisfied if a process executes each operation in \(O_p\) infinitely often and (2) safety is satisfied if, when each process executes operations in \(O_e\) , no process in its closed neighborhood executes operations in \(O_p\setminus O_e\) . We formalize the concept of NMR and give a simple self-stabilizing algorithm using the pigeon-hole principle to demonstrate the design paradigm to achieve NMR. A self-stabilizing algorithm tolerates transient faults (e.g., message loss, memory corruption, etc.) by its ability to converge from an arbitrary configuration to the legitimate one. In addition, we present an application of NMR to an LCM robot system for implementing a move-atomic property, where robots possess an independent clock that is advanced at the same speed. It is the first self-stabilizing implementation of the LCM synchronization for environments where each robot can have limited visibility and lights.
PubDate: 2023-12-18
DOI: 10.1007/s00236-023-00450-8
-
- Balancing m-ary search trees with compressions on the fringe
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We investigate the performance of random m-ary trees grown under an algorithm that perfectly balances k levels, whenever the opportunity arises in a fringe subtree. The average-case analysis shows that considerable saving in space and search time is achieved by such a fringe balancing algorithm.
PubDate: 2023-12-15
DOI: 10.1007/s00236-023-00448-2
-
- n-PS-codes, 2-infix-outfix codes and some related classes of codes
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, n-PS-codes, 2-infix-outfix codes and some related classes of codes are investigated where \(n\ge 1\) . The classes of n-PS-codes and 2-infix-outfix codes are generalizations of classes of prefix codes and suffix codes, and infix codes and outfix codes, respectively. The closure properties of n-PS-codes and g-3-PS-codes under composition are discussed where \(n\ge 1\) , and the condition under which the class of 2-infix-outfix codes is closed under composition is provided.
PubDate: 2023-12-15
DOI: 10.1007/s00236-023-00449-1
-
- Editorial 2023: changes and invariants
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
PubDate: 2023-11-03
DOI: 10.1007/s00236-023-00447-3
-
- A decision procedure for string constraints with string/integer conversion
and flat regular constraints-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract String constraint solving is the core of various testing and verification approaches for scripting languages. Among algorithms for solving string constraints, flattening is a well-known approach that is particularly useful in handling satisfiable instances. As string/integer conversion is an important function appearing in almost all scripting languages, Abdulla et al. extended the flattening approach to this function recently. However, their approach supports only a special flattening pattern and leaves the support of the general flat regular constraints as an open problem. In this paper, we fill the gap by proposing a complete flattening approach for the string/integer conversion. The approach is built upon a new quantifier elimination procedure for the linear-exponential arithmetic (namely, the extension of Presburger arithmetic with exponential functions, denoted by ExpPA) improved from the one proposed by Cherlin and Point in 1986. We analyze the complexity of our quantifier elimination procedure and show that the decision problem for existential ExpPA formulas is in 3-EXPTIME. Up to our knowledge, this is the first elementary complexity upper bound for this problem. While the quantifier elimination procedure is too expensive to be implemented efficiently, we propose various optimizations and provide a prototypical implementation. We evaluate the performance of our implementation on the benchmarks that are generated from the string hash functions as well as randomly. The experimental results show that our implementation outperforms the state-of-the-art solvers.
PubDate: 2023-10-24
DOI: 10.1007/s00236-023-00446-4
-
- Discovering workflow nets of concurrent iterative processes
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A novel and efficient method for discovering concurrent workflow processes is presented. It allows building a suitable workflow net (WFN) from a large event log \(\lambda \) , which represents the behaviour of complex iterative processes involving concurrency. First, the t-invariants are determined from \(\lambda \) ; this allows computing the causal and concurrent relations between the events and the implicit causal relations between events that do not appear consecutively in \(\lambda \) . Then a 1-bounded WFN is built, which could be eventually adjusted if its t-invariants do not match with those computed from \(\lambda \) . The discovered model allows firing all the traces in \(\lambda \) . The procedures derived from the method are polynomial time on \( \lambda \) ; they have been implemented and tested on artificial logs.
PubDate: 2023-09-14
DOI: 10.1007/s00236-023-00445-5
-
- The second step in characterizing a three-word code
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In the fields of combinatorics on words and theory of codes, a two-word language \(\{x, y\}\) is a code if and only if \(xy \not = yx\) . But up to now, corresponding characterizations for a three-word language, which forms a code, have not been completely found. Let \(X=\{x,\ y,\ z\}\) be a three-word language and \( x ,\ y ,\ z \) be their lengths. When \( x = y < z \) , a necessary and sufficient condition for X to be a code was obtained in 2018. If \( x < y = z \le 2 x \) , a necessary and sufficient condition for X to be a code is proposed in this paper.
PubDate: 2023-09-08
DOI: 10.1007/s00236-023-00444-6
-
- Dot to dot, simple or sophisticated: a survey on shape reconstruction
algorithms-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Dot pattern points are the samples taken from all regions of a 2D object, either inside or the boundary. Given a set of dot pattern points in the plane, the shape reconstruction problem seeks to find the boundaries of the points. These boundaries are not mathematically well-defined. Hence, a superior algorithm is the one which produces the result closest to the human visual perception. There are different challenges in designing these algorithms, such as the independence from human supervision, and the ability to detect multiple components, holes and sharp corners. In this paper, we present a thorough review on the rich body of research in shape reconstruction, classify the ideas behind the algorithms, and highlight their pros and cons. Moreover, to overcome the barriers of implementing these algorithms, we provide an integrated application to visualize the outputs of the prominent algorithms for further comparison.
PubDate: 2023-08-01
DOI: 10.1007/s00236-023-00443-7
-
- Testing membership for timed automata
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Given a timed automaton which admits thick components and a timed word w, we present a tester which decides if w is in the language of the automaton or if w is \(\epsilon \) -far from the language, using finitely many samples taken from the weighted time distribution \(\mu \) associated with the input w. We introduce a distance between timed words, the timed edit distance, which generalizes the classical edit distance. A timed word w is \(\epsilon \) -far from a timed language if its relative distance to the language is greater than \(\epsilon \) .
PubDate: 2023-07-17
DOI: 10.1007/s00236-023-00442-8
-
