java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e1_152.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:59:04,538 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:59:04,540 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:59:04,564 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:59:04,565 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:59:04,566 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:59:04,570 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:59:04,573 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:59:04,576 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:59:04,577 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:59:04,578 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:59:04,578 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:59:04,579 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:59:04,583 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:59:04,584 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:59:04,584 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:59:04,598 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:59:04,600 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:59:04,602 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:59:04,603 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:59:04,604 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:59:04,611 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:59:04,611 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:59:04,612 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:59:04,613 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:59:04,614 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:59:04,614 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:59:04,617 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:59:04,618 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:59:04,619 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:59:04,619 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:59:04,625 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:59:04,625 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:59:04,626 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:59:04,627 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:59:04,627 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:59:04,650 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:59:04,650 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:59:04,651 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:59:04,651 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:59:04,651 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:59:04,652 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:59:04,652 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:59:04,652 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:59:04,652 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:59:04,653 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:59:04,653 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:59:04,653 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:59:04,653 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:59:04,653 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:59:04,654 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:59:04,654 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:59:04,654 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:59:04,654 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:59:04,654 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:59:04,656 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:59:04,656 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:59:04,714 INFO ]: Repository-Root is: /tmp [2018-06-22 15:59:04,743 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:59:04,761 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:59:04,763 INFO ]: Initializing SmtParser... [2018-06-22 15:59:04,764 INFO ]: SmtParser initialized [2018-06-22 15:59:04,764 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e1_152.smt2 [2018-06-22 15:59:04,766 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:59:04,879 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e1_152.smt2 unknown [2018-06-22 15:59:05,294 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e1_152.smt2 [2018-06-22 15:59:05,303 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:59:05,318 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:59:05,319 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:59:05,319 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:59:05,319 INFO ]: ChcToBoogie initialized [2018-06-22 15:59:05,323 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,388 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05 Unit [2018-06-22 15:59:05,389 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:59:05,389 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:59:05,389 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:59:05,389 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:59:05,416 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,417 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,428 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,428 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,433 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,434 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,436 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... [2018-06-22 15:59:05,439 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:59:05,441 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:59:05,441 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:59:05,441 INFO ]: RCFGBuilder initialized [2018-06-22 15:59:05,442 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 15:59:05,454 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:59:05,454 INFO ]: Found specification of procedure False [2018-06-22 15:59:05,454 INFO ]: Found implementation of procedure False [2018-06-22 15:59:05,454 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:59:05,454 INFO ]: Found specification of procedure state [2018-06-22 15:59:05,454 INFO ]: Found implementation of procedure state [2018-06-22 15:59:05,454 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:59:05,454 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:59:05,454 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:59:05,792 INFO ]: Using library mode [2018-06-22 15:59:05,792 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:59:05 BoogieIcfgContainer [2018-06-22 15:59:05,793 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:59:05,794 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:59:05,794 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:59:05,798 INFO ]: TraceAbstraction initialized [2018-06-22 15:59:05,798 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:59:05" (1/3) ... [2018-06-22 15:59:05,799 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@57099f37 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:59:05, skipping insertion in model container [2018-06-22 15:59:05,799 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:59:05" (2/3) ... [2018-06-22 15:59:05,799 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@57099f37 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:59:05, skipping insertion in model container [2018-06-22 15:59:05,799 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:59:05" (3/3) ... [2018-06-22 15:59:05,802 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:59:05,813 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:59:05,825 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:59:05,881 INFO ]: Using default assertion order modulation [2018-06-22 15:59:05,882 INFO ]: Interprodecural is true [2018-06-22 15:59:05,882 INFO ]: Hoare is false [2018-06-22 15:59:05,882 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:59:05,882 INFO ]: Backedges is TWOTRACK [2018-06-22 15:59:05,882 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:59:05,882 INFO ]: Difference is false [2018-06-22 15:59:05,882 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:59:05,882 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:59:05,899 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:59:05,913 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:59:05,913 INFO ]: Found error trace [2018-06-22 15:59:05,915 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:05,915 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:05,921 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:59:05,924 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:05,925 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:05,973 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:05,973 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:59:05,973 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:06,044 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:06,231 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:59:06,234 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:59:06,234 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:59:06,236 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:59:06,253 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:59:06,254 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:59:06,256 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:59:06,377 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:59:06,377 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:59:06,378 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:59:06,380 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:59:06,380 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:59:06,398 INFO ]: With dead ends: 13 [2018-06-22 15:59:06,398 INFO ]: Without dead ends: 13 [2018-06-22 15:59:06,400 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:59:06,418 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:59:06,456 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:59:06,458 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:59:06,458 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:59:06,460 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:59:06,460 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:59:06,460 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:59:06,460 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:59:06,460 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:59:06,462 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:59:06,462 INFO ]: Found error trace [2018-06-22 15:59:06,462 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:06,462 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:06,463 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:59:06,463 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:06,463 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:06,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:06,465 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:59:06,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:06,518 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:06,676 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:59:06,676 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:59:06,676 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:59:06,694 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:59:06,815 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:06,826 INFO ]: Computing forward predicates... [2018-06-22 15:59:07,500 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:59:07,537 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:59:07,537 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:59:07,538 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:59:07,538 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:59:07,538 INFO ]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:59:07,539 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:59:08,036 WARN ]: Spent 266.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 15:59:08,251 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 7 [2018-06-22 15:59:08,437 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:59:08,438 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:59:08,438 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:59:08,438 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:59:08,438 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:59:08,439 INFO ]: With dead ends: 15 [2018-06-22 15:59:08,439 INFO ]: Without dead ends: 15 [2018-06-22 15:59:08,440 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:59:08,440 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:59:08,443 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:59:08,443 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:59:08,444 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:59:08,444 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:59:08,444 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:59:08,444 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:59:08,444 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:59:08,444 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:59:08,444 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:59:08,445 INFO ]: Found error trace [2018-06-22 15:59:08,445 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:08,445 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:08,445 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:59:08,445 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:08,445 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:08,446 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:08,446 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:59:08,446 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:08,537 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:08,967 WARN ]: Spent 248.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-06-22 15:59:09,187 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:59:09,187 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:59:09,187 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:59:09,196 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:59:09,272 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:59:09,272 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:09,277 INFO ]: Computing forward predicates... [2018-06-22 15:59:09,926 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:59:09,947 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:59:09,947 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 15:59:09,948 INFO ]: Interpolant automaton has 13 states [2018-06-22 15:59:09,948 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 15:59:09,948 INFO ]: CoverageRelationStatistics Valid=25, Invalid=131, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:59:09,948 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-22 15:59:10,299 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 36 [2018-06-22 15:59:10,542 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:59:10,542 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:59:10,542 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:59:10,542 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 15:59:10,543 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:59:10,543 INFO ]: With dead ends: 19 [2018-06-22 15:59:10,543 INFO ]: Without dead ends: 19 [2018-06-22 15:59:10,544 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:59:10,544 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:59:10,547 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:59:10,547 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:59:10,548 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:59:10,548 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 15:59:10,548 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:59:10,548 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:59:10,548 INFO ]: Interpolant automaton has 13 states. [2018-06-22 15:59:10,548 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:59:10,549 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:59:10,549 INFO ]: Found error trace [2018-06-22 15:59:10,549 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:10,549 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:10,549 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 3 times [2018-06-22 15:59:10,549 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:10,549 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:10,550 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:10,550 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:59:10,550 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:10,695 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:11,313 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 73 [2018-06-22 15:59:11,542 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:59:11,542 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:59:11,542 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 15:59:11,558 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:59:11,685 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 15:59:11,685 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:11,691 INFO ]: Computing forward predicates... [2018-06-22 15:59:12,308 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:59:12,330 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:59:12,330 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2018-06-22 15:59:12,330 INFO ]: Interpolant automaton has 21 states [2018-06-22 15:59:12,330 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 15:59:12,331 INFO ]: CoverageRelationStatistics Valid=48, Invalid=372, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:59:12,331 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 21 states. [2018-06-22 15:59:12,797 WARN ]: Spent 365.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 119 [2018-06-22 15:59:13,219 WARN ]: Spent 318.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 114 [2018-06-22 15:59:13,585 WARN ]: Spent 330.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 108 [2018-06-22 15:59:13,904 WARN ]: Spent 279.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 111 [2018-06-22 15:59:14,241 WARN ]: Spent 281.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 110 [2018-06-22 15:59:14,533 WARN ]: Spent 248.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 114 [2018-06-22 15:59:14,581 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:59:14,582 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:59:14,582 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:59:14,582 INFO ]: Start accepts. Automaton has 21 states. Word has length 25 [2018-06-22 15:59:14,583 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:59:14,583 INFO ]: With dead ends: 23 [2018-06-22 15:59:14,583 INFO ]: Without dead ends: 23 [2018-06-22 15:59:14,584 INFO ]: 0 DeclaredPredicates, 43 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=155, Invalid=601, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:59:14,584 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:59:14,588 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:59:14,588 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:59:14,589 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:59:14,589 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 25 [2018-06-22 15:59:14,589 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:59:14,589 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:59:14,589 INFO ]: Interpolant automaton has 21 states. [2018-06-22 15:59:14,590 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:59:14,591 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:59:14,591 INFO ]: Found error trace [2018-06-22 15:59:14,591 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:14,591 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:14,591 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 4 times [2018-06-22 15:59:14,591 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:14,591 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:14,592 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:14,592 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:59:14,592 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:14,771 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:15,774 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:59:15,774 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:59:15,774 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:59:15,780 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:59:15,929 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:59:15,930 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:15,941 INFO ]: Computing forward predicates... [2018-06-22 15:59:17,036 INFO ]: Checked inductivity of 78 backedges. 1 proven. 56 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:59:17,059 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:59:17,059 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 29 [2018-06-22 15:59:17,059 INFO ]: Interpolant automaton has 29 states [2018-06-22 15:59:17,059 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 15:59:17,060 INFO ]: CoverageRelationStatistics Valid=74, Invalid=738, Unknown=0, NotChecked=0, Total=812 [2018-06-22 15:59:17,060 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 29 states. [2018-06-22 15:59:17,460 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 91 [2018-06-22 15:59:17,718 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 64 [2018-06-22 15:59:18,179 WARN ]: Spent 408.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 89 [2018-06-22 15:59:18,621 WARN ]: Spent 328.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 90 [2018-06-22 15:59:18,996 WARN ]: Spent 308.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 90 [2018-06-22 15:59:19,302 WARN ]: Spent 261.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 85 [2018-06-22 15:59:19,769 WARN ]: Spent 282.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 86 [2018-06-22 15:59:19,819 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:59:19,819 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:59:19,820 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:59:19,820 INFO ]: Start accepts. Automaton has 29 states. Word has length 33 [2018-06-22 15:59:19,820 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:59:19,821 INFO ]: With dead ends: 25 [2018-06-22 15:59:19,821 INFO ]: Without dead ends: 25 [2018-06-22 15:59:19,822 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 136 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=236, Invalid=1096, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:59:19,822 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:59:19,825 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:59:19,825 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:59:19,826 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:59:19,826 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:59:19,826 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:59:19,826 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:59:19,826 INFO ]: Interpolant automaton has 29 states. [2018-06-22 15:59:19,826 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:59:19,827 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:59:19,827 INFO ]: Found error trace [2018-06-22 15:59:19,827 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:19,827 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:19,827 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 5 times [2018-06-22 15:59:19,827 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:19,827 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:19,829 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:19,829 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:59:19,829 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:20,011 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:20,633 WARN ]: Spent 248.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:59:21,019 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 27 [2018-06-22 15:59:21,214 WARN ]: Spent 139.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 26 [2018-06-22 15:59:21,412 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 46 [2018-06-22 15:59:21,875 WARN ]: Spent 445.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 50 [2018-06-22 15:59:22,023 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 34 [2018-06-22 15:59:22,942 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:59:22,942 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:59:22,942 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:59:22,949 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:59:23,106 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2018-06-22 15:59:23,106 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:23,114 INFO ]: Computing forward predicates... [2018-06-22 15:59:23,589 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 15:59:24,057 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:59:24,089 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:59:24,089 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 33 [2018-06-22 15:59:24,090 INFO ]: Interpolant automaton has 33 states [2018-06-22 15:59:24,090 INFO ]: Constructing interpolant automaton starting with 33 interpolants. [2018-06-22 15:59:24,091 INFO ]: CoverageRelationStatistics Valid=81, Invalid=975, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:59:24,091 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 33 states. [2018-06-22 15:59:24,810 WARN ]: Spent 579.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 108 [2018-06-22 15:59:25,273 WARN ]: Spent 328.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 87 [2018-06-22 15:59:25,657 WARN ]: Spent 331.00 ms on a formula simplification. DAG size of input: 175 DAG size of output: 90 [2018-06-22 15:59:26,161 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 178 DAG size of output: 87 [2018-06-22 15:59:26,533 WARN ]: Spent 293.00 ms on a formula simplification. DAG size of input: 172 DAG size of output: 84 [2018-06-22 15:59:26,895 WARN ]: Spent 304.00 ms on a formula simplification. DAG size of input: 159 DAG size of output: 87 [2018-06-22 15:59:27,230 WARN ]: Spent 271.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 84 [2018-06-22 15:59:27,695 WARN ]: Spent 288.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 85 [2018-06-22 15:59:28,143 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 92 [2018-06-22 15:59:28,660 WARN ]: Spent 436.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 95 [2018-06-22 15:59:28,741 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:59:28,741 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:59:28,745 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:59:28,745 INFO ]: Start accepts. Automaton has 33 states. Word has length 37 [2018-06-22 15:59:28,746 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:59:28,746 INFO ]: With dead ends: 31 [2018-06-22 15:59:28,746 INFO ]: Without dead ends: 31 [2018-06-22 15:59:28,747 INFO ]: 0 DeclaredPredicates, 65 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 138 ImplicationChecksByTransitivity, 7.4s TimeCoverageRelationStatistics Valid=364, Invalid=1528, Unknown=0, NotChecked=0, Total=1892 [2018-06-22 15:59:28,747 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:59:28,753 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:59:28,753 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:59:28,754 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:59:28,754 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 37 [2018-06-22 15:59:28,754 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:59:28,754 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:59:28,754 INFO ]: Interpolant automaton has 33 states. [2018-06-22 15:59:28,754 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:59:28,756 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:59:28,756 INFO ]: Found error trace [2018-06-22 15:59:28,756 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:28,756 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:28,756 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 6 times [2018-06-22 15:59:28,756 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:28,756 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:28,757 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:28,757 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:59:28,757 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:29,115 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:30,785 WARN ]: Spent 542.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2018-06-22 15:59:31,036 WARN ]: Spent 178.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 21 [2018-06-22 15:59:31,667 WARN ]: Spent 600.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 23 [2018-06-22 15:59:32,722 WARN ]: Spent 901.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 21 [2018-06-22 15:59:33,147 WARN ]: Spent 393.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 39 [2018-06-22 15:59:33,656 WARN ]: Spent 424.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 52 [2018-06-22 15:59:33,846 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 42 [2018-06-22 15:59:34,481 WARN ]: Spent 557.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 59 [2018-06-22 15:59:35,270 WARN ]: Spent 692.00 ms on a formula simplification. DAG size of input: 224 DAG size of output: 65 [2018-06-22 15:59:35,682 WARN ]: Spent 315.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 47 [2018-06-22 15:59:36,045 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 126 DAG size of output: 39 [2018-06-22 15:59:36,858 WARN ]: Spent 510.00 ms on a formula simplification. DAG size of input: 197 DAG size of output: 47 [2018-06-22 15:59:37,390 WARN ]: Spent 389.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 45 [2018-06-22 15:59:37,612 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 22 [2018-06-22 15:59:38,011 WARN ]: Spent 298.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 9 [2018-06-22 15:59:38,703 WARN ]: Spent 569.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 9 [2018-06-22 15:59:39,263 WARN ]: Spent 408.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 6 [2018-06-22 15:59:39,473 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:59:39,473 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:59:39,473 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:59:39,478 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:59:39,734 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 11 check-sat command(s) [2018-06-22 15:59:39,734 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:59:39,754 INFO ]: Computing forward predicates... [2018-06-22 15:59:41,423 WARN ]: Spent 637.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 13 [2018-06-22 15:59:42,565 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:59:42,587 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:59:42,587 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 45 [2018-06-22 15:59:42,588 INFO ]: Interpolant automaton has 45 states [2018-06-22 15:59:42,588 INFO ]: Constructing interpolant automaton starting with 45 interpolants. [2018-06-22 15:59:42,588 INFO ]: CoverageRelationStatistics Valid=144, Invalid=1836, Unknown=0, NotChecked=0, Total=1980 [2018-06-22 15:59:42,588 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 45 states. [2018-06-22 15:59:43,481 WARN ]: Spent 704.00 ms on a formula simplification. DAG size of input: 222 DAG size of output: 141 [2018-06-22 15:59:44,400 WARN ]: Spent 808.00 ms on a formula simplification. DAG size of input: 265 DAG size of output: 127 [2018-06-22 15:59:45,478 WARN ]: Spent 986.00 ms on a formula simplification. DAG size of input: 254 DAG size of output: 137 [2018-06-22 15:59:46,346 WARN ]: Spent 743.00 ms on a formula simplification. DAG size of input: 239 DAG size of output: 135 [2018-06-22 15:59:47,134 WARN ]: Spent 694.00 ms on a formula simplification. DAG size of input: 228 DAG size of output: 129 [2018-06-22 15:59:47,835 WARN ]: Spent 618.00 ms on a formula simplification. DAG size of input: 223 DAG size of output: 123 [2018-06-22 15:59:48,576 WARN ]: Spent 655.00 ms on a formula simplification. DAG size of input: 223 DAG size of output: 127 [2018-06-22 15:59:49,360 WARN ]: Spent 686.00 ms on a formula simplification. DAG size of input: 221 DAG size of output: 127 [2018-06-22 15:59:50,140 WARN ]: Spent 672.00 ms on a formula simplification. DAG size of input: 222 DAG size of output: 128 [2018-06-22 15:59:50,914 WARN ]: Spent 648.00 ms on a formula simplification. DAG size of input: 226 DAG size of output: 127 [2018-06-22 15:59:51,785 WARN ]: Spent 665.00 ms on a formula simplification. DAG size of input: 221 DAG size of output: 127 [2018-06-22 15:59:52,568 WARN ]: Spent 648.00 ms on a formula simplification. DAG size of input: 217 DAG size of output: 123 [2018-06-22 15:59:53,374 WARN ]: Spent 665.00 ms on a formula simplification. DAG size of input: 222 DAG size of output: 136 [2018-06-22 15:59:53,443 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:59:53,443 INFO ]: Finished difference Result 37 states and 38 transitions. [2018-06-22 15:59:53,445 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 15:59:53,445 INFO ]: Start accepts. Automaton has 45 states. Word has length 49 [2018-06-22 15:59:53,445 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:59:53,446 INFO ]: With dead ends: 37 [2018-06-22 15:59:53,446 INFO ]: Without dead ends: 37 [2018-06-22 15:59:53,447 INFO ]: 0 DeclaredPredicates, 86 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 233 ImplicationChecksByTransitivity, 21.7s TimeCoverageRelationStatistics Valid=652, Invalid=2770, Unknown=0, NotChecked=0, Total=3422 [2018-06-22 15:59:53,447 INFO ]: Start minimizeSevpa. Operand 37 states. [2018-06-22 15:59:53,454 INFO ]: Finished minimizeSevpa. Reduced states from 37 to 37. [2018-06-22 15:59:53,454 INFO ]: Start removeUnreachable. Operand 37 states. [2018-06-22 15:59:53,455 INFO ]: Finished removeUnreachable. Reduced from 37 states to 37 states and 38 transitions. [2018-06-22 15:59:53,455 INFO ]: Start accepts. Automaton has 37 states and 38 transitions. Word has length 49 [2018-06-22 15:59:53,455 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:59:53,455 INFO ]: Abstraction has 37 states and 38 transitions. [2018-06-22 15:59:53,455 INFO ]: Interpolant automaton has 45 states. [2018-06-22 15:59:53,455 INFO ]: Start isEmpty. Operand 37 states and 38 transitions. [2018-06-22 15:59:53,457 INFO ]: Finished isEmpty. Found accepting run of length 62 [2018-06-22 15:59:53,457 INFO ]: Found error trace [2018-06-22 15:59:53,457 INFO ]: trace histogram [14, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:59:53,457 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:59:53,457 INFO ]: Analyzing trace with hash 976009599, now seen corresponding path program 7 times [2018-06-22 15:59:53,457 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:59:53,457 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:59:53,458 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:53,458 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:59:53,458 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:59:54,607 INFO ]: Conjunction of SSA is unsat Received shutdown request... [2018-06-22 16:00:03,748 WARN ]: Verification canceled [2018-06-22 16:00:03,752 WARN ]: Timeout [2018-06-22 16:00:03,752 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:00:03 BoogieIcfgContainer [2018-06-22 16:00:03,752 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 16:00:03,753 INFO ]: Toolchain (without parser) took 58449.31 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 946.3 MB). Free memory was 257.2 MB in the beginning and 1.0 GB in the end (delta: -780.3 MB). Peak memory consumption was 969.7 MB. Max. memory is 3.6 GB. [2018-06-22 16:00:03,754 INFO ]: SmtParser took 0.11 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 16:00:03,754 INFO ]: ChcToBoogie took 70.27 ms. Allocated memory is still 308.8 MB. Free memory was 257.2 MB in the beginning and 255.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:00:03,754 INFO ]: Boogie Preprocessor took 51.17 ms. Allocated memory is still 308.8 MB. Free memory was 255.2 MB in the beginning and 253.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:00:03,755 INFO ]: RCFGBuilder took 351.44 ms. Allocated memory is still 308.8 MB. Free memory was 253.2 MB in the beginning and 237.3 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:00:03,755 INFO ]: TraceAbstraction took 57958.45 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 946.3 MB). Free memory was 237.3 MB in the beginning and 1.0 GB in the end (delta: -800.3 MB). Peak memory consumption was 949.7 MB. Max. memory is 3.6 GB. [2018-06-22 16:00:03,758 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.11 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 70.27 ms. Allocated memory is still 308.8 MB. Free memory was 257.2 MB in the beginning and 255.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 51.17 ms. Allocated memory is still 308.8 MB. Free memory was 255.2 MB in the beginning and 253.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 351.44 ms. Allocated memory is still 308.8 MB. Free memory was 253.2 MB in the beginning and 237.3 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 57958.45 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 946.3 MB). Free memory was 237.3 MB in the beginning and 1.0 GB in the end (delta: -800.3 MB). Peak memory consumption was 949.7 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 62 with TraceHistMax 14, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateComparison was comparing new predicate (quantifier-free) to 4 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 57.8s OverallTime, 8 OverallIterations, 14 TraceHistogramMax, 22.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 79 SDtfs, 529 SDslu, 736 SDs, 0 SdLazy, 578 SolverSat, 628 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 304 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 188 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 556 ImplicationChecksByTransitivity, 38.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=37occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.7s SatisfiabilityAnalysisTime, 22.9s InterpolantComputationTime, 357 NumberOfCodeBlocks, 357 NumberOfCodeBlocksAsserted, 35 NumberOfCheckSat, 344 ConstructedInterpolants, 0 QuantifiedInterpolants, 155068 SizeOfPredicates, 266 NumberOfNonLiveVariables, 4518 ConjunctsInSsa, 363 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 237/884 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/car_6_e1_152.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_16-00-03-768.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/car_6_e1_152.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_16-00-03-768.csv Completed graceful shutdown