On (co-lex) Ordering Automata

• URL: http://arxiv.org/abs/2106.02309v1
• Date: Fri, 4 Jun 2021 07:41:58 GMT
• Title: On (co-lex) Ordering Automata
• Authors: Giovanna D'Agostino and Nicola Cotumaccio and Alberto Policriti and Nicola Prezza
• Abstract summary: 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.
• Score: 2.800608984818919
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted by A. But words can be ordered and among the many possible orders a very natural one is the co-lexicographic one. Such naturalness stems from the fact that it suggests a transfer of the order from words to the automaton's states. In a number of papers automata admitting a total ordering of states coherent with the ordering of the set of words reaching them have been proposed. Such class of ordered automata -- the Wheeler automata -- turned out to be efficiently stored/searched using an index. Unfortunately not all automata can be totally ordered as previously outlined. However, automata can always be partially ordered and an intrinsic measure of their complexity can be defined and effectively determined, as the minimum width of one of their admissible partial orders. As shown in previous works, this new concept of width of an automaton has useful consequences in the fields of graph compression, indexing data structures, and automata theory. In this paper we prove that a canonical, minimum-width, partially-ordered automaton accepting a language L -- dubbed the Hasse automaton H of L -- can be exhibited. H provides, in a precise sense, the best possible way to (partially) order the states of any automaton accepting L, as long as we want to maintain an operational link with the (co-lexicographic) order of Pf(L(A)). Using H we prove that the width of the language can be effectively computed from the minimum automaton recognizing the language. Finally, we explore the relationship between two (often conflicting) objectives: minimizing the width and minimizing the number of states of an automaton.

Related papers

• Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination [2.024925013349319]
  We study an L*-style learning algorithm for weighted automata over the max-plus semiring. We show that it can fail to maintain consistency of tables, and can thus make equivalence queries on obviously wrong hypothesis automata.
  arXiv  Detail & Related papers  (2024-07-13T05:08:06Z)
• Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure [13.231546105751015]
  We present counting reward automata-a finite state machine variant capable of modelling any reward function expressible as a formal language. We prove that an agent equipped with such an abstract machine is able to solve a larger set of tasks than those utilising current approaches.
  arXiv  Detail & Related papers  (2023-12-18T17:20:38Z)
• Automata Cascades: Expressivity and Sample Complexity [90.53326983143644]
  We show that cascades allow for describing the sample complexity of automata in terms of their components. Our results show that one can in principle learn automata with infinite input alphabets and a number of states that is exponential in the amount of data available.
  arXiv  Detail & Related papers  (2022-11-25T11:02:33Z)
• Automatic Label Sequence Generation for Prompting Sequence-to-sequence Models [105.4590533269863]
  We propose AutoSeq, a fully automatic prompting method. We adopt natural language prompts on sequence-to-sequence models. Our method reveals the potential of sequence-to-sequence models in few-shot learning.
  arXiv  Detail & Related papers  (2022-09-20T01:35:04Z)
• 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)
• Alternating Good-for-MDP Automata [4.429642479975602]
  We show that it is possible to repair bad-for-MDPs (GFM) automata by using good-for-MDPs (GFM) B"uchi automata. A translation to nondeterministic Rabin or B"uchi automata comes at an exponential cost, even without requiring the target automaton to be good-for-MDPs. The surprising answer is that we have to pay significantly less when we instead expand the good-for-MDP property to alternating automata.
  arXiv  Detail & Related papers  (2022-05-06T14:01:47Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  We present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding.
  arXiv  Detail & Related papers  (2020-09-08T16:42:55Z)
• Ambiguity Hierarchy of Regular Infinite Tree Languages [77.34726150561087]
  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$.
  arXiv  Detail & Related papers  (2020-09-07T10:08:24Z)
• Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
  We introduce refutationally complete superposition calculi for intentional and extensional clausal $lambda$-free higher-order logic. The calculi are parameterized by a term order that need not be fully monotonic, making it possible to employ the $lambda$-free higher-order lexicographic path and Knuth-Bendix orders.
  arXiv  Detail & Related papers  (2020-05-05T12:10:21Z)

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.