Ambiguity Hierarchy of Regular Infinite Tree Languages
- URL: http://arxiv.org/abs/2009.02985v3
- Date: Wed, 11 Aug 2021 18:36:38 GMT
- Title: Ambiguity Hierarchy of Regular Infinite Tree Languages
- Authors: Alexander Rabinovich and Doron Tiferet
- Abstract summary: A language is k-ambiguous (respectively, boundedly, finitely, ambiguous) if it is accepted by a k-ambiguous automaton.
An automaton is boundedly ambiguous if it is k-ambiguous for some $k in mathbbN$.
- Score: 77.34726150561087
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An automaton is unambiguous if for every input it has at most one accepting
computation. An automaton is k-ambiguous (for k > 0) if for every input it has
at most k accepting computations. An automaton is boundedly ambiguous if it is
k-ambiguous for some $k \in \mathbb{N}$. An automaton is finitely
(respectively, countably) ambiguous if for every input it has at most finitely
(respectively, countably) many accepting computations.
The degree of ambiguity of a regular language is defined in a natural way. A
language is k-ambiguous (respectively, boundedly, finitely, countably
ambiguous) if it is accepted by a k-ambiguous (respectively, boundedly,
finitely, countably ambiguous) automaton. Over finite words every regular
language is accepted by a deterministic automaton. Over finite trees every
regular language is accepted by an unambiguous automaton. Over $\omega$-words
every regular language is accepted by an unambiguous B\"uchi automaton and by a
deterministic parity automaton. Over infinite trees Carayol et al. showed that
there are ambiguous languages.
We show that over infinite trees there is a hierarchy of degrees of
ambiguity: For every k > 1 there are k-ambiguous languages that are not k - 1
ambiguous; and there are finitely (respectively countably, uncountably)
ambiguous languages that are not boundedly (respectively finitely, countably)
ambiguous.
Related papers
- Directed Regular and Context-Free Languages [0.6906005491572399]
A language $L$ is emphdirected if every pair of words in $L$ have a common (scattered) superword in $L$.
For context-free languages, the directedness problem is known to be coNEXP-complete.
We show that for context-free languages, the directedness problem is PSPACE-complete.
arXiv Detail & Related papers (2024-01-13T16:13:45Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA)
We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations)
For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
arXiv Detail & Related papers (2023-10-23T18:26:00Z) - Lexinvariant Language Models [84.2829117441298]
Token embeddings, a mapping from discrete lexical symbols to continuous vectors, are at the heart of any language model (LM)
We study textitlexinvariantlanguage models that are invariant to lexical symbols and therefore do not need fixed token embeddings in practice.
We show that a lexinvariant LM can attain perplexity comparable to that of a standard language model, given a sufficiently long context.
arXiv Detail & Related papers (2023-05-24T19:10:46Z) - The boundaries of meaning: a case study in neural machine translation [0.0]
Subword segmentation algorithms are widely employed in language modeling, machine translation, and other tasks since 2016.
These algorithms often cut words into semantically opaque pieces, such as 'period', 'on', 't', and 'ist'
arXiv Detail & Related papers (2022-10-02T20:26:20Z) - On the Intersection of Context-Free and Regular Languages [71.61206349427509]
We generalize the Bar-Hillel construction to handle finite-state automatons with $varepsilon$-arcs.
We prove that our construction leads to a grammar that encodes the structure of both the input automaton and grammar while retaining the size of the original construction.
arXiv Detail & Related papers (2022-09-14T17:49:06Z) - On (co-lex) Ordering Automata [2.800608984818919]
We show that a canonical, minimum-width, partially-ordered automaton accepting a language L can be exhibited.
Using H we prove that the width of the language can be effectively computed from the minimum automaton recognizing the language.
arXiv Detail & Related papers (2021-06-04T07:41:58Z) - Language learnability in the limit for general metrics: a Gold-Angluin
result [91.3755431537592]
We use Niyogi's extended version of a theorem by Blum and Blum (1975) on the existence of locking data sets to prove a necessary condition for learnability in the limit of any family of languages in any given metric.
When the language family is further assumed to contain all finite languages, the same condition also becomes sufficient for learnability in the limit.
arXiv Detail & Related papers (2021-03-24T13:11:09Z) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
We show that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax.
We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth.
We prove that an RNN with $O(m log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction.
arXiv Detail & Related papers (2020-10-15T04:42:29Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.