BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Andreas Maletti

Andreas Maletti appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata TheoryComputation and LanguageComputational ComplexityData Structures and Algorithms

Catalog footprint

What is connected

9works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

9 published item(s)

preprint2022arXiv

Strong Equivalence of TAG and CCG

Tree-adjoining grammar (TAG) and combinatory categorial grammar (CCG) are two well-established mildly context-sensitive grammar formalisms that are known to have the same expressive power on strings (i.e., generate the same class of string languages). It is demonstrated that their expressive power on trees also essentially coincides. In fact, CCG without lexicon entries for the empty string and only first-order rules of degree at most 2 are sufficient for its full expressive power.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Hyper-Minimization for Deterministic Weighted Tree Automata

Hyper-minimization is a state reduction technique that allows a finite change in the semantics. The theory for hyper-minimization of deterministic weighted tree automata is provided. The presence of weights slightly complicates the situation in comparison to the unweighted case. In addition, the first hyper-minimization algorithm for deterministic weighted tree automata, weighted over commutative semifields, is provided together with some implementation remarks that enable an efficient implementation. In fact, the same run-time O(m log n) as in the unweighted case is obtained, where m is the size of the deterministic weighted tree automaton and n is its number of states.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Composition Closure of Linear Extended Top-down Tree Transducers

Linear extended top-down tree transducers (or synchronous tree-substitution grammars) are popular formal models of tree transformations. The expressive power of compositions of such transducers with and without regular look-ahead is investigated. In particular, the restrictions of nondeletion, epsilon-freeness, and strictness are considered. The composition hierarchy turns out to be finite for all epsilon-free (all rules consume input) variants of these transducers except for nondeleting epsilon-free linear extended top-down tree transducers. The least number of transducers needed for the full expressive power of arbitrary compositions is presented. In all remaining cases (including nondeleting epsilon-free linear extended top-down tree transducers) the composition hierarchy does not collapse.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Random Generation of Nondeterministic Finite-State Tree Automata

Algorithms for (nondeterministic) finite-state tree automata (FTAs) are often tested on random FTAs, in which all internal transitions are equiprobable. The run-time results obtained in this manner are usually overly optimistic as most such generated random FTAs are trivial in the sense that the number of states of an equivalent minimal deterministic FTA is extremely small. It is demonstrated that nontrivial random FTAs are obtained only for a narrow band of transition probabilities. Moreover, an analytic analysis yields a formula to approximate the transition probability that yields the most complex random FTAs, which should be used in experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On minimising automata with errors

The problem of k-minimisation for a DFA M is the computation of a smallest DFA N (where the size |M| of a DFA M is the size of the domain of the transition function) such that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs in time O(|M| log^2 n) where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster O(|M| log n) algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k-minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k-minimal DFA N differing from DFA M on at most m words. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that DFA M and N differ on at msot m words.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal Hyper-Minimization

Minimal deterministic finite automata (DFAs) can be reduced further at the expense of a finite number of errors. Recently, such minimization algorithms have been improved to run in time O(n log n), where n is the number of states of the input DFA, by [Gawrychowski and Jeż: Hyper-minimisation made efficient. Proc. MFCS, LNCS 5734, 2009] and [Holzer and Maletti: An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010]. Both algorithms return a DFA that is as small as possible, while only committing a finite number of errors. These algorithms are further improved to return a DFA that commits the least number of errors at the expense of an increased (quadratic) run-time. This solves an open problem of [Badr, Geffert, and Shipman: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl. 43, 2009]. In addition, an experimental study on random automata is performed and the effects of the existing algorithms and the new algorithm are reported.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Simulation vs. Equivalence

For several semirings S, two weighted finite automata with multiplicities in S are equivalent if and only if they can be connected by a chain of simulations. Such a semiring S is called "proper". It is known that the Boolean semiring, the semiring of natural numbers, the ring of integers, all finite commutative positively ordered semirings and all fields are proper. The semiring S is Noetherian if every subsemimodule of a finitely generated S-semimodule is finitely generated. First, it is shown that all Noetherian semirings and thus all commutative rings and all finite semirings are proper. Second, the tropical semiring is shown not to be proper. So far there has not been any example of a semiring that is not proper.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Simulations of Weighted Tree Automata

Simulations of weighted tree automata (wta) are considered. It is shown how such simulations can be decomposed into simpler functional and dual functional simulations also called forward and backward simulations. In addition, it is shown in several cases (fields, commutative rings, Noetherian semirings, semiring of natural numbers) that all equivalent wta M and N can be joined by a finite chain of simulations. More precisely, in all mentioned cases there exists a single wta that simulates both M and N. Those results immediately yield decidability of equivalence provided that the semiring is finitely (and effectively) presented.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Properties of quasi-alphabetic tree bimorphisms

We study the class of quasi-alphabetic relations, i.e., tree transformations defined by tree bimorphisms with two quasi-alphabetic tree homomorphisms and a regular tree language. We present a canonical representation of these relations; as an immediate consequence, we get the closure under union. Also, we show that they are not closed under intersection and complement, and do not preserve most common operations on trees (branches, subtrees, v-product, v-quotient, f-top-catenation). Moreover, we prove that the translations defined by quasi-alphabetic tree bimorphism are exactly products of context-free string languages. We conclude by presenting the connections between quasi-alphabetic relations, alphabetic relations and classes of tree transformations defined by several types of top-down tree transducers. Furthermore, we get that quasi-alphabetic relations preserve the recognizable and algebraic tree languages.

0 citations0 reviewsNo code linkedOpen access